## 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.

- [1]
- 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.
- [2]
- D. Karger and M. Ruhl, "Finding Nearest Neighbors in Growth-Restricted Metrics,"
*Proc. ACM Symp. Theory of Computing,* Montreal, Canada, May
2002.

More information (http://www.cs.berkeley.edu/~hildrum/neighbors.html) or

Send mail to the author : (hildrum@eecs.berkeley.edu)

Edit this abstract