RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Search

在高维欧氏空间中寻找近似最近邻（ANN）是一个关键问题。最近，借助快速的基于SIMD的实现，产品量化（PQ）及其变体通常可以高效准确地估计向量之间的距离，并在内存中的ANN搜索中取得了巨大成功。尽管它们在经验上很成功，但我们注意到这些方法没有理论误差界限，并且在某些真实世界的数据集上会灾难性地失败。受此启发，我们提出了一种名为RaBitQ的新的随机量化方法，它将$D$维向量量化为$D$位字符串。RaBitQ保证了一个尖锐的理论误差界限，并同时提供了良好的经验精度。此外，我们引入了高效的RaBitQ实现，支持使用位操作或基于SIMD的操作来估计距离。在真实世界的数据集上进行的大量实验证实，（1）我们的方法在精度-效率平衡方面明显优于PQ及其变体，（2）它的经验表现与我们的理论分析相一致。

本论文旨在解决高维欧几里得空间中的近似最近邻问题，并提出了一种新的随机量化方法RaBitQ。

RaBitQ将D维向量量化为D位字符串，具有尖锐的理论误差界限，并提供了支持位运算或基于SIMD的操作的高效实现。

论文在多个真实数据集上进行了广泛的实验，证明RaBitQ在准确性和效率方面都优于PQ及其变体。论文的实验设计详细，使用的数据集丰富，代码也有开源版本。值得深入研究的是RaBitQ的理论误差界限和高效实现方式。

近期相关研究包括Product Quantization及其变体等。