SIGMOD'23-(向量降维距离估计)High-Dimensi
2023-05-22 本文已影响0人
Caucher
编者的总结
- 本文为ANN算法提供了一个距离计算的估计方法，剪枝率比较高，还可以基于此进一步优化HNSW的搜索算法，实现简单，性能提升不错。
- 基本思路是首先使用旋转矩阵作旋转，然后随机选一些维度算L2距离，随着维数越选越多，估计距离也越来越准。
- 文章很强的一点是理论证明，关于剪枝错误率的保障，最终精度的概率保障，期望复杂度等等。
编者的思考
- 引入了两个参数，
需要控制精度，太小则达不到高精度，太大则剪枝率受到影响；另一个
相对好调一些，但是对性能影响也颇大。
- 估计距离仍不是下界距离，虽然精度保障很好，但是终归还是一个概率性的。如果能有剪枝率更高的下界距离会更好。
1 ABSTRACT & INTRODUCTION
- 距离计算近似图算法中的bottleneck
-
很多距离计算可以通过一个估计距离来进行剪枝，无需进行完整计算，理论上可以剪枝的比例是很高的。如下图蓝色部分的距离计算是没用的，算完这个点就丢了。
image.png
3 THE ADSAMPLING METHOD
本文提出的方法叫ADSampling，会在查询中动态地将向量映射到低维空间，然后算估计距离，有以下几个创新点：
- 不同的向量降维后的维度不同，在查询时动态决定。
- 对于可剪枝的向量，（下界）距离计算仅需log(D)期望复杂度。
本文算法层面很简单：
- 在索引构建阶段准备一个随机旋转矩阵，将所有向量旋转后建索引。
- query到来时，首先用该矩阵旋转，得到q'，然后正常进行ANN算法。
- 若遇到距离计算过程，随机采样q'的若干维度（从1维到D维，逐次迭代），计算近似距离和对应的剪枝条件，若可以剪枝，则返回，否则维度+
注意：
- 维度越多，近似距离越精准，误差概率越小。
- 近似距离并非下界距离，这意味着剪枝有可能错误地剪掉了不该剪的。
本文的理论贡献：
- 剪枝错误的概率可以被参数控制，可以被理论证明。
- 阴性样本的期望维数可以证明，则复杂度可以被证明。
- 使用本文方法的AKNN，在精度和效率之间的trade-off证明。注意因为毕竟是有剪枝错误的情况，所以精度肯定是下降的，但带来了效率提升，这里有一个理论证明。
【理论证明部分有机会补充】
5 AKNN++: IMPROVING AKNN+ ALGORITHMS WITH ALGORITHM SPECIFIC OPTIMIZATIONS
5.1 HNSW++: Towards More Approximation
-
HNSW的精度调节抓手是result set的长度，其中前K个作为结果返回必须是精确距离，但是K个之后就不用了，可以用本文提出的近似距离做替代。因为本来这就是个启发式搜索算法，所以也谈不上什么精度损失。
image.png
6 EXPERIMENT
6.1 Experimental Setup
- 数据集
image.png
- 所有硬件优化、SIMD、多线程禁用；
-
6.2 Experimental Results
6.2.1 Overall Results (Time-Accuracy Trade-Off)
- HNSW*是普通剪枝，就是连续算一些维度，超过BSF了就early stop掉，这是一个精确剪枝；
- HNSW+是ADSampling剪枝
- HNSW++是5.1所示。
- 普通剪枝HNSW*的提升很小；
- HSNW+提升还可以，HNSW++提升更显著；
- word2vec数据集上HNSW跑不过IVF；
- ADSampling在高精度区域的提升比低精度区域要大；
image.png
6.2.2 Results of Evaluated Dimensions and Recal
- 左图展示了各方法实际算的维度总数，以普通HNSW为100%；
- ADSampling可以只算60%维度左右，加上HNSW++，只需要算25%左右；
- HNSW+随ef增大而增大的主要原因是ef增大剪枝变得更加困难了；
- 但这个困难并没有加给HNSW++，因为它只用前K个来剪枝，所以反而在时间变长的时候，能剪掉的越来越多了。
image.png
6.2.3 Results of Time Cost Decomposition
image.png
6.2.4 Results for Evaluating the Feasibility of Distance Approximation Techniques for Reliable DCOs
- 相比于ADSampling，PQ或者随机映射的估计距离错误率更高。
image.png
6.2.5 Results of Parameter Study
- 用于剪枝的参数
-
image.png
