使用倒排文件索引进行近似最近邻搜索

Approximate Nearest Neighbor Search Using Inverted File Index

使用 kNN 进行最近邻搜索的一个最大问题在于它执行的是穷举搜索。

换句话说，查询数据点必须与所有数据点逐一匹配才能找到最近邻。这非常低效，尤其是当数据点很多且需要近乎实时的响应时。正因如此，近似最近邻（ANN）搜索算法正变得越来越流行。其核心思想是利用索引（indexing）技术缩小搜索空间，从而提升整体的运行时性能。

倒排文件索引（IVF）可能是这里最简单、最直观的技术之一，你可以马上开始使用。

给定高维空间中的一组数据点，其思路是把它们组织到不同的划分（partition）中，通常使用像 k-means 这样的聚类算法。

结果是，每个划分都有一个对应的质心，而每个数据点只与离它最近的质心所对应的那个划分相关联。

同时，每个质心都维护着关于其划分内所有数据点的信息。

索引建立完成！

在搜索查询数据点的最近邻时，我们不再在整个数据集中搜索，而是先找到离查询最近的质心：

一旦找到最近的质心，就只在属于这个最近划分的那些数据点中搜索最近邻：

我们来看看运行时复杂度与传统 kNN 相比如何。考虑以下几点：

• 共有 N 个数据点
• 每个数据点是 D 维的
• 我们创建 K 个划分。
• 最后，为简单起见，假设每个划分获得相等数量的数据点。

在 kNN 中，查询数据点要与全部 N 个数据点匹配，因此时间复杂度为 O(N·D)。

而在 IVF 中，有两个步骤：1. 与所有质心匹配 → O(K·D)。2. 在最近的划分中寻找最近邻 → O(N·D/K)。

最终的时间复杂度如下：

……这比 kNN 显著要低。举个直观的例子，假设我们有 1000 万个数据点。kNN 的搜索复杂度与 10M 成正比。而用 IVF，假设我们把数据划分成 100 个质心，每个划分大约分到 10 万个数据点。于是时间复杂度与 100 + 100k = 100100 成正比，快了将近 100 倍。

当然，必须注意的是，如果有些数据点实际上很接近

输入数据点，却恰好落在相邻的划分中，我们在最近邻搜索时就会错过它们，如这张图所示。

但这种精度上的折中是我们为了更好的运行时性能而心甘情愿接受的，这正是这些技术被称为“近似最近邻搜索”的原因。