Lossless Compression Of Vector Ids For Approximate Nearest Neighbor Search

Abstract

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 c

Stats

• citations0
• S2 citations—
• github stars89
• HF likes0
• heat score11.11
• arxiv keysevero2025lossless

Related papers

• Interleaved Composite Quantization For High-dimensional Similarity Search (2019)0.00
• Practical And Asymptotically Optimal Quantization Of High-dimensional Vectors In Euclidean Space For Approximate Nearest Neighbor Search (2024)8.82
• Nearest Neighbor Search With Compact Codes: A Decoder Perspective (2021)3.58
• Quantization Meets Projection: A Happy Marriage For Approximate K-nearest Neighbor Search (2024)0.00
• Polysemous Codes (2016)11.49
• Associative Memories To Accelerate Approximate Nearest Neighbor Search (2016)6.34
• Dimension Vs. Precision: A Comparative Analysis Of Autoencoders And Quantization For Efficient Vector Retrieval On BEIR Scifact (2025)0.00
• Qinco2: Vector Compression And Search With Improved Implicit Neural Codebooks (2025)0.00