Approximate nearest neighbor queries in fixed dimensions

By Sunil Arya, David M. Mount. 1993

How researchers see this paper

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

In Algorithms & Complexity

Citations in the corpus

Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs (2016, methodology): “Proximity graph K-ANNS algorithms [10], [18], [19], [20], [21], [22], [23], [24], [25],”
Approximate Nearest Neighbor: Towards Removing the Curse of Dimensionality (2012, background): “One of the earliest works on this topic is [9] (improved upon in [22] and [19]), who gave an algorithm with query time 1/εO(d) · logn and space 1/εO(d) ·n.”
Explicit Approximations of the Gaussian Kernel (2011, methodology): “The dot-dashed line indicates the performance of a 1-NN classiﬁer, trained using the ANN library [Arya and Mount, 1993, Mount and Arya, 2006, Bagon, 2009].”
Worldwide Pose Estimation Using 3D Point Clouds (2012, methodology): “Matching an image feature to a 3D point amounts to retrieving the feature’s nearest neighbor in the 128-D SIFT space, among the set of points P in the 3D model (using approximate nearest neighbor techniques such as [26]), subject to a ratio test.”
Video Inpainting of Complex Scenes (2014, methodology): “We obtain a speedup of 20-50 times over the method of [4].”
Approximate Nearest Neighbor Search Small World Approach (2011, methodology): “For example, Arya and Mount proposed methods with search complexity , but preprocessing requires and algorithm was applicable only to data from E [18].”
Evaluation of local detectors and descriptors for fast feature matching (2012, methodology): “Widely used algorithms in computer vision applications are kd-trees [1, 9, 13] and hashing methods [16].”
Fast k-Nearest Neighbour Search via Prioritized DCI (2017, methodology): “Methods based on tree-based space partitioning (Arya et al., 1998) and local search (Arya & Mount, 1993) have been developed; like many exact algorithms, their query times also scale exponentially in the ambient dimensionality.”
Efficient Graph-Based Image Segmentation (2004, unknown): “We use the ANN algorithm (Arya and Mount, 1993) to find the nearest neighbors for each point.”
Deja Vu: Contextual Sparsity for Efficient LLMs at Inference Time (2023, methodology): “The following definition of approximate nearest neighbor search is very standard in literature (Arya & Mount, 1993; Indyk & Motwani, 1998a; Datar et al., 2004; Andoni et al., 2014; 2015; Andoni & Razenshteyn, 2015; Indyk & Wagner, 2018; Andoni et al., 2017; 2018; Dong et al., 2019; Chen et al.,…”
Landmark classification in large-scale image collections (2009, methodology): “To make kmeans clustering tractable on this quantity of data we use the approximate nearest neighbor (ANN) technique of [1] to efficiently assign points to cluster centers.”
SfM with MRFs: Discrete-Continuous Optimization for Large-Scale Structure from Motion (2013, unknown): “For each such candidate image pair, we compute detailed SIFT matches [36] using approximate nearest neighbors [38].”
Approximate nearest neighbor algorithm based on navigable small world graphs (2014, background): “Note that there is a distinction from the ANN problem defined in the works [19–23] where it is expressed in terms of ε-neighborhood.”
DBSCAN Revisited, Revisited (2017, methodology): “When runtime is crucial, the inaccuracies of approximations may be well within the tolerance limits of the application, and approximative similarity search using k-d-trees [5], or locality sensitive hashing (LSH) [26] are as old as DBSCAN, and have successfully been combined with DBSCAN.”
Interactive image completion with perspective correction (2006, unknown): “Furthermore the fast feedback of our system did not make the usage of methods necessary where nearest neighbors search is approximated [1, 10].”
Distinctive Image Features from Scale-Invariant Keypoints (2004, background): “This priority search order was first examined by Arya and Mount (1993), and they provide further study of its computational properties in (Aryaet al., 1998).”
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].”