Approximate Nearest Neighbor: Towards Removing the Curse of Dimensionality

By Sariel Har-Peled, Piotr Indyk, Rajeev Motwani. 2012

4,956 citations recorded by the source corpus.

We present two algorithms for the approximate nearest neighbor problem in high dimensional spaces. For data sets of size n living in IR 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.

Subfields: Computational Theory and Mathematics, Computer Graphics and Computer-Aided Design, Information Retrieval & Search, Signal Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

  1. David P. Woodruff
  2. Ping Li
  3. Anshumali Shrivastava
  4. Jayadev Acharya
  5. Ravi Kumar
  6. Jelani Nelson
  7. Manas A. Pathak
  8. Uri Stemmer

In Computer Graphics and Computer-Aided Design

  1. Matthias Nießner
  2. Ping Li
  3. Angela Dai
  4. Anshumali Shrivastava
  5. Jiajun Wu
  6. Alexander Ponomarenko
  7. Yury Malkov
  8. Kaiming He

In Information Retrieval & Search

  1. Ping Li
  2. Anshumali Shrivastava
  3. Jimmy J. Lin
  4. Jingdong Wang
  5. Sanjiv Kumar
  6. Jingkuan Song
  7. Heng Tao Shen
  8. Herv'e J'egou

In Signal Processing

  1. Karen Livescu
  2. Ping Li
  3. Herman Kamper
  4. James R. Glass
  5. Anshumali Shrivastava
  6. Antonio Torralba
  7. Aren Jansen
  8. Shane Settle

Citations in the corpus