Abstract
To compress large datasets of high-dimensional descriptors, modern quantization schemes learn multiple codebooks and then represent individual descriptors as combinations of codewords. Once the codebooks are learned, these schemes encode descriptors independently. In contrast, we present AnnArbor, a new coding scheme that arranges dataset descriptors into a set of arborescence graphs and encodes non-root descriptors by quantizing their displacements with respect to their parent nodes. By optimizing the structure of arborescences, our coding scheme significantly decreases quantization error while incurring minimal overhead on memory and search speed.
Introduction: The Redundancy in High-Dimensional Data
Modern computer vision tasks often involve searching through billions of high-dimensional vectors, such as SIFT or deep features. To make this manageable, vectors are typically compressed using quantization, which maps them to a finite set of codewords. The standard approach, Product Quantization (PQ), treats each vector as an independent entity. However, this ignores the inherent local structure of datasets; nearby vectors often share significant information. Encoding their absolute positions independently is redundant. AnnArbor addresses this by exploiting the relationships between neighboring vectors to improve compression accuracy without sacrificing search efficiency.
Methods: Arborescence and Star Coding
The core innovation of AnnArbor is the use of Arborescence Coding. An arborescence is a directed tree where every node except the root has exactly one parent. The dataset is partitioned into a forest of these trees.
The encoding process follows these steps:
- Joint Coding: The dataset is organized into a forest. Roots are encoded using standard absolute quantization (e.g., Optimized Product Quantization).
- Relative Encoding: Non-root nodes are represented by the quantized displacement (difference vector) from their parent. Because displacements between neighbors are smaller than absolute coordinates, they can be quantized with much higher precision.
- Topology Optimization: The tree structure is not fixed. AnnArbor greedily optimizes the topology, deciding for each point whether it should be a root or a child based on which minimizes the total reconstruction error.
- Star Coding: A simplified version where trees have a maximum depth of one. This "star" structure (one root, many direct children) is easier to implement and maintains extremely low memory overhead.
Search remains fast because scalar products are additive. The scalar product of a query and a child node is the sum of the scalar product with the parent and the scalar product with the displacement. By using look-up tables and a breadth-first traversal, search speed remains comparable to standard PQ.
Key Results
AnnArbor consistently outperforms standard baselines like OPQ and Multi-D-ADC across various memory budgets and datasets, including SIFT1M, DEEP1M, and the San Francisco Landmark Dataset (SFLD).
- Error Reduction: On deep datasets, the scheme reduces Mean Squared Reconstruction Error (MSRE) by up to 20% compared to OPQ.
- Search Accuracy: Recall@k metrics are significantly improved, particularly for deep descriptors which exhibit strong local clustering.
- Low Overhead: By re-ordering the dataset so that trees are stored contiguously, the topology information can be stored using only 2-3 bits per vector—a negligible cost for a massive gain in accuracy.
Conclusion and Future Work
AnnArbor demonstrates that treating dataset topology as an optimization variable can yield substantial gains in vector compression. While the current greedy optimization for building trees is effective, future work may explore more sophisticated graph algorithms or integration with inverted indexing (IVF) to scale to billions of vectors.
Summary updated