Volume 8 (2012) Article 14 pp. 321-350
Special Issue in Honor of Rajeev Motwani
Approximate Nearest Neighbor: Towards Removing the Curse of Dimensionality
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.