Scalable Nearest Neighbor Algorithms for High Dimensional Data

By Marius Muja, David G. Lowe. 2014

1,508 citations recorded by the source corpus.

Subfields: Computer Vision and Pattern Recognition, 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 Computer Vision and Pattern Recognition

In Information Retrieval & Search

In Signal Processing

Citations in the corpus

Large Memory Layers with Product Keys (2019, background): “Their approach relies on an external indexing structure [30], which is approximate and needs to be re-learned regularly while training the neural network to avoid a catastrophic drift.”
Fast Patch-based Style Transfer of Arbitrary Style (2016, methodology): “It may be desirable to perform clustering on the style patches to reduce the number of patches, or use alternative implementations such as fast approximate nearest neighbour search methods [12, 28].”
Efficient Global 2D-3D Matching for Camera Localization in a Large-Scale 3D Map (2017, methodology): “Next, for every 2D feature we find a set of tentative matches from the 3D graph nodes, by comparing their descriptor similarity via an efficient vocabulary-tree search mechanism [36].”
Secrets of GrabCut and Kernel K-Means (2015, methodology): “To handle features inR27 we used sparse histograms for GrabCut and approximate nearest neighbors [24] for aKKM.”
Big IoT Data Analytics: Architecture, Opportunities, and Open Research Challenges (2017, methodology): “Using cases further improve the KNN algorithm for application in anomaly detection [53], high-dimensional data [54], and scientiﬁc experiments [55].”
Learning and Calibrating Per-Location Classifiers for Visual Place Recognition (2013, methodology): “2011) combined with sub-linear approximate nearest neighbor search (Muja and Lowe 2014).”
From Neural Re-Ranking to Neural Ranking: Learning a Sparse Representation for Inverted Indexing (2018, neutral): “However, the exact brute-force k-NN is practically infeasible and an approximation of k-NN [35] is used to be able to make use of dense representation in the ranking scenario [6].”
Pose Estimation for Augmented Reality: A Hands-On Survey (2016, neutral): “Since this is not a generic problem, various efficient solutions for this problem have been already proposed [85].”
Projection onto the Manifold of Elongated Structures for Accurate Extraction (2015, methodology): “For Nearest Neighbor search we use the FLANN library [31].”
Accelerating Large-Scale Inference with Anisotropic Vector Quantization (2019, methodology): “Tree search methods such as (Muja & Lowe, 2014; Dasgupta & Freund, 2008) partition the space recursively, forming a tree.”
SIFT Meets CNN: A Decade Survey of Instance Retrieval (2016, methodology): “Due to the high dimensionality of the VLAD/FV embeddings, efficient compression and ANN search methods have been employed [61], [62].”
Milvus: A Purpose-Built Vector Data Management System (2021, background): “Prior works on approximate search can be roughly classified in four categories: LSH-based [23, 23, 24, 32, 40, 44, 45, 48, 73], tree-based [17, 46, 54, 57], graph-based [20, 43, 49, 61, 72], and quantization-based [3, 6, 22, 27, 33, 35].”
Deep Reinforcement Learning in Large Discrete Action Spaces (2015, methodology): “We see that even our most lossy FLANN setting with no re-ranking converges to an optimal policy in this task.”
From Neural Re-Ranking to Neural Ranking: Learning a Sparse Representation for Inverted Indexing (2018, neutral): “k-NN is practically infeasible and an approximation of k-NN [35] is used to be able to make use of dense representation in the ranking scenario [6].”
The Faiss Library (2024, neutral): “One of the most popular approaches in the industry is to employ Locality Sensitive Hashing (LSH) as a way to compress embeddings into compact codes.”