A skip list approach for answering approximate nearest neighbor queries
by Ka-Hang Wong
THESIS
2002
M.Phil. Computer Science
viii, 40 leaves : ill. ; 30 cm
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.
Post a Comment