Approximate Nearest Neighbor: Towards Removing the Curse of Dimensionality
Received: August 20, 2010
Published: July 16, 2012
Published: July 16, 2012
Keywords: Approximate nearest neighbor, high dimensions, locality-sensitive hashing
Categories: algorithms, data structures, nearest neighbor, approximation algorithms, high dimension, hashing, locality-sensitive hashing, norm, metric embedding, Voronoi decomposition, minimum spanning tree, special issue, Motwani special issue
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.