FINGER：基于图的近似最近邻搜索的快速推理

近似K-最近邻搜索（AKNNS）现在已经在现代应用中无处不在，例如具有双塔深度学习模型的快速搜索过程。特别是基于图的 AKNNS 方法由于其卓越的性能而受到了极大的关注。这些方法依靠贪婪图搜索来遍历数据点作为数据库中的嵌入向量。在这种贪婪搜索方案下，我们做了一个关键的观察：许多距离计算不会影响搜索更新，因此可以在不损害性能的情况下对这些计算进行近似。因此，我们提出了 FINGER，一种在 AKNNS 中进行高效图搜索的快速推理方法。FINGER 通过估计相邻残差向量之间的角度来近似距离函数。近似距离可用于绕过不必要的计算，以实现更快的搜索。根据经验，当谈到加速 HNSW（最流行的基于图的 AKNNS 方法之一）的推理时，FINGER 在不同的基准数据集上明显优于现有加速方法和传统库 20% 至 60%。

当今的许多机器学习 (ML) 应用都涉及最近邻搜索：数据表示为高维空间中的点；查询（例如，要与数据点匹配的照片或文本字符串）嵌入到该空间中；并且检索最接近查询的数据点作为候选解决方案。

然而，计算查询与数据集中每个点之间的距离通常非常耗时，因此模型构建者转而使用近似最近邻搜索技术。其中最流行的方法之一是基于图的近似，其中数据点被组织成图。搜索算法遍历图，定期更新迄今为止遇到的最接近查询的点的列表。

在今年网络会议上发表的一篇论文中，我们描述了一种新技术，该技术使基于图的最近邻搜索更加高效。该技术基于以下观察：当计算查询与比当前列表上的任何候选点更远的点之间的距离时，近似距离测量通常就足够了。因此，我们提出了一种非常有效地计算近似距离的方法，并表明它可以将执行近似最近邻搜索所需的时间减少 20% 到 60%。

基于图的搜索

从广义上讲，近似k最近邻搜索算法（找到最接近查询向量的k 个邻居）分为三类：量化方法、空间划分方法和基于图的方法。在几个基准数据集上，基于图的方法迄今为止取得了最佳性能。

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

过去对基于图的近似的研究主要集中在组装底层图的方法上。例如，某些方法会在给定节点和远程节点之间添加连接，以帮助确保搜索不会陷入局部最小值；一些方法集中于修剪高度连接的节点，以防止同一节点被反复访问。这些方法都有其优点，但没有一种方法是全面的赢家。

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

近似距离

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

FINGER通过参考先前探索的节点c的向量来定义查询向量q和新图节点向量d之间的距离。q和c都可以表示为沿c的投影（q proj和d proj）以及与c正交的“残差”向量（ q res和d res）之和。

q和d都可以表示为沿c 的投影和垂直于c 的“残差向量”之和。本质上，这是将c视为空间的基向量。

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

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

为了评估我们的方法，我们在三个不同的数据集上将 FINGER 的性能与之前三种基于图的近似方法的性能进行了比较。在一系列不同的召回率 10@10 中——或者模型在 10 个最佳候选者中找到查询的真正最近邻的比率——FINGER 的搜索效率比所有前辈都要高。有时差异非常显着——一个数据集上的差异为 50%，召回率为 98%，而另一个数据集上的差异几乎为 88%，召回率为 86%。

微信群                    公众号