Abstract
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.
The Challenge of Large-Scale Retrieval
In modern large-scale computer vision and information retrieval systems, performing Approximate Nearest Neighbor (ANN) search across billions of high-dimensional vectors presents a significant computational and memory bottleneck. State-of-the-art methods, such as Product Quantization (PQ), address memory constraints by compressing vectors into short codes. However, this compression inevitably introduces approximation errors.
To achieve high accuracy, traditional systems often employ a "post-verification" step. This involves retrieving a short-list of candidates using compressed codes and then fetching the original, uncompressed vectors from disk to calculate exact distances. For billion-scale datasets, the original vectors cannot fit in RAM. Fetching them requires random disk I/O, which is prohibitively slow and limits the number of hypotheses that can be practically verified.
Proposed Method: Residual Re-ranking
This paper introduces a memory-efficient re-ranking scheme based on source coding, denoted as ADC+R or IVFADC+R. Instead of relying on exact vectors stored on disk, the method operates entirely in RAM using a two-tiered compression strategy:
- Base Quantization: The original vector is compressed into a coarse code (e.g., 8 bytes).
- Residual Quantization: The system calculates the "residual vector"—the difference between the original vector and its coarse approximation. This residual is then compressed using a second product quantizer into a "refinement code" (e.g., an additional 8 bytes).
During search, the system scans base codes to generate a short-list of potential neighbors. For these candidates, it reconstructs a more accurate vector by adding the decoded residual to the base approximation. This allows for highly refined distance estimates without disk access, mimicking the "successive description layers" found in scalable video compression.
The BIGANN Dataset
To evaluate ANN algorithms at a realistic scale, the authors introduced BIGANN, which was the largest public dataset for this purpose at the time of release. It consists of:
- Base vectors: 1 billion 128-dimensional SIFT descriptors.
- Query vectors: 10,000 vectors with pre-computed ground-truth nearest neighbors.
- Learning vectors: 100 million vectors used for training quantizers.
Prior to BIGANN, most methods were evaluated on smaller datasets that failed to capture the severe memory and disk I/O constraints inherent in real-world, billion-scale applications.
Experimental Results
Experiments on the BIGANN dataset demonstrate that adding a short refinement code significantly improves accuracy with negligible impact on query latency. For instance, adding an 8-byte refinement code to an 8-byte base code in the ADC method improved recall@10 from 27.4% to 68.3%.
For the inverted-file variant (IVFADC+R), the refinement step nearly doubled the recall@10 (from 37.2% to 70.1%) while only increasing query time from 0.074 to 0.116 seconds. Furthermore, the split ADC+R method (8 bytes base + 8 bytes refinement) proved more efficient than a standard ADC using a single 16-byte code, achieving better recall while being approximately twice as fast because heavy distance calculations are restricted to a small subset of candidates.
Conclusion
This RAM-based re-ranking strategy provides a scalable solution for billion-vector search. By using residual quantization to refine distance estimates, the method bypasses the slow disk I/O bottleneck of traditional post-verification. The approach is highly adaptable and can be integrated into various multi-dimensional indexing frameworks that provide approximate vector reconstructions.
Summary updated