MPhil Thesis Defence


"A Skip-List Based Approach for Answering Approximate Nearest Neighbor
Queries"

By

Mr. Ka-Hang Wong


Abstract

We present a new algorithm for answering approximate nearest neighbor
queries that is inspired by skip lists. Our data structure uses linear
space and can answer queries in expected logarithmic time, under the
assumption that the query point is a random point of the set containing
the query point and the data points. We have implemented a practical
variant of this algorithm and show empirically that it performs
significantly better than existing approaches.


Date:			Friday, 25 January 2002

Time:			10:30a.m.-12:30p.m.

Venue:			Room 2302
			Lifts 17-18

Committee Members:	Dr. Sunil Arya (Supervisor)
			Dr. Siu-Wing Cheng (Chairman)
			Dr. Mordecai Golin


**** ALL are Welcome ****