Volume 8 (2012) Article 14 pp. 321-350
Special Issue in Honor of Rajeev Motwani
Approximate Nearest Neighbor: Towards Removing the Curse of Dimensionality
Received: August 20, 2010
Published: July 16, 2012
Download article from ToC site:
[PDF (627K)]    [PS (1751K)]    [PS.GZ (617K)]
[Source ZIP]
Keywords: Approximate nearest neighbor, high dimensions, locality-sensitive hashing
ACM Classification: F.2.2
AMS Classification: 68W25

Abstract: [Plain Text Version]

We present two algorithms for the approximate nearest neighbor problem in high-dimensional spaces. For data sets of size $n$ living in ${\mathbb R}^d$, the algorithms require space that is only polynomial in $n$ and $d$, while achieving query times that are sub-linear in $n$ and polynomial in $d$. We also show applications to other high-dimensional geometric problems, such as the approximate minimum spanning tree.

The article is based on the material from the authors' STOC'98 and FOCS'01 papers. It unifies, generalizes, and simplifies the results from those papers.