Searching in one billion vectors: Re-rank with source coding

By Herv'e J'egou, Romain Tavenard, Matthijs Douze, Laurent Amsaleg. 2011

384 citations recorded by the source corpus.

Recent indexing techniques inspired by source coding have been shown successful to index billions of high-dimensional vectors in memory. In this paper, we propose an approach that re-ranks the neighbor hypotheses obtained by these compressed-domain indexing methods. In contrast to the usual post-verification scheme, which performs exact distance calculation on the short-list of hypotheses, the estimated distances are refined based on short quantization codes, to avoid reading the full vectors from disk. We have released a new public dataset of one billion 128-dimensional vectors and proposed an experimental setup to evaluate high dimensional indexing algorithms on a realistic scale. Experiments show that our method accurately and efficiently re-ranks the neighbor hypotheses using little memory compared to the full vectors representation.

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

In Information Retrieval & Search

Citations in the corpus

Billion-Scale Similarity Search with GPUs (2017, methodology): “ and R@100=0.86 in 0.02ms per query on a Titan X. For the same time budget, our implementation obtains R@1=0.80 and R@100=0.95. SIFT1B. We compare again with Wieschollek et al., on the Sift1B dataset [26] of 1 billion SIFT image features at n q = 104. We compare the search performance in terms of sa”
Large Scale Nearest Neighbors Search Based on Neighborhood Graph (2013, background): “However, in [15], their search quality is measured by the recall@r measure, i.”
Polysemous Codes (2016, methodology): “B IGANN is a large-scale benchmark [30] widely used for ANN search, also made of SIFT descriptors.”
K-Means Hashing: An Affinity-Preserving Quantization Method for Learning Binary Compact Codes (2013, methodology): “Following another common criterion in PQ methods [11, 12], we expect the variance of each subspace to be balanced.”
A Survey on Learning to Hash (2016, methodology): “SIFT1B [53] includes 1B 128-dimensional BYTE-valued SIFT vectors as the reference set, 100M vectors as the learning set and 10K vectors as the query set.”
Inner Product Similarity Search using Compositional Codes (2014, methodology): “We conduct the inner product similarity search experiments over four data sets: SIFT1 M [6], SIFT1 B [25], linear models (LM1 M ), and Netﬂix.”
The Inverted Multi-Index (2012, methodology): “ments was introduced in [13] and contains 1 billion of 128-”
Estimating Local Intrinsic Dimensionality (2015, positive): “This set has been created for the evaluation of nearestneighbor search strategies at very large scales [23].”
Permutation Search Methods are Efficient, Yet Faster Search is Possible (2015, methodology): “SIFT is a ﬁve million subset of SIFT descriptors (from the learning subset) downloaded from a TEXMEX collection website[27].”
The Faiss Library (2024, neutral): “The k-means vector quantizer (Kmeans): The ideal vector quantizer minimizes the MSE between the original and the decompressed vectors.”
Milvus: A Purpose-Built Vector Data Management System (2021, methodology): “SIFT1B contains1billion128-dimensionalSIFTvectors(512GB)and Deep1B contains 1 billion 96-dimensional image vectors (384GB) extracted from a deep neural network.”
Locally Optimized Product Quantization for Approximate Nearest Neighbor Search (2014, background): “A second-order inverted multiindex [3] comprises two subspace quantizers Q1, Q2 over Rd/2, each of K sub-centroids.”
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 vulnerability of learning to adversarial perturbation increases with intrinsic dimensionality (2017, methodology): “Figure 4 plots the values for δ when using the BIGANN_SIFT1B dataset [25], where d = 128 and n = 10(9).”
Fast search in Hamming space with multi-index hashing (2012, methodology): “Shown are histograms of the search radii that are required to find 10-NN and 1000-NN, for 64 and 128-bit code from LSH [2], and 128-bit codes from MLH [16], based on 1B SIFT descriptors [11].”
Fast Neighborhood Graph Search Using Cartesian Concatenation (2013, methodology): “The superiority over IVFADC stems from that our approach signiﬁcantly increases the number of inverted indices and produces space partitions with smaller (coarse) quantization errors and that our system accesses a few coarse centers while guarantees relatively accurate inverted lists.”
Improving Bilayer Product Quantization for Billion-Scale Approximate Nearest Neighbors in High Dimensions (2014, methodology): “We also follow the previous works [5, 1, 2] and use the Recall@T as a main measure of the NN-search system quality.”
Fast Exact Search in Hamming Space With Multi-Index Hashing (2013, neutral): “With 64-bit codes there are about 1B buckets within a Hamming ball with a 7-bit radius.”