A skip list approach for answering approximate nearest neighbor queries
Ka-Hang Wong · 2002
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.