最近邻搜索|Nearest neighbor search

在许多应用领域，包括：

• 模式识别–特别是光学字符识别
• 统计分类–参见k-最近邻算法
• 计算机视觉
• 计算几何–参见最近的点对问题
• 数据库–例如，基于内容的图像检索
• 编码理论–看最大似然解码
• 数据压缩–见MPEG-2标准
• 机器人传感[2]
• 推荐系统–例如协作过滤
• 网络营销–见上下文广告和行为定位
• DNA测序
• 拼写检查–建议正确拼写
• 抄袭检测
• 预测职业运动员职业道路的相似性。
• 聚类分析–在某种意义上，将一组观测值分配到子集(称为聚类)中，使同一聚类中的观测值相似，通常基于欧几里的距离
• 化学相似性
• 基于采样的运动计划

已经提出了针对NNS各种问题的解决方案。算法的质量和有用性取决于查询的时间复杂性和必须维护的任何搜索数据结构的空间复杂性。它通常被称为维度灾难（curse of dimensionality）非正式观察表明，在高维欧几里得空间中，使用多项预处理和多对数搜索时间没有通用的精确解释。

NNS 最简单的解决方案是计算从查询点到数据库中每个其他点的距离，并保存最好的。在这种算法中，有时被称为天真的方法(暴力算法)，运行时间的复杂性是 O ( d N ) O(dN) O(dN)，其中N是S集合的基数（cardinality）和d是M空间的维数。搜索数据结构不需要维护，因此线性搜索不超过数据库存储的空间复杂性。平均而言，高维空间中简单搜索的性能优于空间划分方法。[3]

自 1970 自20世纪90年代以来，分支定界法已经应用于这个问题。这种方法包括空间索引（spatial index）或者空间访问方法。开发了几种空间划分（space-partitioning）方法来解决 NNS 问题。也许最简单的事情kd 树，它迭代将搜索空间平分为两个 该区域包括父亲区域的一半。通过对每个分支的查询点进行评估，并通过从根到叶遍历树进行查询。根据查询中规定的距离，可能还需要评估可能包括命中的相邻分支。恒定维度查询时间的平均复杂度为 O ( l o g N ) O(log N ) O(logN) [4]在随机分布点的情况下，最坏情况的复杂性是 O ( k N ( 1 ? 1 / k ) ) O ( kN ^(1-1/ k )) O(kN(1?1/k) ) [5] 或者，R-tree数据结构被设计为支持动态最近邻搜索上下文，因为它具有高效的插入和删除算法，例如R*树。[6] R-trees 不仅可以为欧几里德距离生成最近邻，还可以用于其他距离。

在一般度量空间的情况下，分支定界方法称为度量树(metric tree)方法。具体示例包括vp-tree和BK-tree方法。

使用一组取自 3 维空间的点并放入BSP 树中，并给定取自同一空间的查询点，给出了寻找离查询点最近的点云点问题的可能解决方案在下面的算法描述中。

对于树的每个分支，猜测点云中最近的点位于包含查询点的半空间中。情况可能并非如此，但它是一个很好的启发式方法。在递归地解决了猜测半空间问题的所有麻烦之后，现在将这个结果返回的距离与查询点到分区平面的最短距离进行比较。后一个距离是查询点与可能存在于未搜索的半空间中的最近可能点之间的距离。如果这个距离大于前面结果中返回的距离，那么显然不需要搜索另一个半空间。如果有这样的需求，那么就必须费力解决另一半空间的问题，然后将其结果与前一个结果进行比较，然后返回正确的结果。当查询点靠近云时，该算法的性能比线性时间更接近对数时间，因为当查询点与最近的点云点之间的距离接近于零时，该算法只需使用查找查询点作为获取正确结果的关键。然后将其结果与前一个结果进行比较，然后返回正确的结果。当查询点靠近云时，该算法的性能比线性时间更接近对数时间，因为当查询点与最近的点云点之间的距离接近于零时，该算法只需使用查找查询点作为获取正确结果的关键。然后将其结果与前一个结果进行比较，然后返回正确的结果。当查询点靠近云时，该算法的性能比线性时间更接近对数时间，因为当查询点与最近的点云点之间的距离接近于零时，该算法只需使用查找查询点作为获取正确结果的关键。

允许近似最近邻搜索算法返回点，其与查询的距离最多为c乘以从查询到最近点的距离。这种方法的吸引力在于，在许多情况下，近似最近邻几乎与精确邻接一样好。特别是，如果距离测量准确地捕捉到用户的质量，那么距离的微小差异是无关紧要。[7]

近似图方法（例如 HNSW [8]）被认为是近似最近邻搜索的当前最新技术。[8] [9] [10]

这些方法基于邻近邻域图中的贪婪遍历 G ( V , E ) G(V,E) G(V,E)，其中每一点 x i ∈ S x_{i}\in S xi​∈S 与顶点唯一关联 v i ∈ V v_{i}\in V vi​∈V. **在集合S中搜索查询q的最近邻采用在图中搜索顶点的形式 G ( V , E ) G(V,E) G(V,E)。

