The Inverted Multi-Index

By Artem Babenko, Victor S. Lempitsky. 2012

510 citations recorded by the source corpus.

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

In Computer Vision and Pattern Recognition

In Information Retrieval & Search

Citations in the corpus

Large Memory Layers with Product Keys (2019, background): “This can be done in O ( k 2 × d q ) operations (in practice, this could be done in O ( k log k ) scalar operations with a priority list [2], but this choice is less compliant with GPU architectures).”
Billion-Scale Similarity Search with GPUs (2017, background): “For instance, the inverted multi-index [4], useful for high-speed/low-quality operating points, depends on a complicated “multi-sequence” algorithm.”
Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs (2016, methodology): “To compare the performance of Hierarchical NSW against PQ algorithms we used the facebook Faiss library(8) as the baseline (a new library with state-of-the-art PQ algorithms [12], [15] implementations, released after the current manuscript was submitted) compiled with the”
Scalable Nearest Neighbor Algorithms for High Dimensional Data (2014, methodology): “Dimensionality reduction has been used in the literature with good results ([7], [27], [28], [32], [57]), however even with dimensionality reduction it can be challenging to fit the data in the memory of a single machine for very large data sets.”
Get Out of My Lab: Large-scale, Real-Time Visual-Inertial Localization (2015, methodology): “the use of high-quality kNN algorithms for real-valued vectors [15, 38, 40, 5] and thus avoids the problems of kNN searches in binary spaces [50].”
Human Pose Estimation Using a Joint Pixel-wise and Part-wise Formulation (2013, background): “This can be solved [2] in O(PcK logK), where Pc is the number of children of the parent.”
Locally Optimized Product Quantization for Approximate Nearest Neighbor Search (2014, methodology): “We compare against three of the methods discussed in section 4.3, all using a single index on a coarse quantizer and PQ-encoded residuals, with any optimization being global.”
Improving Bilayer Product Quantization for Billion-Scale Approximate Nearest Neighbors in High Dimensions (2014, methodology): “For dataset compression, [1] followed the IVFADC system and used product quantization with global codebooks shared across all cells in order to encode the displacements of the vectors from centroids (this system is referred to as MultiD-ADC ).”
Cartesian K-Means (2013, methodology): “Search can be sped up significantly; using a coarse initial quantization and an inverted file structure for AD and AH , as suggested by [7, 1], and using the multi-index hashing method of [13] for Hamming distance.”
Cache locality is not enough: High-Performance Nearest Neighbor Search with Product Quantization Fast Scan (2015, unknown): “Given a database vector p , we use the 4 least significant bits of p [0] · · · p [3] to index values in S 0 , · · · , S 3 and the 4 most signiﬁcant bits of p [4] · · · p [7] to index values in S 4 , · · · , S 7 .”
Accelerating Large-Scale Inference with Anisotropic Vector Quantization (2019, methodology): “the cost of constructing index structures in addition to storing original vectors. Thus they are usually used in combination with linear search quantization methods, in ways similar to inverted index [7, 29, 30]. 3 Problem Formulation Common quantization techniques focus on minimizing the reconstruc”
Embedding-based Retrieval in Facebook Search (2020, methodology): “It is useful to compare between IMI [11] and IVF [15] algorithms.”
Approximate Nearest Neighbor Search on High Dimensional Data - Experiments, Analyses, and Improvement (v1.0) (2016, unknown): “Given a query vector q = [q((1)), q((2))], the search algorithm in [6] first retrieves L closest sub-codedwords {Cij }i∈{ 1,2 },j∈{ 1,2,.”
Fast Nearest Neighbor Search in the Hamming Space (2016, methodology): “1: b ← nearest bridge vector to q through the Multi-sequence algorithm in [9] 2: PQ ← {b} 3: L ← 0 4: while L < Lmax do 5: if b is top of PQ then 6: call ExtractOnDemand(b,PQ) 7: else 8: t ← top of PQ 9: examine and push neighbor points of t in neighborhood graph G to PQ 10: L ← L + number of new po”
Web-Scale Image Clustering Revisited (2015, methodology): “However, search is based on ideas extended from the inverted multi-index [4].”
Optimized Product Quantization (2014, methodology): “The inverted multi-index method [2] uses a product quantizer for inverted indexing.”
Fast Neighborhood Graph Search Using Cartesian Concatenation (2013, methodology): “, [4, 18, 28, 34, 39], and is composed of a set of inverted lists, each of which corresponds to a cluster of reference vectors.”
KNN-Diffusion: Image Generation via Large-Scale Retrieval (2022, background): “As in Babenko & Lempitsky (2014), we deﬁne Voronoi cells in the d -dimensional space (where d = 512 is the CLIP embedding dimensional space), s.t each database vector falls in one of the cells.”
Efficient Indexing of Billion-Scale Datasets of Deep Descriptors (2016, methodology): “After short-list extraction the (G)NO-IMI performs reranking of candidate points in the same manner as it was proposed in [2, 14].”
Multiscale Quantization for Fast Similarity Search (2017, methodology): “Compared to IVFADC [20], which uses plain PQ with coarse quantizers, our end-to-end trained MSQ reduces quantization error by 15-20% on SIFT1M, and 20-25% on DEEP10M, which is a substantial reduction.”