Nearest neighbor queries in metric spaces
Kenneth L. Clarkson · 1997
Given a set Sofn sites (points), andadistance measure cl, the nearest neighbor searching problem, or post office problem, istobuild adatastructure sothatgiven a query point q, the site nearest to g can be found quickly.This paper gives data structures for this problem when the sites and queries are in a metric space.The data structures can be analyzed when the metric space satisfies a certain spherepacking bound.Onedata structure, denoted D(S), requires expected O(n)(lgn)O(lK 1gT(s)) time to build.Here 'Y(S) is the distance ratio of S, the ratio of the distance between the farthest pair of points in S to the distance between the closest pair.The constant factors in the bound depend on the sphere-packing bound.When the query pointqis arandom element of {q} uS, as for example when q and the points of S are randomly generated from a common distribution, then the query time is expected (lgn)O(lglgrfs)).A side effect of building D(S) is to solve the all-nearest-neighbors problem for S. Another data structure given here, denoted &f(,$!,Q), requires aa input data an additional set Q, taken to berepresentative of the query points.Thecost of building this data structure is the same EMfor building D(S U Q).The data structure A4(S, Q) can sometimes return wrong answers, but when q is a random element of {q}UQ, the probability of failure is 0(log2n)/K, where K s lQ1/n is a parameter of the construction.When Q and {q} are random subsets of {q} UQ US, the expected query time for iM(S, Q) is O(Klogn)log T, when the returned answer is correct, and the expected space needed is O(n) Klog T.