基本算法 - 贪婪搜索 - 工作如下：

搜索从输入点顶点开始 v i ∈ V v_{i}\in V vi​∈V，通过计算从查询 q到其邻域的每个顶点的距离 v j : ( v i , v j ) ∈ E v_{j}:(v_{i},v_{j})\in E vj​:(vi​,vj​)∈E ，然后找到具有最小距离值的顶点。如果查询与选定顶点之间的距离值小于查询与当前元素之间的距离值，则算法移动到选定顶点，它成为新的输入点。该算法在达到局部最小值时停止：一个顶点，其邻域不包含比顶点本身更接近查询的顶点。

邻近邻域图的概念在多篇文章中得到了利用，包括 Arya 和 Mount 的开创性论文，[11]在 VoroNet 系统中用于平面，[12]在 RayNet 系统中用于平面 E n E ^{n} En , [13]以及在 Metrized Small World [14] 和 HNSW [8]算法中用于具有距离函数的空间的一般情况。在这些作品之前，Toussaint 发表了一篇开创性的论文，其中他介绍了相对邻域图的概念。[15]

局部敏感散列（LSH）是一种基于对点进行操作的距离度量将空间中的点分组为“桶”的技术。在所选度量下彼此靠近的点以高概率映射到同一个桶。[16]

该cover tree具有基于数据集上的一个理论界限加倍不变。搜索时间的界限是 O ( c 12 l o g n ) O ( c^{12} log n ) O(c12logn)，其中c 是数据集的扩展常数。

在高维空间中，树索引结构变得无用，因为无论如何都需要检查越来越多的节点。为了加速线性搜索，存储在 RAM 中的特征向量的压缩版本用于在第一次运行中预过滤数据集。在第二阶段使用来自磁盘的未压缩数据来确定最终候选对象以进行距离计算。[17]

VA 文件方法是基于压缩的搜索的一种特殊情况，其中每个特征组件都被均匀且独立地压缩。多维空间中的最佳压缩技术是矢量量化(VQ)，通过聚类实现。对数据库进行聚类，并检索最“有希望”的聚类。已经观察到对 VA-File、基于树的索引和顺序扫描的巨大收益。[18] [19]还要注意聚类和 LSH 之间的相似之处。

NNS 问题有许多变体，其中最著名的两个是*k-*最近邻搜索和ε-近似最近邻搜索。

k-最近邻搜索识别查询的前k 个最近邻。这种技术通常用于预测分析，以根据其邻居的共识来估计或分类一个点。k最近邻图是其中每个点都连接到它的k 个最近邻的图**。

在某些应用程序中，检索最近邻居的“正确猜测”可能是可以接受的。在这些情况下，我们可以使用一种算法**，该算法不能保证在每种情况下都返回实际的最近邻居，以换取提高速度或节省内存。通常这种算法会在大多数情况下找到最近的邻居，但这在很大程度上取决于被查询的数据集**。

支持近似最近邻搜索的算法包括局部敏感散列、最佳 bin 优先和基于平衡框分解树的搜索。[20]

最近邻距离比率不是将阈值应用于从原始点到挑战者邻居的直接距离，而是根据与前一个邻居的距离的比率来应用阈值。它在CBIR中使用局部特征之间的相似性通过“示例查询”来检索图片。更一般地说，它涉及几个匹配问题。

固定半径近邻是一个问题，即希望在距指定点的给定固定距离内有效地找到欧几里得空间中给定的所有点。假设距离是固定的，但查询点是任意的。

对于某些应用程序（例如熵估计），可能有N 个数据点，并希望知道这N 个点中的每一个的最近邻。当然，这可以通过对每个点运行一次最近邻搜索来实现，但改进的策略将是一种利用这N 个查询之间的信息冗余来产生更有效搜索的算法。举个简单的例子：当找到从点X到点Y的距离时，这也告诉了我们从点Y到点X的距离，因此可以在两个不同的查询中重复使用相同的计算。

给定一个固定维度，一个半定正范数（因此包括每个 L p范数），以及这个空间中的n个点，每个点的最近邻可以在 O ( n l o g n ) O ( n logn ) O(nlogn) 时间内找到，并且m 个最近邻每个点都可以在 O ( m n l o g n ) O (mn log n ) O(mnlogn) 时间内找到。[21] [22]

• 球树
• 最近的点对问题
• 聚类分析
• 基于内容的图像检索
• 维度的诅咒
• 数字信号处理
• 降维
• 近邻的固定半径
• 傅里叶分析
• 基于实例的学习
• *k -*最近邻算法
• 线性最小二乘
• 局部敏感散列
• 最小哈希
• 多维分析
• 最近邻插值
• 邻居加入
• 主成分分析
• 范围搜索
• 相似性学习
• 奇异值分解
• 稀疏分布式内存
• 统计距离
• 时间序列
• Voronoi 图
• 小波

