形式上,最近邻(NN)搜索问题定义如下:给定空间M中的一组点S和查询点q ∈ M,找到S 中与q的最近点。唐纳德·高德纳( Donald Knuth )在 The Art of Computer Programming (1973)的第3 篇将其称为邮局问题(post-office problem),指的是为住宅分配最近的邮局的应用程序。这个问题的直接概括是k -NN 搜索,我们需要找到k 个最近点。
在具有小的固定维度的空间中搜索最近邻|Nearest neighbor search in spaces with small intrinsic dimension
该cover tree具有基于数据集上的一个理论界限加倍不变。搜索时间的界限是
O ( c^{12} log n )
,其中c 是数据集的扩展常数。
投影径向搜索|Projected radial search
在数据是几何点的密集 3D 地图的特殊情况下,传感技术的投影几何可用于显着简化搜索问题。这种方法要求 3D 数据通过对二维网格的投影进行组织,并假设数据在除对象边界之外的相邻网格单元之间是空间平滑的。这些假设在处理诸如测量、机器人和立体视觉等应用中的 3D 传感器数据时是有效的,但通常不适用于无组织的数据。在实践中,该技术对knn问题的平均搜索时间为
给定一个固定维度,一个半定正范数(因此包括每个 L p范数),以及这个空间中的n个点,每个点的最近邻可以在
O ( n logn )
时间内找到,并且m 个最近邻每个点都可以在
O (mn log n )
时间内找到。[21] [22]
相关
球树
最近的点对问题
聚类分析
基于内容的图像检索
维度的诅咒
数字信号处理
降维
近邻的固定半径
傅里叶分析
基于实例的学习
*k -*最近邻算法
线性最小二乘
局部敏感散列
最小哈希
多维分析
最近邻插值
邻居加入
主成分分析
范围搜索
相似性学习
奇异值分解
稀疏分布式内存
统计距离
时间序列
Voronoi 图
小波
参考文献
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.
Jump up to:ab Bewley, A.; Upcroft, B. (2013). Advantages of Exploiting Projection Structure for Segmenting Dense 3D Point Clouds (PDF). Australian Conference on Robotics and Automation.
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.
Andrew Moore. "An introductory tutorial on KD trees" (PDF). Archived from the original (PDF) on 2016-03-03. Retrieved 2008-10-03.
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.
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.
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.
Jump up to:abc Malkov, Yury; Yashunin, Dmitry (2016). "Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs". arXiv:1603.09320 [cs.DS].
"New approximate nearest neighbor benchmarks".
"Approximate Nearest Neighbours for Recommender Systems".
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.
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.
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.
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.
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.
A. Rajaraman & J. Ullman (2010). "Mining of Massive Datasets, Ch. 3".
Weber, Roger; Blott, Stephen. "An Approximation-Based Data Structure for Similarity Search" (PDF). S2CID 14613657. Archived from the original (PDF) on 2017-03-04.
Ramaswamy, Sharadh; Rose, Kenneth (2007). "Adaptive cluster-distance bounding for similarity search in image databases". ICIP.
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.
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.
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.