Home Bookmarks Papers Blog

Approximate Nearest Neighbor: Towards Removing the Curse of Dimensionality

Sariel Har-Peled, Piotr Indyk, and Rajeev Motwani.


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.
PDF.
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:
  1. Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality, by P. Indyk and R. Motwani. Appeared in STOC 1998.
  2. A Replacement for Voronoi Diagrams of Near Linear Size, by S. Har-Peled. Appeared in FOCS 2001.

Last modified: Thu Jan 12 18:48:59 CST 2012