更高效的近似最近邻搜索
在今年的Web Conference上，提出了一种使基于图的最近邻搜索更高效的新技术。该技术基于关键观察：当计算查询点与候选列表中较远点的距离时，近似距离测量通常足够。FINGER技术通过高效计算近似距离，将搜索时间减少20%-60%。
基于图的搜索方法
近似k最近邻搜索算法主要分为三类：量化方法、空间划分方法和基于图的方法。在多个基准数据集上，基于图的方法目前表现最佳。
搜索过程从图中选取起点c，探索其邻居节点，计算这些节点与查询向量q的距离，将最近邻加入候选列表。然后从候选列表中选择最接近q的节点继续探索，直到未探索节点与q的距离开始增大。
FINGER技术原理
FINGER（基于图的近似最近邻搜索快速推理）技术的关键创新在于距离近似计算：
- 将查询向量q和新节点d表示为沿已探索节点c的投影分量和残差向量分量之和
- 利用预计算存储的节点向量值，q与d的距离计算简化为估计它们残差向量间的夹角
- 该夹角可通过c的直接邻居残差向量间的关系合理近似
性能评估
在三个不同数据集上的测试表明：
- 在98%召回率下，一个数据集效率提升达50%
- 在86%召回率下，另一个数据集效率提升近88%
- 性能优势在各种图构建方法中均保持一致
这项技术为高维空间中的近似最近邻搜索提供了通用的效率提升方案，特别适用于需要快速响应的大规模机器学习应用场景。