1. Cayton, Lawerence (2008). “Fast nearest neighbor retrieval for bregman divergences”. Proceedings of the 25th International Conference on Machine Learning. pp. 112–119. doi:10.1145/1390156.1390171. ISBN 9781605582054. S2CID 12169321.
2. Jump up to:a b Bewley, A.; Upcroft, B. (2013). Advantages of Exploiting Projection Structure for Segmenting Dense 3D Point Clouds (PDF). Australian Conference on Robotics and Automation.
3. Weber, Roger; Schek, Hans-J.; Blott, Stephen (1998). “A quantitative analysis and performance study for similarity search methods in high dimensional spaces” (PDF). VLDB '98 Proceedings of the 24rd International Conference on Very Large Data Bases. pp. 194–205.
4. Andrew Moore. “An introductory tutorial on KD trees” (PDF). Archived from the original (PDF) on 2016-03-03. Retrieved 2008-10-03.
5. Lee, D. T.; Wong, C. K. (1977). “Worst-case analysis for region and partial region searches in multidimensional binary search trees and balanced quad trees”. Acta Informatica. 9 (1): 23–29. doi:10.1007/BF00263763. S2CID 36580055.
6. Roussopoulos, N.; Kelley, S.; Vincent, F. D. R. (1995). “Nearest neighbor queries”. Proceedings of the 1995 ACM SIGMOD international conference on Management of data – SIGMOD '95. p. 71. doi:10.1145/223784.223794. ISBN 0897917316.
7. Andoni, A.; Indyk, P. (2006-10-01). “Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions”. 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS’06). pp. 459–468. CiteSeerX 10.1.1.142.3471. doi:10.1109/FOCS.2006.49. ISBN 978-0-7695-2720-8.
8. Jump up to:a b c Malkov, Yury; Yashunin, Dmitry (2016). “Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs”. arXiv:1603.09320 [cs.DS].
9. “New approximate nearest neighbor benchmarks”.
10. “Approximate Nearest Neighbours for Recommender Systems”.
11. Arya, Sunil; Mount, David (1993). “Approximate Nearest Neighbor Queries in Fixed Dimensions”. Proceedings of the Fourth Annual {ACM/SIGACT-SIAM} Symposium on Discrete Algorithms, 25–27 January 1993, Austin, Texas.: 271–280.
12. Olivier, Beaumont; Kermarrec, Anne-Marie; Marchal, Loris; Rivière, Etienne (2006). “Voro Net: A scalable object network based on Voronoi tessellations” (PDF). 2007 IEEE International Parallel and Distributed Processing Symposium. RR-5833. pp. 23–29. doi:10.1109/IPDPS.2007.370210. ISBN 1-4244-0909-8. S2CID 8844431.
13. Olivier, Beaumont; Kermarrec, Anne-Marie; Rivière, Etienne (2007). Peer to Peer Multidimensional Overlays: Approximating Complex Structures. Principles of Distributed Systems. 4878. pp. 315–328. CiteSeerX 10.1.1.626.2980. doi:10.1007/978-3-540-77096-1_23. ISBN 978-3-540-77095-4.
14. Malkov, Yury; Ponomarenko, Alexander; Krylov, Vladimir; Logvinov, Andrey (2014). “Approximate nearest neighbor algorithm based on navigable small world graphs”. Information Systems. 45: 61–68. doi:10.1016/j.is.2013.10.006.
15. Toussaint, Godfried (1980). “The relative neighbourhood graph of a finite planar set”. Pattern Recognition. 12 (4): 261–268. Bibcode:1980PatRe…12…261T. doi:10.1016/0031-3203(80)90066-7.
16. A. Rajaraman & J. Ullman (2010). “Mining of Massive Datasets, Ch. 3”.
17. Weber, Roger; Blott, Stephen. “An Approximation-Based Data Structure for Similarity Search” (PDF). S2CID 14613657. Archived from the original (PDF) on 2017-03-04.
18. Ramaswamy, Sharadh; Rose, Kenneth (2007). “Adaptive cluster-distance bounding for similarity search in image databases”. ICIP.
19. Ramaswamy, Sharadh; Rose, Kenneth (2010). “Adaptive cluster-distance bounding for high-dimensional indexing”. TKDE.
20. Arya, S.; Mount, D. M.; Netanyahu, N. S.; Silverman, R.; Wu, A. (1998). “An optimal algorithm for approximate nearest neighbor searching” (PDF). Journal of the ACM. 45 (6): 891–923. CiteSeerX 10.1.1.15.3125. doi:10.1145/293347.293348. S2CID 8193729. Archived from the original (PDF) on 2016-03-03. Retrieved 2009-05-29.
21. Clarkson, Kenneth L. (1983), “Fast algorithms for the all nearest neighbors problem”, 24th IEEE Symp. Foundations of Computer Science, (FOCS '83), pp. 226–232, doi:10.1109/SFCS.1983.16, ISBN 978-0-8186-0508-6, S2CID 16665268.
22. Vaidya, P. M. (1989). “An O(n log n) Algorithm for the All-Nearest-Neighbors Problem”. Discrete and Computational Geometry. 4 (1): 101–115. doi:10.1007/BF02187718.