Finding the Nearest Neighbor Using Queries to a Distance Oracle

Kirsten Hildrum
(Professor Satish Rao)

Given a set of points, S, in a metric space and query point q, the goal is to find the point in S closest to q. Ideally, the data structure to do this only relies on an oracle that gives the distance between any two points, and not on any other detail of the metric space.

In some metric spaces, this seems difficult. Consider, for example, a metric space and a query point such that all points in S are at a distance one from each other, and all but one are at distance q from S. Finding the one point closest to q will probably require querying the distance from q to every point in S. In other metric spaces, it is possible to do this with a logarithmic number of queries (see [1] or [2]).

Following up on [1] and [2], we have a result showing that this can be done in constant space and logarithmic time for unchanging sets S and hope to argue that a similar data structure with expected constant space works for dynamic sets S.

A more general goal is to characterize the metric spaces for which finding the nearest point requires a sublinear number of queries and develop algorithms for those metric spaces.

K. Hildrum, J. D. Kubiatowicz, S. Rao, and B. Y. Zhao, "Distributed Object Location in a Dynamic Network," Proc. ACM Symp. Parallel Algorithms and Architectures, Winnepeg, Canada, August 2002.
D. Karger and M. Ruhl, "Finding Nearest Neighbors in Growth-Restricted Metrics," Proc. ACM Symp. Theory of Computing, Montreal, Canada, May 2002.

More information ( or

Send mail to the author : (

Edit this abstract