Fast neighbor search by using revised k-d tree
Fast neighbor search by using revised k-d tree
复制标题
使用修正的 k-d 树进行快速邻居搜索
DOI：
10.1016/j.ins.2018.09.012
复制
发表时间：
2019-01-01
影响因子：
8.1
通讯作者：
Du, Jixiang
中科院分区：
文献类型：
--
作者：
Chen, Yewang;Zhou, Lida;Du, Jixiang
利用两种技术，提出了两种新的基于修正k-d树的邻居查询算法，包括范围查询(RNN)和最近邻(NN)查询。第一种技术通过检查节点的单元是否在指定的查询点邻域内或外部来减少不必要的距离计算，另一种技术通过保存子孙节点的索引来减少冗余的访问节点。并用MatLab和C语言实现了算法。MatLab版是对原有的基于k-d树的RNN和NN的改进，C版是对基于缓冲区k-d树的k-近邻查询(KNN)的改进。理论和实验分析表明，所提出的算法分别在低维时显著改善了原始的RNN、NN和KNN。折衷是修正的k-d树的额外空间成本大约是O(αnlog(N))。(C)2018 Elsevier Inc.保留所有权利。
We present two new neighbor query algorithms, including range query (RNN) and nearest neighbor (NN) query, based on revised k-d tree by using two techniques. The first technique is proposed for decreasing unnecessary distance computations by checking whether the cell of a node is inside or outside the specified neighborhood of query point, and the other is used to reduce redundant visiting nodes by saving the indices of descendant points. We also implement the proposed algorithms in Matlab and C. The Matlab version is to improve original RNN and NN which are based on k-d tree, C version is to improve k-Nearest neighbor query (kNN) which is based on buffer k-d tree. Theoretical and experimental analysis have shown that the proposed algorithms significantly improve the original RNN, NN and kNN in low dimension, respectively. The tradeoff is that the additional space cost of the revised k-d tree is approximately O(alpha nlog(n)). (C) 2018 Elsevier Inc. All rights reserved.