A skip list approach for answering approximate nearest neighbor queries

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 of Award	2002
Original language	English
Awarding Institution	The Hong Kong University of Science and Technology