**
Efficient Search for Approximate Nearest Neighbor in High
Dimensional Spaces
**

*
Eyal Kushilevitz, Rafail Ostrovsky, Yuval Rabani
*

**
Abstract:
**

We address the problem of designing data structures that
allow efficient search for approximate nearest neighbors.
More specifically, given a database consisting of a set
of vectors in some high dimensional Euclidean space, we
want to construct a space-efficient data structure that
would allow us to search, given a query vector, for the
closest or nearly closest vector in the database. We also
address this problem when distances are measured by the
L_{1 }norm, and in the Hamming cube. Significantly improving and
extending recent results of Kleinberg, we construct data
structures whose size is polynomial in the size of the
database, and search algorithms that run in time
nearly linear or nearly quadratic in the dimension
(depending on the case; the extra factors are
polylogarithmic in the size of the database).

**comment:**
Journal version appeared in SIAM J. Comput. 30(2): 457-474 (2000).
Preliminary version in
Proceedings of
The 30's ACM Symposium on Theory of Computing (STOC-98)

Fetch PostScript file of the paper Fetch PDF file of the paper

Back to Publications List |