An Investigation of Practical Approximate Nearest Neighbor Algorithms

By Ting Liu, Andrew W. Moore, Alexander G. Gray, Ke Yang. 2004

513 citations recorded by the source corpus.

Subfields: Information Retrieval & Search

How researchers see this paper

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

In Information Retrieval & Search

Citations in the corpus

Maximum inner-product search using cone trees (2012, methodology): “Ball trees are widely used for the task of nearest neighbor search and are known to be fairly scalable to moderately high dimensions [28, 26].”
Deep Neural Networks for YouTube Recommendations (2016, background): “Since calibrated likelihoods from the softmax output layer are not needed at serving time, the scoring problem reduces to a nearest neighbor search in the dot product space for which general purpose libraries can be used [12].”
Barnes-Hut-SNE (2013, methodology): “Motivated by their strong performance reported in earlier work in [17], we opt to use metric trees to approximate the similarities of the input objects in our algorithm.”
Parallel Spectral Clustering in Distributed Systems (2011, methodology): “For example, it is possible that one only approximately finds the t nearest neighbors using techniques such as spill-tree [26].”
Adaptive Blocking: Learning to Scale Up Record Linkage (2006, methodology): “A number of methods for fast nearest-neighbor searching [16, 22] are closely related to the adaptive blocking problem, however these techniques typically rely on strong metric assumptions in the data space, while our approach works with arbitrary blocking predicates.”
Efficient indexing for large scale visual search (2009, background): “These characteristics bring difficulties to existing high-dimensional indexing techniques, e.g. Locality Sensitive Hashing (LSH) [1] and KD-tree[13].”
Cross-domain Recommendation via Deep Domain Adaptation (2018, methodology): “[6], we only have to perform the neighbourhood search in the dot product space of the learned item features and user features [24], and thus the computation of the somax function can be avoided.”
Fast Neighborhood Graph Search Using Cartesian Concatenation (2013, methodology): “We compare our approach with stateof-the-art algorithms, including iterative neighborhood graph search [38], original neighborhood graph search (AryaM93) [2], trinary projection (TP) trees [20], vantage point (VP) tree [46], Spill trees [24], FLANN [27], and inverted multi-index [4].”
Pose tracking from natural features on mobile phones (2008, background): “A Spill Tree [ 14 ] is a variant of a k-d Tree that uses an overlapping splitting area.”
In-Batch Negatives for Knowledge Distillation with Tightly-Coupled Teachers for Dense Retrieval (2021, methodology): “When retrieving texts in response to a given query, computationally expensive transformer inference is replaced by much faster approximate nearest neighbor (ANN) search (Liu et al., 2004; Malkov and Yashunin, 2020).”
Distilling Dense Representations for Ranking using Tightly-Coupled Teachers (2020, methodology): “Thus, despite its aspirations to single-stage ANN search, end-to-end retrieval with ColBERT still requires multi-stage retrieval.”
Real-Time Detection and Tracking for Augmented Reality on Mobile Phones (2010, background): “We discovered that multiple trees with randomized dimensions for pivoting allow for a highly robust voting process, similarly to the randomized trees [10] : instead of using a single tree, we combine a number of Spill Trees into a Spill Forest.”
FANNG: Fast Approximate Nearest Neighbour Graphs (2016, background): “Algorithm 2 has the favourable property of creating graphs of relatively low degree (number of outgoing edges per vertex).”
Approximate Nearest Subspace Search with Applications to Pattern Recognition (2007, methodology): “As such, it has attracted considerable attention in recent years, and a number of ef-ﬁcient algorithms for approximate nearest neighbor (ANN) search have been proposed (e.g., [2, 8, 11, 13]).”
Random projection trees and low dimensional manifolds (2008, background): “Finally, (4) holds with probability ≥ 1−δ2 by Corollary 8.”
Query-driven iterated neighborhood graph search for large scale indexing (2012, unknown): “P ′ ← Perturbation( R ∗ , q, T, history ) R ∗′ ← LocalNGSearch( P ′ , G, history )”