Abstract
Searching through high-dimensional spaces with billions of points requires efficient indexing structures. Traditional methods using multiple independent inverted indexes often suffer from redundancy, as independent quantizers tend to cluster around the same dense data regions. This paper proposes Joint Inverted Indexing, a method that jointly optimizes multiple quantizers to provide diverse coverage of the data space. By reducing redundant partitions, the approach achieves over 90% recall on billion-scale datasets in under 10 milliseconds.
Introduction
In the era of big data, navigating high-dimensional spaces is a critical challenge for computer vision and information retrieval. Inverted indexing, analogous to a textbook index, maps features to "visual words" (codewords) using quantizers like k-means. To improve search accuracy, systems often employ multiple inverted files. The rationale is that if one quantizer misses a neighbor due to boundary effects, another might capture it. However, existing methods like k-means Locality Sensitive Hashing (KLSH) generate these quantizers independently, leading to significant inefficiencies.
The Redundancy Problem
Independent k-means trials naturally gravitate toward dense data clusters. Consequently, multiple independent quantizers often produce highly similar codewords and partition boundaries. This redundancy means that multiple indexes "watch" the same regions while simultaneously missing the same boundaries, wasting computational resources without improving recall.
Joint Optimization Methodology
The authors propose a three-step joint optimization process to move from independent quantizer construction to a coordinated approach:
- Joint Codeword Generation: Instead of running k-means L times to get K codewords each, the algorithm runs a single pass of k-means to generate all L x K codewords at once. This ensures that the entire pool of codewords is diverse and covers the data space efficiently.
- Codeword Grouping: These L x K codewords are organized into K balanced groups. Each group contains L codewords that are relatively close to each other.
- Codeword Assignment: To build a specific quantizer, the algorithm randomly selects exactly one codeword from each of the K groups. This is repeated L times to create L distinct quantizers.
This strategy ensures each quantizer remains dispersed across the space while shifting boundaries relative to one another, maximizing the probability that a query point falls "well-inside" at least one partition.
Experimental Results
The method was evaluated on standard high-dimensional benchmarks including SIFT1M, GIST1M, and the massive SIFT1B dataset (one billion SIFT vectors). Joint Inverted Indexing consistently outperformed LSH, randomized k-d trees, and the then-state-of-the-art Inverted Multi-Index.
On the SIFT1B dataset, the method achieved over 90% recall (within the top 100 candidates) in less than 10 milliseconds using a single CPU thread. This performance highlights the efficiency gains of minimizing joint distortion across multiple quantizers.
Conclusion
Joint Inverted Indexing demonstrates that optimizing quantizers collectively rather than independently significantly enhances large-scale search efficiency. By focusing on the "at least one" principle—where a point only needs to be correctly indexed in one of the L quantizers—the method avoids the pitfalls of redundant coverage. While it requires a larger memory footprint to store multiple inverted files, its superior speed and recall make it a powerful tool for production-scale indexing systems.
This paper was originally presented at ICCV 2013 by researchers from Microsoft Research Asia and the University of Science and Technology of China.
Summary updated