A skip list approach for answering approximate nearest neighbor queries
by Ka-Hang Wong
M.Phil. Computer Science
viii, 40 leaves : ill. ; 30 cm
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.
Permanent URL for this record: https://lbezone.hkust.edu.hk/bib/b728573