Theory of Computing
-------------------
Title : Approximate Nearest Neighbor: Towards Removing the Curse of Dimensionality
Authors : Sariel Har-Peled, Piotr Indyk, and Rajeev Motwani
Volume : 8
Number : 14
Pages : 321-350
URL : http://www.theoryofcomputing.org/articles/v008a014
Abstract
--------
We present two algorithms for the approximate nearest neighbor
problem in high-dimensional spaces. For data sets of size n
living in 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.