AMS-DIMACS Book Chapter (to appear) and Proc. 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) | 2000 |

**Abstract: **
Our work gives a positive result for nearest neighbor search
in high dimensions. It establishes that radius-limited search
is, under particular circumstances, free of the {\em curse of
dimensionality}. It further illuminates the nature of the
curse, and may therefore someday contribute to improved general
purpose algorithms for high dimensions and for general metric
spaces.

We consider the problem of nearest neighbor search in the Euclidean hypercube $[-1,+1]^d$ with uniform distributions, and the additional natural assumption that the nearest neighbor is located within a constant fraction $R$ of the maximum interpoint distance in this space, i.e. within distance $2 R \sqrt{d}$ of the query.

We introduce the idea of {\em aggressive pruning} and give a family of practical algorithms, an idealized analysis, and describe experiments. Our main result is that search complexity measured in terms of $d$-dimensional inner product operations, is i) strongly sublinear with respect to the data set size $n$ for moderate $R$, ii) asymptotically, and as a practical matter, independent of dimension.

Given a random data set, a random query within distance $2 R \sqrt{d}$ of some database element, and a randomly constructed data structure, the search succeeds with a specified probability, which is a parameter of the search algorithm. On average a search performs $\approx n^\rho$ distance computations where $n$ is the number of of points in the database, and $\rho < 1$ is calculated in our analysis. Linear and near-linear space structures are described, and our algorithms and analysis are free of large hidden constants, i.e. the algorithms perform far less work than exhaustive search -- both in theory and practice.

**Keywords: **
Nearest neighbor search,
Vantage point tree (vp-tree),
Kd-tree,
Computational geometry,
Metric space.

- View the complete paper (converted to HTML)
- The complete paper (PDF)
- The complete paper (PostScript)
- BibTex entry
- My homepage ( Peter N. Yianilos )
- See also: