Lossless Compression of Vector IDs for Approximate Nearest Neighbor Search

近似最近邻搜索依赖于大多数情况下从RAM访问的索引。因此，存储是限制可以从一台机器服务的数据库大小的因素。有损向量压缩，即嵌入量化，已被广泛应用于减少索引的大小。然而，对于倒排文件和基于图的索引，辅助数据（如向量ID和链接（边））可能占据了大部分的存储成本。我们介绍了这些情况下的无损压缩方案，并对其进行了评估。这些方法基于非对称数字系统或小波树，利用了在数据结构内部ID顺序无关紧要这一事实。在某些设置下，我们可以将向量ID压缩7倍，而不会影响准确度或搜索运行时间。对于十亿级规模的数据集，这可以将索引大小减少30%。此外，我们还证明，对于某些数据集，这些方法还可以通过利用原始量化算法中的次优性来无损压缩量化向量代码。我们的方法的源代码可在https://github.com/facebookresearch/vector_db_id_compression获取。

论文试图解决在近似最近邻搜索中，由于辅助数据（如向量ID和链接）导致的存储成本过高的问题。这并不是一个全新的问题，但该研究专注于减少这些特定类型的存储开销，以支持更大规模的数据集。

关键思路是引入无损压缩方案，特别是基于不对称数字系统或小波树的方法，来压缩向量ID和其他辅助数据。这些方法利用了ID顺序在数据结构内部无关紧要的事实，从而实现了高效压缩，而不会影响查询准确性和运行时间。相比现有研究，这种方法特别针对辅助数据进行了优化。

实验设计包括对不同规模数据集的测试，展示了高达7倍的压缩率，且对搜索性能没有负面影响。此外，对于某些数据集，还能进一步无损压缩量化后的向量代码。研究使用了数十亿规模的数据集，并且提供了开源代码（https://github.com/facebookresearch/vector_db_id_compression）。未来值得深入研究的方向包括探索更多类型的数据集适用性及改进现有的量化算法。

近期相关研究包括但不限于：1) 基于学习的索引结构优化；2) 高维空间中的高效检索算法；3) 利用神经网络进行特征编码和解码的研究。具体论文例如《Deep Learning-based Hashing for Approximate Nearest Neighbor Search》、《Optimized Product Quantization for Approximate Nearest Neighbor Search》等。