##
Finding Nearest Neighbors in Growth-restricted Metrics

**
David R. Karger and Matthias Ruhl
**
*
ACM Symposium on Theory of Computing (STOC '02)*

Montréal, May 2002

[Postscript, 165KB]

[PDF, 146KB]

### Abstract

Most research on nearest neighbor algorithms in the literature has
been focused on the Euclidean case. In many practical search
problems however, the underlying metric is non-Euclidean. Nearest
neighbor algorithms for general metric spaces are quite weak, which
motivates a search for other classes of metric spaces that can be
tractably searched.

In this paper, we develop an efficient dynamic data structure for
nearest neighbor queries in *growth-constrained* metrics.
These metrics satisfy the property that for any point *q* and
distance *d* the number of points within distance 2*d* of
*q* is at most a constant factor larger than the number of
points within distance *d*. Spaces of this kind may occur in
networking applications, such as the Internet or Peer-to-peer
networks, and vector quantization applications, where feature
vectors fall into low-dimensional manifolds within high-dimensional
vector spaces.

Back to publications