Source-linked AI summary
Searching in one billion vectors: re-rank with source coding
Hervé Jégou, Romain Tavenard, Matthijs Douze, Laurent Amsaleg
TL;DR
Large-scale compressed indexing needs accurate re-ranking without loading full database vectors from disk. The paper refines neighbor hypotheses using short quantization codes and evaluates the approach on a public billion-vector dataset, where re-ranking improves recall and search precision at low response-time cost.
Problem
Exact post-verification of shortlisted neighbors requires reading full vectors from disk when billion-scale databases exceed central memory.
Method
The paper re-ranks hypotheses from compression-based indexing by refining estimated distances with quantization codes stored in memory.
Results
Re-ranking strongly improves recall and precision, achieving state-of-the-art performance on a one-billion-vector dataset without disk access.
Takeaways & Limitations
The approach offers an alternative to standard post-verification while using little memory compared with full-vector storage.
Takeaways & Limitations
The evaluation omits measures for retrieving k nearest neighbors with k > 1, relying on the conclusion that k=1 remains qualitatively valid.
Abstract
from arXiv · showhide
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.
1. INTRODUCTION
Approximate nearest-neighbor methods support large-scale applications but face a memory–accuracy trade-off. Compression-based approaches reduce memory use, while re-ranking improves the ordering of retrieved hypotheses but traditionally requires accessing full vectors.
- Approximate nearest-neighbor search is needed for large databases, including computer-vision and music-retrieval applications.
- Many established methods consume substantial memory because they require several hash tables or trees.
- Re-ranking improves the search output of partitioning-, binary-, and quantized-code methods by verifying early neighbor hypotheses.
- Standard re-ranking computes exact Euclidean distances for shortlisted hypotheses, requiring vectors to be read from disk when they do not fit in memory.
- The paper proposes a post-verification scheme for compression-based indexing methods, focusing on a state-of-the-art method that outperforms FLANN.
CNRS, IRISA
The paper combines compressed-code refinement with a billion-vector evaluation benchmark. Its experiments report improved precision and state-of-the-art performance without disk access.
- The method refines the initial ranking using codes stored in RAM, exploiting the first-stage approximation of each indexed vector.
- The evaluation dataset contains one billion SIFT vectors and uses exact nearest-neighbor ground truth for 10000 queries.
- The dataset addresses memory issues overlooked by evaluations on unrealistically small collections of vectors.
- Re-ranking significantly improves search precision and achieves state-of-the-art performance at billion-vector scale without accessing the disk.
2. CONTEXT: COMPRESSION BASED INDEXING
The context introduces ADC, a source-coding index that represents database vectors with quantized codes and ranks them using approximate distances. Product quantization makes large codebooks tractable by separately quantizing subvectors and using lookup tables.
- ADC encodes each database vector with a quantized version and estimates its distance to an unquantized query.
- The approximate nearest neighbor is obtained by minimizing the distance estimator rather than the exact distance.
- Unlike binary embedding, ADC leaves the query unencoded, so it introduces no approximation error on the query side.
- Product quantization splits each vector into m subvectors and separately quantizes them, avoiding explicit enumeration of a large K-means codebook.
- The induced product-quantizer codebook contains K = (Ks)^m centroids while each subquantizer uses a small Ks-sized codebook.
- Lookup tables provide subvector distance terms, with generation complexity O(d × Ks), negligible versus O(d × n) when Ks ≪n.
- The method represents indexing as vector approximation, with quantization error bounded on average and improving as more code bits are allocated.
3. RE-RANKING NEIGHBORS USING SOURCE CODING
The method refines approximate neighbor rankings using compact codes that reconstruct improved database-vector approximations, avoiding exact full-vector post-verification. It adds residual codes to the initial indexing codes and re-ranks only the retrieved shortlist, with memory determined by both code lengths.
- 3.1. Refinement: principle: The method avoids costly exact post-verification by refining distances from the database-point approximation supplied by ADC indexing.ADC provides an explicit approximation qc(y), which the method exploits instead of reading and comparing full indexed vectors.
- 3.1. Refinement: principle: For selected shortlist vectors, the system reconstructs an improved approximation as qc(y) + qr(y − qc(y)) and recomputes the distance for re-ranking.The refined estimate is applied only to potential neighbors returned by the first retrieval stage.
- 3.1. Refinement: principle: Residual vectors are encoded with an independent product quantizer qr to reduce approximation error in estimated distances.The residual code supplies an additional description layer beyond the initial quantizer qc.
- 3.1. Refinement: principle: The total memory usage per indexed vector is m + m′ bytes, where m′ is the refinement-code length in bytes.The refinement quantizer uses 8 bits per subquantizer, leaving m′ as its parameter.
- 3.2. Search algorithm: Offline indexing learns both quantizers, encodes each vector and its residual, then stores the resulting codes with the indexing structure.The search stage first generates a shortlist with ADC, refines each shortlist vector, and returns the k vectors with smallest refined distances.
- 3.2. Search algorithm: The shortlist size k′ is typically chosen with k′/k = 2 to keep post-verification-like refinement complexity negligible.The appropriate shortlist size also depends on m, m′, k′, and the vector distribution.
4. EXPERIMENTS
Experiments on BIGANN evaluate re-ranking accuracy and efficiency for billion-scale approximate nearest-neighbor search. Re-ranking substantially improves recall, while adding limited query-time cost and enabling favorable memory–speed trade-offs.
- 4.1. BIGANN: a billion-sized evaluation dataset: BIGANN provides one billion 128-dimensional SIFT vectors, 10,000 queries, learning vectors, and exact-distance ground truth for evaluating ANN methods at realistic scale.Smaller database ground truths are also provided, and measurements were averaged over the first 1,000 queries.
- 4.2. Evaluation protocol: Recall@r measures the proportion of queries whose nearest neighbor appears within the first r ranked positions, while efficiency is measured by actual timings.Equivalently, recall@r reflects whether exact verification of a short-list of r vectors would retrieve the nearest neighbor correctly.
- 4.3. Evaluation of the proposed approach: Re-ranking significantly improves PQ+R over ADC and IVFPQ+R over IVFADC on recall@r for one-billion-vector search.The experiments use k=10000 and k′=20000; IVFADC+R compares each query with approximately 1/128th of the indexed vectors.
- 4.3. Evaluation of the proposed approach: Table 1 shows that re-ranking has limited impact on query time, while IVFADC remains better than ADC at the cost of 4 additional bytes per indexed vector.The same comparison holds between IVFADC+R and ADC+R.
- 4.3. Evaluation of the proposed approach: For fixed memory, ADC+R achieves similar recall to ADC at lower computing cost and is approximately two times faster.The re-ranking stage is nearly negligible relative to the first retrieval stage, whose complexity is asymptotically linear in m and n for large n.
- 4.3. Evaluation of the proposed approach: Increasing the refinement-code size m′ yields near-perfect neighbors, and re-ranking becomes more important as database size grows because of increasing outliers.With m′=16 bytes, search quality degrades more gracefully as the dataset expands.
5. CONCLUSION
The paper proposes memory-limited re-ranking for source-coding-based indexing and evaluates it on a new one-billion-vector dataset. Refining neighbor hypotheses with short RAM-resident codes improves recall while avoiding costly disk accesses.
- 5. CONCLUSION: The method re-ranks vectors using a limited amount of memory, avoiding costly disk accesses during post-verification.It refines the initial ranking using codes stored in RAM rather than reading full vectors from disk.
- 5. CONCLUSION: Experiments show that refinement strongly improves recall at a rather low response-time cost on a new public dataset of one billion vectors.The dataset supports experimental validation of high-dimensional indexing at billion-vector scale.