更高效的近似最近邻搜索

当今许多机器学习应用都涉及最近邻搜索：数据被表示为高维空间中的点；查询（例如需要与数据点匹配的照片或文本字符串）被嵌入该空间；检索与查询最接近的数据点作为候选解决方案。然而，计算查询与数据集中每个点之间的距离通常耗时过长，因此模型构建者转而使用近似最近邻搜索技术。其中最流行的是基于图的近似方法，即将数据点组织成图结构，搜索算法遍历图并持续更新遇到的最近邻点列表。

在今年的网络会议上发表的一篇论文中，介绍了一种使基于图的最近邻搜索更加高效的新技术。该技术基于这样的观察：当计算查询与当前候选列表中所有点更远的点之间的距离时，近似距离测量通常就足够了。因此，提出了一种高效计算近似距离的方法，显示可将近似最近邻搜索所需时间减少20%至60%。

基于图的搜索

广义上讲，近似k最近邻搜索算法（寻找最接近查询向量的k个邻居）分为三类：量化方法、空间分区方法和基于图的方法。在几个基准数据集上，基于图的方法目前表现最佳。

给定查询q的嵌入，基于图的搜索选择图中的一个点c并探索其所有邻居（即与其共享边的节点）。算法计算这些节点与查询的距离，并将最接近的节点添加到候选列表中。然后从这些候选中选择最接近查询的点并探索其邻居，根据需要更新列表。此过程持续进行，直到未探索的图节点与查询向量之间的距离开始增加——这表明算法正在离开真实最近邻的邻域。

过去关于基于图近似的研究主要集中在构建基础图的方法上。例如，有些方法在给定节点和远处节点之间添加连接，以帮助确保搜索不会陷入局部最小值；有些方法专注于修剪高度连接的节点以防止同一节点被重复访问。每种方法都有其优点，但没有一种方法在所有情况下都明显胜出。

相反，我们专注于一种适用于所有图构建方法的技术，因为它提高了搜索过程本身的效率。我们将该技术称为FINGER（基于图的近似最近邻搜索的快速推理）。

近似距离计算

考虑查询向量q、正在探索其邻居的节点c以及c的一个邻居d的情况，我们希望计算d与q之间的距离。

FINGER通过参考先前探索的节点c的向量来定义查询向量q与新图节点向量d之间的距离。q和d都可以表示为沿c的投影（qproj和dproj）和与c正交的"残差"向量（qres和dres）之和。这本质上是将c视为空间的基向量。

如果算法正在探索c的邻居，则意味着它已经计算了c与q之间的距离。在论文中表明，如果利用现有计算以及节点向量值的某些操作（可以预先计算和存储），估计q和d之间的距离就简化为估计它们的残差向量之间的角度。

我们认为，该角度可以合理地根据c的直接邻居（图中与c共享边的节点）的残差向量之间的角度来近似。思路是，如果q足够接近c以至于c值得探索，那么如果q是图的一部分，它很可能是c的最近邻之一。因此，c的其他邻居的残差向量之间的关系告诉我们这些邻居之一（d）的残差向量与q的残差向量之间的关系。

为了评估方法，在三个不同数据集上将FINGER的性能与三种先前的基于图近似方法进行了比较。在一系列不同的recall10@10率（模型在其10个顶级候选中找到查询的真实最近邻的速率）下，FINGER的搜索效率均优于所有先前方法。有时差异相当显著——在一个数据集上，在98%的高召回率下达到50%，在另一个数据集上，在86%的召回率下达到近88%。