An optimal algorithm for approximate nearest neighbor searching fixed dimensions

By Sunil Arya, David M. Mount, Nathan S. Netanyahu, Ruth Silverman, Angela Y. Wu. 1998

How researchers see this paper

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

Citations in the corpus

Approximate Nearest Neighbor: Towards Removing the Curse of Dimensionality (2012, background): “Another line of research [AMN + 94] resulted in an algorithm with linear space O ( dn ) but query time ( d/(cid:15) ) O ( d ) · log n .”
Scaling Memory-Augmented Neural Networks with Sparse Reads and Writes (2016, neutral): “Maintaining and querying the ANN index represents the most expensive part of the network, which is reasonable as content-based addressing is inherently expensive [14, 1].”
Evaluation of image-based modeling and laser scanning accuracy for emerging automated performance monitoring techniques (2011, methodology): “Since the number of features is large, a k–d tree matching scheme [33] is used to reduce the computation cost for matching.”
LOCI: fast outlier detection using the local correlation integral (2003, methodology): “Although some algorithms exist for approximate nearest neighbor search [3, 7, 11], it seems unlikely that these can be used to achieve O(kN) time with LOF.”
The Fast Johnson--Lindenstrauss Transform and Approximate Nearest Neighbors (2009, background): “There is abundant literature on (approximate) nearest neighbor searching [5, 6, 7, 9, 12, 13, 14, 18, 24, 29, 23, 27, 32, 33, 42, 43, 37].”
Fitting a $C^m$-Smooth Function to Data II (2009, methodology): “The following result is contained in [1].”
Scale-invariant heat kernel signatures for non-rigid shape recognition (2010, methodology): “We used the approximate nearest neighbor algorithm [1] as implemented in the ANN tool- box.”
Partial and approximate symmetry detection for 3D geometry (2006, methodology): “We perform mean-shift clustering using the method proposed in [Arya et al. 1998] to efficiently compute neighborhoods in 7D transformation space.”
Feature Extraction From Point Clouds (2001, methodology): “For our purposes we could compute a sufficient approximation to the Riemannian graph with the approximate nearest neighbor library ANN [4].”