Nearest Neighbor Queries in Metric Spaces

For a metric space V with distance measure d, and sets S,Q subset V, this paper gives a data structure for answering nearest neighbor queries on S: given q epsilon V, find a the point in S closest to q. The set Q is used here in the construction of the data structure. The data structure may return incorrect answers, but it generally returns sites that are nearly the closest, as observed for some common cases. (When the points of S, Q, and q are uniformly distributed in a square, and the distance measure is l sub 2, a version of the data structure gives the correct answer 90% of the time, and on average .15 sites are closer than the returned site. For this version, searching requires about 34 distance evaluations for {S} = 2000, and the space required is about 10 bytes/site. Note that the algorithm uses the distance measure as a "black box". With 4000 similarly distributed points in R sup (20), and average search time of 325 distance evaluations gives a site for which about 2.5 sites are closer, on average).