更高效的近似最近邻搜索

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

在今年网络会议上发表的论文中，我们提出了一种新技术，显著提高了基于图的最近邻搜索效率。该技术基于这样的观察：当计算查询与比当前候选列表中任何点都远的点之间的距离时，近似距离测量通常已足够。因此，我们提出了一种高效计算近似距离的方法，并证明该方法可将近似最近邻搜索所需时间减少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%。

研究领域

搜索与信息检索

标签

网络会议