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
- David P. Woodruff
- Ping Li
- Anshumali Shrivastava
- Jayadev Acharya
- Ravi Kumar
- Jelani Nelson
- Manas A. Pathak
- Uri Stemmer
In Computer Graphics and Computer-Aided Design
- Matthias Nießner
- Ping Li
- Angela Dai
- Anshumali Shrivastava
- Jiajun Wu
- Alexander Ponomarenko
- Yury Malkov
- Kaiming He
In Information Retrieval & Search
- Ping Li
- Anshumali Shrivastava
- Jimmy J. Lin
- Jingdong Wang
- Sanjiv Kumar
- Jingkuan Song
- Heng Tao Shen
- Herv'e J'egou
In Signal Processing
- Karen Livescu
- Ping Li
- Herman Kamper
- James R. Glass
- Anshumali Shrivastava
- Antonio Torralba
- Aren Jansen
- Shane Settle
Citations in the corpus
- Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs (2016, neutral): “(LSH) [8], [9] and product quantization (PQ) [10], [11], [12], [13], [14], [15], [16], [17].”
- Asymmetric LSH (ALSH) for Sublinear Time Maximum Inner Product Search (MIPS) (2014, methodology): “The theory [11] behind LSH still works if we use hash function h1 for preprocessing x ∈ S and a different hash function h2 for querying, as long as the probability of the event {h2(q) = h1(x)} increases with Sim(q, x), and there exist p1 and p2 with the required property.”
- Pretrained Transformers for Text Ranking: BERT and Beyond (2020, methodology): “ximation in distance in 1 ˚usually has no measurable impact on end-user perceptions of quality. The earliest solutions to approximate nearest neighbor search were based on locality-sensitive hashing [Indyk and Motwani, 1998, Gionis et al., 1999, Bawa et al., 2005], but proximity graph methods method”
- The People's Speech: A Large-Scale Diverse English Speech Recognition Dataset for Commercial Usage (2021, background): “We think locality-sensitive hashing [21] of ivectors [24], xvectors [30], or other text-independent speaker embedding is a promising approach to find speaker overlap in utterances.”
- The Stack: 3 TB of permissively licensed source code (2022, methodology): “Next, we compute the MinHash with 256 permutations of all documents, and use Locality Sensitive Hashing (Har-Peled et al., 2012) to find clusters of duplicates.”
- Sparse, Dense, and Attentional Representations for Text Retrieval (2020, background): “Approximate retrieval (Indyk and Motwani, 1998; Har-Peled et al., 2012) is often necessary in practice.”
- Learning Sight from Sound: Ambient Sound Provides Supervision for Visual Learning (2017, positive): “Binary coding model For the other variation of our model (which we call the Binary model), we use a binary coding scheme (Indyk and Motwani 1998; Salakhutdinov and Hin-ton 2009; Weiss et al 2009) equivalent to a multi-label clas-sification problem.”
- Adversarial Examples Detection in Deep Networks with Convolutional Filter Statistics (2016, background): “extrapolation in a 4, 000dimensional or 40, 000-dimensional space? It looks like almost everything is extrapolation since the data is inherently sparse in such a high-dimensional space [9, 6], a phenomenon well-known as the curse of dimensionality.”
- Relational autoencoder for feature extraction (2017, background): “This is because although machine learning models should, theoretically, be able to work on any number of features, high-dimensional datasets always bring about a series of problems including over-fitting, high-computational complexity and overly complicated models, which gives rise to a well known i”
- Random Feature Maps for Dot Product Kernels (2012, methodology): “Their contribution is reminiscent of Indyk and Motwani (1998) who perform low distortion embeddings (by invoking the JohnsonLindenstrauss Lemma) in order to overcome the curse of dimensionality for the nearest neighbor problem.”
- RUPEE: A fast and accurate purely geometric protein structure search (2018, background): “For this task, min-hashing [29] and 169 locality sensitive hashing (LSH) [30] can be combined to reduce this to subquadratic 170 time.”
- Shape Completion Using 3D-Encoder-Predictor CNNs and Shape Synthesis (2016, methodology): “To synthesize level l of P 0 , we compute the volumetric patch feature for each voxel v and use an approximate nearest neighbor search [12] to find the most similar voxel w of the neighbors, and update the value of P 0 ( v ) with that of N lx ( w ) .”
- Deep Fried Convnets (2014, background): “We search the standard deviation of the random Gaussian matrix used in Fastfood within the set {0.001, 0.005, 0.01, 0.05} and vary the number of features that Fastfood uses among {1024, 2048}.”
- Learning to Remember Rare Events (2017, background): “LSH is a hashing scheme so that near neighbors get similar hashes (Indyk & Motwani, 1998; Andoni & Indyk, 2006).”
- Ambient Sound Provides Supervision for Visual Learning (2016, methodology): “Binary coding model For the other variation of our model (which we call the Binary model), we use a binary coding scheme [14,31,36] equivalent to a multi-label classification problem.”
- ProtTrans: Towards Cracking the Language of Life’s Code Through Self-Supervised Deep Learning and High Performance Computing (2020, methodology): “data parallelism: Were the large models introduced here still too small to capture all data? Unfortunately, this brings up training efficiency as recently investigated by sparse Transformers [72] or attention optimized with locality-sensitive hashing (LSH) [73] as introduced recently by the Reformer”
- Privacy via the Johnson-Lindenstrauss Transform (2012, methodology): “This transform has become a fundamental tool in dimensionality reduction and similarity search in high dimensions, and computer science literature [1,17] has proposed several constructions for P .”
- End-to-End Retrieval in Continuous Space (2018, background): “While the problem of nearest neighbor search (Indyk and Motwani, 1998; Gionis et al., 1999) is central to continuous retrieval, we’re glossing over it here for two reasons.”
- Barnes-Hut-SNE (2013, background): “Most of these studies focus on speeding up nearest-neighbor searches using space-partitioning (metric) trees ( e.g. , B-trees [2], cover trees [3], and vantage-point trees [31]) or using locality sensitive hashing approaches ( e.g. , [12, 29]).”