Locally Optimized Product Quantization for Approximate Nearest Neighbor Search

By Yannis Kalantidis, Yannis Avrithis. 2014

315 citations recorded by the source corpus.

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

In Media Technology

In Information Retrieval & Search

Citations in the corpus

Billion-Scale Similarity Search with GPUs (2017, background): “Many other meth-ods, like LOPQ and the Polysemous codes [27, 16] are too complex to be implemented eﬃciently on GPUs.”
Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs (2016, background): “(LSH) [8], [9] and product quantization (PQ) [10], [11], [12], [13], [14], [15], [16], [17].”
Quantization based Fast Inner Product Search (2015, neutral): “In this paper, we take a quantization based view of the MIPS problem and show that it leads to even better accuracy under both ﬁxed space or ﬁxed time budget on a variety of real world tasks.”
GPU accelerated t-distributed stochastic neighbor embedding (2019, background): “We can see that the optimized tsnecuda, which makes use of the ability to switch dynamically between basic inverted files, and IVFADC for nearest neighbor computation outperforms the other two implementations of tsnecuda as the dimensions grow.”
Hashing for Similarity Search: A Survey (2014, methodology): “Locally optimized product quantization [58] applies Cartesian k-means to the search algorithm with the inverted index, where there is a quantizer for each inverted list.”
Sketch-based manga retrieval using manga109 dataset (2015, methodology): “If much faster searches are required, we can employ more sophisticated ANN data structures [68], [69].”
Efficient Indexing of Billion-Scale Datasets of Deep Descriptors (2016, methodology): “Currently, Multi-LOPQ system provides the highest recall on the SIFT1B dataset.”
Cache locality is not enough: High-Performance Nearest Neighbor Search with Product Quantization Fast Scan (2015, unknown): “Another part of publications focuses on optimizing the learning of sub-quantizers to increase recall [21, 10, 15], which is orthogonal to our work.”
FANNG: Fast Approximate Nearest Neighbour Graphs (2016, background): “This means that if the graph has an edge from p1 to p2, then it is not necessary for it to have an edge from p1 to any vertex p3 that is closer to p2 than p1.”
The Inverted Multi-Index (2012, background): “Secondly, in Kalantidis and Avrithis [30] and in our report [31], the idea of local codebooks that describe the distribution of the points within each cell of a multi-index has been demonstrated to bring further boost to search accuracy.”
Multiscale Quantization for Fast Similarity Search (2017, methodology): “Researchers have proposed multiple ways to estimate such a rotation matrix: Norouzi and Fleet [30] use ITQ [13] style alternating quantization; Optimized PQ [11] also applied a simple strategy to minimize the quantization error; Locally Optimized PQ [22] learns a separate R for each coarse partition”
A Survey on Learning to Hash (2016, methodology): “Locally optimized product quantization [62] applies optimized production quantization to the search algorithm with the inverted index, where there is a quantizer for each”
Efficient Large-Scale Approximate Nearest Neighbor Search on the GPU (2016, methodology): “Note that the reported time of [11] excludes all intensive operations like the multiplicamethod avg.”
Large-Scale Image Retrieval with Attentive Deep Local Features (2016, methodology): “To reduce encoding errors, a KD-tree is used to partition each Voronoi cell, and a Locally Optimized Product Quantizer [20] is employed for each subtree with fewer than 30K features.”
Deep Learning for Intelligent Transportation Systems: A Survey of Emerging Trends (2020, methodology): “is to train a deep neural network to summarize the content of images, and then use tools such as Locally Optimized Product Quantization (LOPQ) [48] to index a database.”
Polysemous Codes (2016, background): “The limitation imposed by this memory bottleneck has led to two-stage approaches [27,28,2,32], in which the feature space is ﬁrst partitioned through hashing or clustering.”
Sparse composite quantization (2015, background): “There are other attempts to improve product quantization in the other ways, such as distance-encoded product quantization [10] and locally optimized product quantization [15], which can also be combined with our approach in the same way.”