We present two algorithms for the approximate nearest neighbor
problem in high dimensional spaces. For data sets of size n
living in Rd, 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.
This paper is to appear in a
special issue of ToC in the memory of Rajeev Motwani, see here.
This paper is based on the conference papers:
Approximate Nearest Neighbors: Towards Removing
the Curse of Dimensionality, by P. Indyk and
R. Motwani. Appeared in STOC 1998.