# Lossless Compression of Vector IDs for Approximate Nearest Neighbor Search

arXiv: https://arxiv.org/abs/2501.10479 · HTML: https://mlsanity.com/paper/2501.10479/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 64 references that are in the map.
- First posted on arXiv 16 Jan 2025.

## Builds on (most cited first, 24 of 24)

- [Billion-scale similarity search with GPUs](https://mlsanity.com/paper/1702.08734/) (2017)
- [Deep Compression: Compressing Deep Neural Networks with Pruning, Trained Quantization and Huffman Coding](https://mlsanity.com/paper/1510.00149/) (2015)
- [Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs](https://mlsanity.com/paper/1603.09320/) (2016)
- [Google Landmarks Dataset v2 -- A Large-Scale Benchmark for Instance-Level Recognition and Retrieval](https://mlsanity.com/paper/2004.01804/) (2020)
- [A Self-Supervised Descriptor for Image Copy Detection](https://mlsanity.com/paper/2202.10261/) (2022)
- [Spreading vectors for similarity search](https://mlsanity.com/paper/1806.03198/) (2018)
- [Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph](https://mlsanity.com/paper/1707.00143/) (2017)
- [Practical Lossless Compression with Latent Variables using Bits Back Coding](https://mlsanity.com/paper/1901.04866/) (2019)
- [Results of the NeurIPS'21 Challenge on Billion-Scale Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2205.03763/) (2022)
- [Revisiting the Inverted Indices for Billion-Scale Approximate Nearest Neighbors](https://mlsanity.com/paper/1802.02422/) (2018)
- [HiLLoC: Lossless Image Compression with Hierarchical Latent Variable Models](https://mlsanity.com/paper/1912.09953/) (2019)
- [Residual Quantization with Implicit Neural Codebooks](https://mlsanity.com/paper/2401.14732/) (2024)
- [CAGRA: Highly Parallel Graph Construction and Approximate Nearest Neighbor Search for GPUs](https://mlsanity.com/paper/2308.15136/) (2023)
- [Unsupervised Neural Quantization for Compressed-Domain Similarity Search](https://mlsanity.com/paper/1908.03883/) (2019)
- [RoarGraph: A Projected Bipartite Graph for Efficient Cross-Modal Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2408.08933/) (2024)
- [DeDrift: Robust Similarity Search under Content Drift](https://mlsanity.com/paper/2308.02752/) (2023)
- [Link and code: Fast indexing with graphs and compact regression codes](https://mlsanity.com/paper/1804.09996/) (2018)
- [Automating Nearest Neighbor Search Configuration with Constrained Optimization](https://mlsanity.com/paper/2301.01702/) (2023)
- [Compressing Multisets with Large Alphabets using Bits-Back Coding](https://mlsanity.com/paper/2107.09202/) (2021)
- [Zuckerli: A New Compressed Representation for Graphs](https://mlsanity.com/paper/2009.01353/) (2020)
- [Entropy Coding of Unordered Data Structures](https://mlsanity.com/paper/2408.08837/) (2024)
- [Random Edge Coding: One-Shot Bits-Back Coding of Large Labeled Graphs](https://mlsanity.com/paper/2305.09705/) (2023)
- [Random Permutation Codes: Lossless Source Coding of Non-Sequential Data](https://mlsanity.com/paper/2411.14879/) (2024)
- [Random Cycle Coding: Lossless Compression of Cluster Assignments via Bits-Back Coding](https://mlsanity.com/paper/2412.00369/) (2024)

## Built on by (most cited first, 1 of 1)

- [LEANN: A Low-Storage Vector Index](https://mlsanity.com/paper/2506.08276/) (2025)

## Abstract (arXiv)

Approximate nearest neighbor search for vectors relies on indexes that are most often accessed from RAM. Therefore, storage is the factor limiting the size of the database that can be served from a machine. Lossy vector compression, i.e., embedding quantization, has been applied extensively to reduce the size of indexes. However, for inverted file and graph-based indices, auxiliary data such as vector ids and links (edges) can represent most of the storage cost. We introduce and evaluate lossless compression schemes for these cases. These approaches are based on asymmetric numeral systems or wavelet trees that exploit the fact that the ordering of ids is irrelevant within the data structures. In some settings, we are able to compress the vector ids by a factor 7, with no impact on accuracy or search runtime. On billion-scale datasets, this results in a reduction of 30% of the index size. Furthermore, we show that for some datasets, these methods can also compress the quantized vector codes losslessly, by exploiting sub-optimalities in the original quantization algorithm. The source code for our approach available at https://github.com/facebookresearch/vector_db_id_compression.