AnnArbor: Approximate Nearest Neighbors Using Arborescence Coding

Artem Babenko, Victor S. LempitskyICCV 2017 · OpenReview

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.

Topological variants of joint coding: Star Coding (left), Arborescence Coding (middle), and Multi-level Arborescence (right).

The encoding process follows these steps:

  1. Joint Coding: The dataset is organized into a forest. Roots are encoded using standard absolute quantization (e.g., Optimized Product Quantization).
  2. 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.
  3. 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.
  4. 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).

Reconstruction error and distribution analysis for the DEEP10M dataset using 16 bytes per vector.
  • 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

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 to that, we present a new coding scheme that arranges dataset descriptors into a set of arborescence graphs, and then encodes non-root descriptors by quantizing their displacements with respect to their parent nodes. By optimizing the structure of arborescences, our coding scheme can decrease the quantization error considerably, while incurring only minimal overhead on the memory footprint and the speed of nearest neighbor search in the compressed dataset compared to the independent quantization. The advantage of the proposed scheme is demonstrated in a series of experiments with datasets of SIFT and deep descriptors.
BibTeX
@inproceedings{babenko2017annarbor,
  author = {Artem Babenko and Victor S. Lempitsky},
  title = {{AnnArbor: Approximate Nearest Neighbors Using Arborescence Coding}},
  booktitle = {IEEE/CVF International Conference on Computer Vision},
  year = {2017},
  url = {https://openreview.net/forum?id=rybbObzu-B},
}
Figure