高维数据的可扩展最近邻算法
摘要
在许多计算机视觉和机器学习问题中，庞大的训练集是实现良好性能的关键。然而，许多计算机视觉和机器学习算法中最耗费计算资源的部分是寻找与表示训练数据的高维向量的最近邻匹配。我们提出了新的近似最近邻匹配算法，并对其进行评估与与以前的算法进行比较。 在匹配高维特征时，我们发现两种算法最为高效：随机化 k‑d 森林（randomized k-d forest）和本文提出的新算法——优先搜索 k‑means 树（priority search k-means tree）。我们还提出了一种通过搜索多棵层次聚类树来匹配二进制特征的新算法，并证明它优于文献中常用的方法。我们表明，最佳的最近邻算法及其参数取决于数据集的特性，并描述了一种自动化配置流程，用于为特定数据集寻找最佳算法。为了将其扩展到那些无法在单台机器内存中容纳的大规模数据集，我们提出了一个分布式最近邻匹配框架，该框架可与本文所述的任何算法配合使用。所有这些研究成果已作为开源库 “快速近似最近邻库”（FLANN）发布，该库已集成到 OpenCV 并且如今成为最受欢迎的最近邻匹配库之一。
作者
Marius Muja BitLit Media Inc，温哥华，BC，加拿大
David G. Lowe 计算机科学系, 不列颠哥伦比亚大学 (UBC), 2366 Main Mall, 温哥华, BC, 加拿大
出版信息
期刊: IEEE Transactions on Pattern Analysis and Machine Intelligence 年份: 2014 卷号: 36 期号: 11 页码: 2227-2240 DOI: 10.1109/TPAMI.2014.2321376 文章编号: 6809191 ISSN: 打印 ISSN: 0162-8828, CD: 2160-9292, 电子 ISSN: 1939-3539
指标
论文引用数: 1011 总下载量: 41557
关键词
IEEE 关键词: Approximation algorithms, Clustering algorithms, Vegetation, Partitioning algorithms, Approximation methods, Machine learning algorithms, Computer vision
索引词： 高维，维度数据，最近邻算法，大型数据集，层次聚类，优化算法，计算机视觉，数据集特征，多个树，算法的一部分，单机，层次树，最近邻匹配，大型训练集，计算机视觉算法，计算机机器学习，层次聚类树，估计算法，树的数量，图像块，局部敏感哈希，最近邻搜索，SIFT特征，消息传递接口，邻域搜索，查询点，树搜索，搜索性能，优先队列，时间开销
作者关键词： 最近邻搜索，大数据，近似搜索，算法配置
未定义
第一节 介绍
许多计算机视觉算法中最耗费计算资源的部分是搜索与高维向量最相似的匹配，也称为最近邻匹配。拥有一种高效的算法来在大型数据集中快速执行最近邻匹配，能够为许多应用带来数个数量级的速度提升。此类问题的例子包括在大型数据集中寻找局部图像特征的最佳匹配 12，使用 k-means 或类似算法将局部特征聚类为视觉词 [3]，用于场景识别的全局图像特征匹配 3，人体姿态估计 4，用于物体识别的可变形形状匹配 5 或执行归一化互相关（NCC）以比较大型数据集中的图像块 6。最近邻搜索问题在许多其他应用中也具有重要意义，包括机器学习、文档检索、数据压缩、生物信息学和数据分析。
已证明使用大型训练集是获得许多计算机视觉方法良好实际性能的关键 78 9。如今，互联网是此类训练数据的庞大资源 10，但对于大型数据集，所使用算法的性能很快成为关键问题。
在高维特征工作时，正如在计算机视觉应用中遇到的多数情况（图像补丁、局部描述符、全局图像描述符），通常没有已知的近似邻居搜索算法能够同时实现精确性和可接受的性能。为了获得速度提升，许多实际应用被迫接受近似搜索，其中返回的邻居并非全部精确，意味着有些邻居是近似的，但通常仍然接近精确邻居。在实践中，近似最近邻搜索算法常能提供超过 95% 的正确邻居，并且速度比线性搜索快两到几个数量级。在许多情况下，最近邻搜索只是包含其他近似的更大应用的一部分，使用近似邻居而非精确邻居几乎没有性能损失。
本文评估了文献中最有前途的最近邻搜索算法，提出了新的算法并改进了现有算法，提出了一种执行自动算法选择和参数优化的方法，并讨论了使用计算集群将问题扩展到极大数据集的难题。我们已将所有工作发布为名为 fast library for approximate nearest neighbors（FLANN）的开源库。
1.1 定义与符号
在本文中，我们关注度量空间中高效最近邻搜索的问题。度量空间中的最近邻搜索可以定义如下：给定度量空间 M 中的一组点 P=\{ p_1, p_2, \ldots, p_n\} 以及查询点 q \in M，找到相对于度量距离 d :M \times M \rightarrow {\mathbb R} 与 q 最接近的元素 {\mathrm NN}(q,P) \in P：
{\mathrm NN}(q,P) = arg min_{x\in P}\ d(q,x).
最近邻问题 是寻找一种方法来预处理集合 P，以便能够高效执行操作 {\mathrm NN}(q,P)。
我们经常不仅想找到最近的第一个邻居，还想找到若干最近邻。在这种情况下，搜索可以根据返回的邻居数量和它们与查询点的距离以多种方式进行：K-最近邻（KNN）搜索，其目标是找到距离查询点最近的 K 个点；以及半径最近邻搜索（RNN），其目标是找到所有位于距离查询点小于 R 的点。
我们以更正式的方式定义 K-最近邻 搜索如下：
{\mathrm KNN}(q,P,K) = A,
其中 A 是满足以下条件的集合：
\vert A\vert = K, A \subseteq P
\forall x\in A, y \in P-A, d(q,x)\le d(q,y).
K最近邻搜索具有一个属性，即它将 始终返回恰好 K 个邻居（如果在 P 中至少有 K 个点）。
可以按如下方式定义 radius nearest neighbor 搜索：
{\mathrm RNN}(q,P,R) = \{ p\in P, d(q,p)< R\} .
根据如何选择值 R，半径搜索可以返回从零到整个数据集的任意数量点。在实践中，给半径搜索传递一个很大的值 R 并让搜索返回大量点往往非常低效。Radius K-nearest neighbor（RKNN）搜索是 K-nearest neighbor 搜索和半径搜索的结合，其中可以对半径搜索应返回的点数设置上限：
{\mathrm RKNN}(q,P,K,R) = A,
使得
\vert A\vert \le K, A \subseteq P
\forall x \in A, y \in P-A, d(q,x)< R\; {\mathrm and }\; d(q,x)\le d(q,y) .
SECTION 2 背景
最近邻搜索是许多计算机视觉算法的基本组成部分，也是许多其他领域的重要组成部分，因此被广泛研究。本节回顾了该领域的先前工作。
2.1 最近邻匹配算法
我们回顾了最广泛使用的最近邻技术，分为三类：划分树、哈希技术和邻接图技术。
2.1.1 划分树
kd-tree 1112 是最知名的最近邻算法之一。它在低维空间中非常有效，但在高维数据中性能会迅速下降。
Arya 等人 13 提出了一种 k-d 树的变体，用于通过考虑 (1+\varepsilon)-approximate 最近邻来进行近似搜索，其中 dist(p, q) \le (1 + \varepsilon)dist(p^\ast, q) 的真正最近邻是 p^\ast。作者还提出使用优先队列来加速搜索。这种近似最近邻搜索的方法也被称为“误差边界”近似搜索。
另一种近似最近邻搜索的方法是限制搜索过程中花费的时间，或称为“time bound”近似搜索。该方法在 14 中提出，k-d 树搜索在检查固定数量叶节点后提前停止。实际上，时间受限的近似准则往往比误差受限的近似搜索取得更好结果。
在 15 中提出了多棵随机化 k-d 树，用以加速近似最近邻搜索。在 16 中，我们进行了广泛的比较，结果表明多棵随机化树是匹配高维数据的最有效方法之一。
已提出使用非轴对齐划分超平面的 k-d 树变体：PCA 树 17、RP 树 18 以及三分投影树 19。我们未发现这些算法比随机化 k-d 树划分更高效，因为在搜索过程中评估多维度的开销超过了更优空间划分带来的收益。
另一类划分树通过使用各种聚类算法而不是像 k-d 树及其变体那样使用超平面来划分空间。例如，这些划分包括层次 k‑means 树 20、GNAT 21、锚点层次结构 22、vp‑tree [21]、cover tree 23 以及 spill-tree 24。Nister 和 Stewenius 25 提出了词汇树，通过访问层次 k‑means 树的单个叶节点来进行搜索。Leibe et al. 26 提出了使用混合分区-凝聚聚类算法构建的 ball‑tree 数据结构。Schindler et al. 27 提出了搜索层次 k‑means 树的新方法。Philbin et al. [2] 进行实验，显示在识别任务中，近似平面词汇表优于词汇树。在本文中，我们描述了一种修改后的 k‑means 树算法，我们发现在某些数据集上效果最好，而在其他数据集上随机化 k‑d 树效果最佳。
Jégou et al. 28 提出了乘积量化方法，在该方法中他们将空间划分为低维子空间，并通过在这些子空间中计算量化索引来为数据集点生成紧凑码。使用非对称近似距离，紧凑码可以高效地与查询点比较。Babenko 和 Lempitsky 29 提出了反向多索引，它通过在反向索引中用乘积量化替代标准量化来得到更细密的搜索空间划分。这两种方法已被证明在搜索大型数据集时高效，应考虑进一步评估并可能整合到 FLANN 中。
2.1.2 基于哈希的最近邻技术
或许最著名的基于哈希的最近邻技术是局部敏感哈希（LSH） 30，它使用大量哈希函数，且相近元素的哈希值也倾向于相近。LSH 的变体，如多探测 LSH 31，通过减少哈希表数量来降低高存储成本，而 LSH Forest [^29] 则在不需要手动调参的情况下更好地适应数据。
哈希方法的性能高度依赖于其使用的哈希函数质量，许多研究致力于通过使用各种学习技术计算数据相关的哈希函数来改进哈希方法：参数敏感哈希 32，谱哈希 [^30]，从学习到的度量得到的随机化 LSH 哈希 [^31]，核化 LSH [^32]，学习得到的二进制嵌入 [^33]，平移不变核哈希 [^34]，半监督哈希 [^35]，优化核哈希 [^36] 和互补哈希 [^37]。
不同的 LSH 算法为搜索质量提供理论保证，并已在多项项目中成功应用，然而我们在第 4 节报告的实验表明，在实际中，它们通常被使用空间划分结构的算法所超越，例如随机 k-d 树和优先搜索 k-means 树。
2.1.3 最近邻图技术
最近邻图方法构建了一个图结构，其中点是顶点，边将每个点连接到其最近邻。查询点用于使用各种策略探索该图，以更接近它们的最近邻。在 [^38] 中，作者在图中挑选若干相距较远的元素作为“种子”，并以最佳优先的方式从这些种子开始图探索。同样，[^39] 的作者执行了 k-NN 图的最佳优先探索，但使用爬山策略并随机选择起始点。他们展示了与随机 KD 树相比更具优势的最新实验结果，因此建议将所提出的算法用于未来评估并可能整合到 FLANN 中。
最近邻图方法面临构建 k-NN 图结构成本相当高的问题。Wang 等人 [^40] 通过构建近似最近邻图来降低构建成本。
2.2 NN 算法的自动配置
已有数百篇论文发表在最近邻搜索算法上，但缺乏系统的比较来指导在算法之间的选择并设置它们的内部参数。实际上，在大多数最近邻文献中，设置算法参数是一个手动过程，采用各种启发式方法，且很少使用更系统的方法。
Bawa et al. [^29] 表明标准 LSH 算法的性能高度依赖于哈希键的长度，并提出了 LSH Forest，一种自调节算法，消除了这一数据相关参数。
在之前的论文 33 中，我们提出了一种通过将网格搜索与更细粒度的 Nelder-Mead 下坡单纯形优化过程相结合的自动最近邻算法配置方法 [^41]。
对 algorithm configuration 方法 [^42][^43] 已有大量研究，然而我们尚未发现将此类技术应用于寻找最近邻算法最佳参数的论文。Bergstra 和 Bengio [^44] 表明，除非参数空间很小，否则随机搜索可能比网格搜索更有效的参数优化策略。
SECTION 3 快速近似 NN 匹配
精确搜索对许多应用来说成本过高，因此引起了人们对近似最近邻搜索算法的兴趣，这些算法在某些情况下返回非最优邻居，但速度可比精确搜索快数个数量级。
在评估了许多针对具有广泛维度的数据集的近似最近邻搜索算法后 34[^45]，我们发现其中两种算法中有一种表现最佳：priority search k-means tree 或 multiple randomized k-d trees。这些算法将在本节其余部分进行描述。
3.1 随机化 k-d 树算法
随机化 k-d 树算法 35，是一种近似最近邻搜索算法，它构建多棵随机化 k-d 树并并行搜索。树的构建方式类似于经典 k-d 树 36 [10]，不同之处在于经典 k-d 树在拆分时会选择方差最高的维度，而随机化 k-d 树的拆分维度是随机选择 从前 N_D 维度，具有最高方差。 我们在实现中使用了固定值 N_D=5，因为它在所有数据集上表现良好，并且进一步调优并不会带来显著收益。
在搜索随机化 k-d 森林时，所有随机化树共享一个优先队列。该优先队列按每个分支的决策边界到查询点的距离递增排序，因此搜索会首先探索所有树中最近的叶子。一次数据点在某棵树中被检查（与查询点比较）后，将被标记，以避免在其他树中再次检查。近似程度由最大访问叶子数（跨所有树）决定，返回在该时点找到的最佳最近邻候选。
图 1 显示了在同一时间在许多随机化 kd-trees 中搜索的价值。可以看出，随着随机化树数量的增加，性能提升直至某一临界点（本例中约 20 棵随机树），之后再增加随机树数量会导致性能停滞或下降。使用多棵随机树的内存开销随树的数量线性增加，因此在某一点提升的速度可能无法抵消额外的内存消耗。
图 1. 通过使用多棵随机化 kd-trees 获得的加速（100K SIFT features data set）。
图 2 说明了为什么探索多棵随机化 kd-tree 能提升搜索性能的直观原因。当查询点靠近某个拆分超平面时，它的最近邻几乎等概率位于超平面的两侧，如果位于拆分超平面的对侧，则需要进一步探索树，才能访问包含它的单元。使用多棵随机分解可以提高在其中一棵树中，查询点及其最近邻位于同一单元的概率。
图 2. 随机化 kd-trees 示例。最近邻在第一次分解中位于查询点的决策边界另一侧，但在第二次分解中与查询点在同一单元。
3.2 优先搜索 k-均值树算法
我们已经发现随机化 k-d 森林在许多情况下非常有效，然而在其他数据集上，另一种算法——priority search k-means tree——在寻找近似最近邻时更为有效，尤其是在需要高精度时。priority search k-means tree 通过使用跨所有维度的完整距离对数据点进行聚类，尝试更好地利用数据中存在的自然结构， 与仅按单个维度一次划分数据的（随机化）k-d 树算法形成对比。
基于对数据点聚类的分层划分方案的最近邻算法已在文献中提出过 37 [19]38。这些算法在构造划分树的方式（是否使用 k-means、凝聚式或其他聚类形式）以及用于探索层级树的策略上存在差异。我们开发了一个改进版本，使用 best-bin-first 策略探索 k-means 树，类似于已被发现能显著提升近似 kd-tree 搜索性能的方法。
3.2.1 算法描述
优先搜索 k-means 树通过在每一层使用 k-means 聚类将数据点划分为 K 个不同区域，然后递归地对每个区域内的点应用相同的方法来构造。递归在某个区域内的点数小于 K 时停止（见算法 1）。
树的搜索方式是先从根节点遍历到最近的叶子节点，在每个内部节点沿着与查询点最近的簇中心所在的分支前进，并将路径上未探索的所有分支加入优先队列（见算法 2）。优先队列按从查询点到正在加入队列的分支边界的距离递增排序。初始树遍历完成后，算法恢复遍历树，始终从队列中的顶端分支开始。
在每个节点划分数据时使用的簇数量 K 是算法的一个参数，称为 branching factor（分支因子），而选择 K 对获得良好搜索性能非常重要。第 3.4 节中，我们提出了一种寻找最优算法参数的算法，包括最优分支因子。图 3 展示了几种具有不同分支因子的层次 k-means 分解的可视化。
Fig. 3. 使用不同分支因子（4、32、128）构建的优先搜索 k-均值树的投影。投影采用与[26]相同的技术，灰度值表示每个树层上最近聚类中心与第二近聚类中心之间距离的比例，从而最深的值（比例 \approx 1）落在 k-均值区域之间的边界附近。
优先搜索 k-均值树的另一个参数是 I_{max}，即在 k-均值聚类循环中执行的最大迭代次数。进行更少的迭代可以显著降低树的构建时间，并导致略低于最优的聚类结果（如果我们将点到聚类中心的平方误差之和视为最优度量）。然而，我们观察到，即使使用少量迭代，最近邻搜索性能也与通过运行聚类直至收敛构造的树相似，正如图 4 所示。可以看出，使用仅七次迭代即可获得使用完整收敛构造的树的近 90% 的最近邻性能，但构建时间仅为 10% 以下。
Fig. 4. k-均值迭代次数对k-均值树搜索速度的影响。图表显示相对于使用完全收敛时的相对搜索时间。
在 k-均值聚类中选择初始中心点时可使用的算法可以通过 C_{alg} 参数进行控制。在我们的实验（以及 FLANN 库）中，我们使用了以下算法：随机选择、Gonzales’ 算法（将中心点彼此间隔开）以及 KMeans++ 算法 [^46]。我们发现，初始簇的选择在大多数情况下对整体搜索效率仅产生微小影响，而随机初始簇的选择通常是优先搜索 k-均值树的不错选择。
3.2.2 分析
在分析优先搜索 k-均值树的复杂度时，我们考虑树的构建时间、搜索时间以及存储树所需的内存。
Construction time complexity。在构建 k‑means 树的过程中，每个内部节点都必须执行一次 k‑means 聚类操作。考虑一个具有 v 个子节点、关联 n_v 条数据点的节点，并假设 k‑means 聚类循环的最大迭代次数为 I，则聚类操作的复杂度为 O(n_v d K I)，其中 d 表示数据维度。考虑同一层的所有内部节点，整体复杂度为 \sum n_v = n，因此构造树的一层的复杂度为 O(n d K I)。假设树是平衡的，树的高度为 (\log\; n / \log\; K)，从而总的树构造成本为 O(ndKI (\log\; n / \log\; K))。
Search time complexity。在时间受限的近似最近邻搜索中，算法在检查了 L 条数据点后停止。考虑一个完整的优先搜索 k‑means 树，分支因子为 K，所需的自顶向下树遍历次数为 L/K（完整的 k‑means 树中每个叶子节点包含 K 条点）。在每一次自顶向下遍历中，算法需要检查 O(\log\; n / \log\; K) 个内部节点以及一个叶子节点。
对于每个内部节点，算法需要找到距离查询点最近的分支，因此需要计算子节点所有簇中心的距离，这是一个 O(Kd) 操作。未被探索的分支被添加到优先队列中，使用二项堆时可以以 O(K) 的摊销成本完成。对于叶子节点，必须计算查询点与叶子中所有点之间的距离，耗时为 O(Kd)。综上，整体搜索成本为 O(Ld (\log\; n / \log\; K))。
3.3 层次聚类树
匹配二进制特征在计算机视觉社区越来越受到关注，最近提出了许多二进制视觉描述子：BRIEF [^47]、ORB [^48]、BRISK [^49]。许多适用于匹配基于向量的特征的算法，例如随机化 kd‑树和优先搜索 k‑means 树，要么效率不高，要么不适用于匹配二进制特征（例如，优先搜索 k‑me‑an 树要求点位于一个向量空间，其中它们的维度可以独立平均）。
二进制描述子通常使用汉明距离进行比较，对于二进制数据，可以将其计算为位异或（XOR）操作，随后对结果进行位计数（在支持计数单词中位数的硬件上非常高效）。
本节简要介绍了一种新型数据结构和算法，称为层次聚类树 ,，我们发现它在匹配二进制特征时非常有效。若要了解该算法的更详细描述，建议读者参考 [^45] 和 [^50]。
层次聚类树通过递归地将输入数据集聚类，使用随机数据点作为非叶子节点的聚类中心，对搜索空间进行分解（见算法3）。
与上述所述的优先搜索k‑means树相比，使用多棵树并没有带来显著改进，我们发现构建多棵层次聚类树并使用共享的优先队列（与对随机化kd‑tree已被证明有效的相同方法 39）并行搜索，可显著提升搜索性能。
3.4 自动选择最佳算法
我们的实验表明，近似最近邻搜索的最佳算法高度依赖于多个因素，例如数据维度、数据集的大小和结构（数据集中特征之间是否存在相关性）以及所需的搜索精度。此外，每个算法都有一组对搜索性能具有显著影响的参数（例如随机树的数量、分支因子、k‑means 迭代次数）。
正如我们在第2.2节中已提到的，最近邻算法的最优参数通常是手动选择的，使用各种启发式方法。本节提出了一种方法，用于为特定数据集自动选择最佳最近邻算法并确定其最优参数。
通过将最近邻算法本身视为通用最近邻搜索例程 A 的一个参数，问题可简化为确定给出最佳解决方案的参数 \theta \in \Theta，其中 \Theta 也称为参数配置空间。这可以表述为参数配置空间中的一个优化问题：
\mathop{\mathrm min}_{\theta \in \Theta }c(\theta)
其中 c : \Theta \rightarrow {\mathbb R} 是一个成本函数，用来表示搜索算法 A 在给定输入数据上使用参数 \theta 配置时的性能。
我们将成本定义为搜索时间、树构建时间和树内存开销的组合。根据不同的应用，这三项因素的重要性可能不同：在某些情况下，我们并不在意树的构建时间（如果仅构建一次树并在大量查询中使用），而在其他情况下，树的构建时间和搜索时间都必须尽量小（如果树是在线构建并被少量搜索）。在内存受限环境中工作时，我们还可能想限制内存开销。我们将成本函数定义如下：
c(\theta) = {{ s(\theta)+w_b b(\theta)\over {\mathrm min}_{\theta \in \Theta }(s(\theta)+w_b b(\theta))} +w_m m(\theta)}, \tag{\hbox{(1)}}
其中 s(\theta)、b(\theta) 和 m(\theta) 表示使用参数 \theta 构建并查询树时的搜索时间、树构建时间和内存开销。 内存开销被测量为树所使用的内存与数据所使用的内存之比：m(\theta) = m_t(\theta)/m_d。 权重 w_b 和 w_m 用于控制构建时间和内存开销在总体成本中的相对重要性。 构建时间权重（w_b）控制树构建时间相对于搜索时间的重要性。 搜索时间定义为搜索与树中点数相同数量的点所需的时间。 时间开销相对于最佳时间成本 {\mathrm min}_{\theta \in \Theta }(s(\theta)+w_b b(\theta)) 计算，后者定义为在不考虑内存使用的情况下的最优搜索和构建时间。
我们将上述优化分为两步进行：首先使用网格搜索对参数空间进行全局探索，然后在第一步找到的最佳解的基础上进行局部优化。网格搜索在第一步是一种可行且有效的方法，因为参数数量相对较少。在第二步中，我们使用 Nelder‑Mead 降阶单纯形法 [^41] 进一步在参数空间进行局部探索，并对第一步获得的最佳解进行微调。虽然这并不能保证得到全局最优解，但我们的实验表明得到的参数值在实际中接近最优。
我们使用随机子采样交叉验证来生成数据和查询点，在运行优化时使用。 在 FLANN 中，优化可以在完整数据集上运行以获得最准确的结果，也可以仅使用数据集的一部分来实现更快的自动调优过程。 参数选择仅需针对每种数据集类型执行一次，最优参数值可以保存并应用于所有未来同类型的数据集。
第4节 实验
对于本节所呈现的实验，我们使用了一系列具有广泛尺寸和数据维度的数据集。所用的数据集包括 Winder/Brown 补丁数据集 [53]，不同维度随机采样数据的数据集，来自 CD 封面数据集 40 的不同大小 SIFT 特征数据集，以及从形成全景的重叠图像中提取的 SIFT 特征数据集。
我们使用 搜索精度（或简称 精度）来衡量近似最近邻算法的准确性，定义为近似算法返回的邻居中真正最近邻的比例。我们将算法的搜索性能定义为执行线性搜索所需时间与执行近似搜索所需时间之比，并称其为搜索加速比或简称 加速比。
4.1 快速近似最近邻搜索
我们展示了若干实验，以分析第 3 节中描述的两种算法的性能。
4.1.1 数据维度
数据维度是对最近邻匹配性能影响巨大的因素之一。图 5 的顶部显示了在随机向量情况下，随着维度增加搜索性能下降的情况。此情况下的数据集每个包含 10^5 个向量，其值随机从同一均匀分布中采样。这些随机数据集是最近邻搜索中最困难的问题之一，因为没有任何一个值能预测任何其他值。
图 5. 对不同维度数据的搜索效率。我们在随机向量和图像补丁上进行了实验，数据集大小为 100K。随机向量（顶部图像）代表了维度无相关性的最难情况，而大多数实际问题更像图像补丁（底部图像）。
从图 5 的上部可以看出，随着维度的增加，最近邻搜索的效率很低（当维度大于 800 时，68% 的精度下，近似搜索速度不比线性搜索更快）。
在许多真实世界数据集上，性能差异显著。 图 5 底部展示了对重新采样以实现不同维度的 Winder/Brown 图像块的加速率随维度变化的函数。 然而，在这种情况下，加速率并不会随维度降低，实际上在某些精度下会增加。 这可以通过维度之间存在强相关性来解释，因此即使对于 64\times 64 块（4,096 维），仅有少数维度之间的相似性也能为整体块相似性提供有力证据。
Fig. 6 展示了在 Trevi 数据集上针对不同块大小的四个查询示例。
Fig. 6. 不同块大小的最近邻查询示例。 Trevi Fountain 块数据集使用不同块大小进行查询。 行按块大小递减排列。 查询块位于每个面板的左侧，后续的五个块是从100,000个块中得到的最近邻。 相对于真实结果的不正确匹配用 X 标示。
4.1.2 搜索精度
我们使用了几组不同大小的数据集用于图 7 中的实验。我们通过随机抽样从一组超过 500 万个 SIFT features（提取自 CD 封面图像）中构造了 10 万和 100 万个 SIFT feature data sets 41。我们还使用了同一来源的 3100 万个 SIFT feature data set。
图 7. 不同数据集大小的搜索加速.
所需的搜索精度决定了任何近似算法可以获得的加速程度。查看图 7（sift1M 数据集）我们发现，如果我们愿意接受低至 60% 的精度，即返回的邻居中有 40% 并非精确最近邻，而仅为近似，我们就能实现相较于线性搜索（使用多重随机化 kd‑trees）的三阶幅度加速。然而，如果我们要求精度超过 90%，加速幅度会更小，低于两阶幅度（使用优先搜索 k‑means 树）。
我们将最佳的两种快速近似最近邻算法（多重随机kd树和优先搜索k-means树）与现有方法ANN 42和LSH算法43在第一组包含100,000个SIFT特征的数据集上进行比较。由于LSH实现（E ^2LSH包）解决了R-近邻问题（在查询点半径R内寻找邻居，而不是最近邻），为了寻找最近邻，我们使用了E^2LSH用户手册中建议的方法：我们为递增的R值计算R-近邻。LSH算法的参数是使用包含在E^2LSH包中的参数估计工具选择的。对于每一种情况，我们已将精度计算为正确找到最近邻的查询点所占百分比。图8显示，优先搜索k-means算法在性能上比ANN和LSH算法高约一个数量级。ANN的结果与图1中的实验一致，因为ANN仅使用单棵kd树，没有从使用多棵随机化树获得加速。
图8. 比较几种最近邻算法的搜索效率.
图9比较了当数据集为测试集中的每个特征提供真正匹配时，与仅包含错误匹配时的最近邻匹配性能。真正匹配是指查询点和最近邻点代表相同实体的匹配，例如，在SIFT特征的情况下，它们表示同一对象的图像补丁。在本实验中，我们使用了两个10万SIFT特征数据集，一个是从全局图像匹配得到的真值，另一个是从500万SIFT特征数据集中随机采样的，仅包含每个测试集特征的错误匹配。我们的实验表明，在查询特征可能明显比其他邻居更接近的情况下，随机化kd树在真正匹配方面的性能显著更好。类似的结果已在[^51]中报道。
图9. 当查询点在数据集中没有“真正”匹配与有“真正”匹配时的搜索加速.
图10显示了Winder/Brown补丁数据集的一个样本中随机化kd树和优先搜索k-means树之间的性能差异。在这种情况下，随机化kd树算法显然在所有情况下都优于优先搜索k-means算法，除非精度接近100%。看起来，当数据的内在维数远低于实际维数时，kd树的表现更好，可能是因为它能更好地利用维度之间的相关性。然而，图7表明k-means树在其他数据集（尤其是高精度）上表现更好。这表明对每个数据集执行算法选择的重要性。
图10. 特里维喷泉补丁数据集的搜索加速.
4.1.3 自动选择最优算法
在表1中，我们展示了在包含10万随机采样的SIFT特征的数据集上运行第3.4节所述参数选择过程的结果。我们使用了两种不同的搜索精度（60%和90%）以及w_b和w_m这两个折衷因子的多种组合。对于构建时间权重w_b，我们使用了三种可能的取值：0代表我们不关心树的构建时间，1代表树的构建时间和搜索时间同等重要，0.01代表我们主要关心搜索时间，但也想避免构建时间过长。同样，内存权重被选为0（内存使用不是问题），\infty（内存使用是主要关注点），以及1（两者的折中）。
表 1
4.2 二进制特征
本节评估了第3.3节所述层次聚类树的性能。
我们使用 Winder/Brown patches 数据集 [^52] 来比较层次聚类树与其他知名最近邻搜索算法的最近邻搜索性能。为此比较，我们结合了向量特征（如 SIFT、SURF、图像块）和二进制特征（如 BRIEF、ORB）。图像块已被下采样到 16\times 16 像素，并使用归一化互相关进行匹配。图 11 显示了不同特征类型的最近邻搜索时间。图中每个点均使用针对该特征类型表现最佳的算法计算（SIFT、SURF、图像块使用随机化 kd-树或优先搜索 k‑means 树，BRIEF 和 ORB 使用层次聚类算法）。在每种情况下，都采用最大化给定精度加速的最优参数。
图 11. 不同流行特征类型（包括二进制和向量）的绝对搜索时间.
图 12 中，我们将层次聚类树与多探测局部敏感哈希实现 44 进行比较。为此比较，我们使用了从识别基准图像数据集 45 中提取的 BRIEF 和 ORB 特征数据集，约包含 500 万个特征。可以看出，在此数据集上，层次聚类索引的性能优于 LSH 实现。相比之下，当需要高精度时，LSH 实现需要显著更多的内存，因为它必须分配大量哈希表以实现高搜索精度。在图 12 的实验中，多探测 LSH 在搜索精度超过 90% 时所需的内存是层次搜索的六倍。
图 12. 在约 500 万特征的 Nister/Stewenius 识别基准图像数据集上，层次聚类索引与 LSH 的比较.
第5节 缩放最近邻搜索
许多论文表明，结合简单的非参数方法与大规模数据集可实现非常好的识别性能 46[7] [^53][^54]。将系统扩展到如此大型的数据集是一项艰巨的任务，其主要挑战之一是无法将数据加载到单台机器的主内存中。例如，47 的原始微型图像数据集约为 240 GB，已超过目前大多数计算机可用的内存。对于 4849 [55] 中使用的数据集大小，内存中的数据适配更为困难。
在处理如此大量的数据时，可能的解决方案包括对数据进行某些降维处理，保持数据在磁盘上并仅在主内存中加载其部分，或将数据分布到多台计算机上并使用分布式最近邻搜索算法。
降维已在文献中得到良好结果（[7] 5051 [^30][^55]），然而即使使用降维，对于非常大的数据集，在单台机器的内存中容纳数据仍然具有挑战性。将数据存储在磁盘上会因内存与磁盘访问时间之间的性能差距而导致显著的性能惩罚。在 FLANN 中，我们采用了跨多台机器执行分布式最近邻搜索的方法。
5.1 在计算集群上进行搜索
为了扩展到非常大的数据集，我们采用将数据分发到计算集群中的多台机器并使用所有机器并行执行最近邻搜索的方法。数据在机器之间均等分布，使得在一个由 N 台机器组成的集群中，每台机器只需索引和搜索整个数据集的 1/N（尽管可以更改比例，使某些机器拥有比其他机器更多的数据）。一旦所有机器完成搜索，最近邻搜索的最终结果通过合并集群中所有机器的部分结果得到。
为了在计算集群上分发最近邻匹配，我们实现了一个类似 Map-Reduce 的算法，使用消息传递接口（MPI）规范。
算法 4 描述了构建分布式最近邻匹配索引的过程。集群中的每个进程并行执行，并从分布式文件系统读取一部分数据集。所有进程使用各自的数据集片段并行构建最近邻搜索索引。
为了搜索分布式索引，查询从客户端发送到 MPI 集群中的一台计算机，我们称其为主服务器（见图 13）。按约定，主服务器是 MPI 集群中 rank 为 0 的进程，尽管 MPI 集群中的任何进程都可以扮演主服务器的角色。
图 13. 使用消息传递接口标准在计算集群上扩展最近邻搜索。
主服务器将查询广播到集群中的所有进程，然后每个进程可以在自己的一部分数据上并行运行最近邻匹配。当搜索完成后，使用 MPI 归约操作将结果合并回主进程，最终结果返回给客户端。
主服务器在合并结果时并不是瓶颈。MPI 归约操作也是分布式的，部分结果以两两的方式按层次从集群中的服务器合并到主服务器。此外，合并操作非常高效，因为查询与邻居之间的距离不需要重新计算，它们是由每个服务器的最近邻搜索操作返回的。
在为最近邻搜索分发大型数据集时，我们选择将数据划分为多个不相交的子集，并为每个子集构建独立的索引。在搜索期间，查询会广播到所有索引，每个索引在其关联的数据中执行最近邻搜索。在另一种方法中，Aly et al. [^56] 引入了一种分布式 k‑d 树实现，他们在所有其他树（叶子树）之上放置一个根 k‑d 树，根树的作用是选择一部分树进行搜索，并仅将查询发送到这些树。它们表明，分布式 k‑d 树的吞吐量高于使用独立树，原因是每个查询只需要搜索部分树。
正如上文所述并在 FLANN 中实现的那样，将数据集划分为独立子集的优点在于它不依赖所使用的索引类型（随机化 k‑d 树、优先搜索 k‑means 树、层次聚类、LSH），并且可以应用于 FLANN 中的任何现有或未来的最近邻算法。在 [^56] 的分布式 k‑d 树实现中，搜索不会在根节点回溯，因此，如果根 k‑d 树在开始时未选择相应的叶子 k‑d 树，可能会导致包含近邻点的子集根本不被搜索。
5.2 分布式搜索评估
本节我们呈现了若干实验，展示了 FLANN 中分布式最近邻匹配框架的有效性。为这些实验，我们使用了 52 的 8000 万图案数据集。
在 MPI 分布式系统中，可以在同一台机器上运行多个并行进程，推荐的方法是将进程数设置为机器的 CPU 核心数。图 14 展示了我们在单台拥有八个 CPU 核心的机器上运行多个 MPI 进程的实验结果。可以看到，从 1 个进程提升到 4 个进程时，总体性能提升；但从四个进程增加到八个进程时，性能却下降。这可以用在同一台机器上提升并行度也会增加对主内存的请求数（因为所有进程共享同一主内存）的事实来解释，最终瓶颈从 CPU 转移到内存。超过此点继续提升并行度会导致性能下降。图 14 还展示了直接使用 FLANN 而不使用 MPI 层时的直接搜索性能。预期之中，直接搜索性能与使用单进程 MPI 层时的性能相同，说明 MPI 运行时没有显著开销。为了在单台机器上进行实验，我们在本实验和图 15 中都使用了仅 800 万张微小图像的子集。
图 14. 在单台多核机器上分布式最近邻搜索。当并行度超过某个阈值后，内存访问成为瓶颈。 “直接搜索” 案例对应于直接使用 FLANN 库，而不使用 MPI 层。
图 15. 将搜索分布到多台机器的优势。即使使用相同数量的并行进程，将计算分布到多台机器仍因减少内存访问开销而提升性能。“直接搜索”对应于不使用 MPI 层直接使用 FLANN，作为对照基准。
图 15 显示了在一台、两台或三台机器上使用八个并行进程所获得的性能。即使使用相同数量的并行进程，将这些进程分布到更多机器上时，性能仍会上升。这同样可以用内存访问开销来解释，因为使用更多机器时，每台机器上运行的进程更少，从而需要的内存访问次数更少。
图 16 显示了 8000 万张微小图像 53 数据集的搜索加速。所使用的算法是 radomized k-d 树森林，因为自动调优程序判断其在此情况下最有效。可以看到，搜索性能随数据集规模良好缩放，并且使用多个并行进程时获得收益。
图 16. 直接使用计算集群匹配 8000 万个微小图像.
之前的所有实验表明，将最近邻搜索分布到多台机器上，不仅可以使用更多内存，而且整体性能都会提升。理想情况下，分布到 N 台机器时，速度提升会是 N 倍，但在实际使用近似最近邻搜索时，提升幅度更小，原因是每台机器上的搜索在输入数据集规模上具有亚线性复杂度。
第 6 节 FLANN 库
本文所呈现的工作已公开发布为名为 Fast Library for Approximate Nearest Neighbors 的开源库 [^57]。
FLANN 被大量研究与工业项目使用（例如， [60] [^58][^59] [^60][^61]），并因其被包含在 OpenCV [^62]（流行的开源计算机视觉库）而在计算机视觉社区得到广泛应用。FLANN 也被其他知名开源项目使用，例如点云库（PCL）和机器人操作系统（ROS） [^60]。FLANN 已被主流 Linux 发行版（如 Debian、Ubuntu、Fedora、Arch、Gentoo 及其衍生版）打包。
第 7 节 结论
本文关注高维空间中快速最近邻搜索的问题，这是许多计算机视觉与机器学习算法中的核心问题，并且往往是这些算法中计算量最大的部分。我们提出并比较了在高维空间进行快速近似搜索时表现最佳的算法：随机化 k-d 树以及新提出的优先搜索 k-means 树。我们还引入了一种用于二进制特征快速近似匹配的新算法。为了解决在处理极大规模数据集时出现的问题，我们提出了一种面向计算集群的分布式最近邻匹配算法。
脚注
. 现代 x86_64 架构的 POPCNT 指令。
. http://phototour.cs.washington.edu/ patches/default.htm.
. http://www.vis.uky.edu/ stewe/ukbench/data/.
. 我们使用了公开可用的 ANN 实现 (http://www.cs.umd.edu/ mount/ANN/) 和 LSH (http://www.mit.edu/ andoni/LSH/)。
. “Algorithm Configuration” 列显示所选算法及其最佳参数（在 kd-tree 的情况下为随机树数量；在 k‑means 树的情况下为分支因子和迭代次数），“Dist Error” 列显示与精确最近邻相比的平均距离误差，“Search Speedup” 显示相对于线性搜索的搜索加速，“Memory Used” 显示树所占用的内存占数据集内存的比例，而 “Build Time” 列显示树构建时间占线性搜索时间的比例。
. http://www.cs.ubc.ca/ research/flann.