提出可灵活压缩的量化方法，兼顾高精度与低内存消耗。
Practical and Asymptotically Optimal Quantization of High-Dimensional Vectors in Euclidean Space for Approximate Nearest Neighbor Search
- 扩展RaBitQ支持多种压缩率，保持理论最优性
- 在相同内存下，精度和效率均超越现有方法
- 适合需要平衡速度与存储的向量搜索场景
高维欧氏空间中的近似最近邻（ANN）查询是数据库系统的关键操作。量化是一种主流向量压缩方法，可降低内存开销。近期的RaBitQ方法在相同压缩率下实现了最佳的准确率与效率，并具备严格的理论保证。但该方法仅适用于高压缩率（32倍）场景，无法通过增加空间提升精度。本文提出一种新量化方法，扩展了RaBitQ的适用范围，继承其理论优势，证明了在空间与误差边界之间的渐近最优性。同时，设计了高效实现方案，使该方法可用于实际的ANN查询，显著降低空间与时间开销。在真实数据集上的大量实验表明，在相同内存条件下，本方法始终优于当前最优基线，兼具更高准确率与更快速度。
原文摘要 · Abstract (English)
Approximate nearest neighbor (ANN) query in high-dimensional Euclidean space is a key operator in database systems. For this query, quantization is a popular family of methods developed for compressing vectors and reducing memory consumption. Recently, a method called RaBitQ achieves the state-of-the-art performance among these methods. It produces better empirical performance in both accuracy and efficiency when using the same compression rate and provides rigorous theoretical guarantees. However, the method is only designed for compressing vectors at high compression rates (32x) and lacks support for achieving higher accuracy by using more space. In this paper, we introduce a new quantization method to address this limitation by extending RaBitQ. The new method inherits the theoretical guarantees of RaBitQ and achieves the asymptotic optimality in terms of the trade-off between space and error bounds as to be proven in this study. Additionally, we present efficient implementations of the method, enabling its application to ANN queries to reduce both space and time consumption. Extensive experiments on real-world datasets confirm that our method consistently outperforms the state-of-the-art baselines in both accuracy and efficiency when using the same amount of memory.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。