用无损压缩技术大幅减小向量索引体积，提升大规模检索效率。
Lossless Compression of Vector IDs for Approximate Nearest Neighbor Search
- 利用熵编码与波浪树压缩向量ID，不依赖排序顺序
- 在十亿级数据上减少30%索引大小，搜索性能不变
- 适合需要高精度的海量向量检索系统使用
向量近似最近邻搜索通常依赖驻留于内存的索引，存储空间成为限制单机可服务数据库规模的关键因素。尽管嵌入量化已广泛用于压缩向量，但对于倒排文件和图结构索引，辅助数据如向量ID和边链接仍占主要存储开销。本文提出并评估了针对此类场景的无损压缩方案，基于非对称数值系统（ANS）和波浪树（wavelet trees），利用数据结构中ID顺序无关的特性。在某些场景下，向量ID压缩比达7倍，不影响精度或搜索速度；在十亿级数据集上，索引大小减少30%。此外，我们发现部分数据集可通过优化原始量化算法中的次优性，实现量化码字的无损压缩。代码已开源：https://github.com/facebookresearch/vector_db_id_compression。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。