Fast neighbor search by using revised k-d tree

被引：70

作者：

Chen, Yewang ^{[1
]}

Zhou, Lida ^{[1
]}

Tang, Yi ^{[2
]}

Singh, Jai Puneet ^{[3
]}

Bouguila, Nizar ^{[4
]}

Wang, Cheng ^{[1
]}

Wang, Huazhen ^{[1
]}

Du, Jixiang ^{[1
]}

机构：

[1] Huaqiao Univ, Coll Comp Sci & Technol, Xiamen 361021, Peoples R China

[2] Guangzhou Univ, Sch Math & Informat Sci, Guangzhou 510006, Guangdong, Peoples R China

[3] Concordia Univ, Concordia Engn & Comp Sci, Montreal, PQ H3G 2W1, Canada

[4] Concordia Univ, Fac Engn & Comp Sci, Concordia Inst Informat Syst Engn, Montreal, PQ H3G 2W1, Canada

来源：

INFORMATION SCIENCES | 2019年 / 472卷

基金：

中国国家自然科学基金;

关键词：

k-d tree; NN; kNN; RNN; APPROXIMATE NEAREST-NEIGHBOR; ALGORITHMS; DATABASES; QUERIES;

D O I：

10.1016/j.ins.2018.09.012

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

080201 [机械制造及其自动化];

摘要：

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.

引用

页码：145 / 162

页数：18

共 49 条

[1]

Nearest-Neighbor Searching Under Uncertainty II [J].