Chen, Yewang, Zhou, Lida, Tang, Yi, Singh, Jai Puneet, Bouguila, Nizar 
ORCID: https://orcid.org/0000-0001-7224-7940, Wang, Cheng, Wang, Huazhen and Du, Jixiang
(2018)
Fast Neighbor Search By Using Revised K-D Tree.
Information Sciences
.
ISSN 00200255
(In Press)
Preview |
Text (in press, accepted version) (application/pdf)
3MBFast-Neighbor-Search-By-Using-Revised-K-D-Tree_2018_Information-Sciences.pdf - Accepted Version Available under License Spectrum Terms of Access. |
Official URL: http://dx.doi.org/10.1016/j.ins.2018.09.012
Abstract
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(αnlog (n)).
| Divisions: | Concordia University > Gina Cody School of Engineering and Computer Science > Concordia Institute for Information Systems Engineering |
|---|---|
| Item Type: | Article |
| Refereed: | Yes |
| Authors: | Chen, Yewang and Zhou, Lida and Tang, Yi and Singh, Jai Puneet and Bouguila, Nizar and Wang, Cheng and Wang, Huazhen and Du, Jixiang |
| Journal or Publication: | Information Sciences |
| Date: | 6 September 2018 |
| Funders: |
|
| Digital Object Identifier (DOI): | 10.1016/j.ins.2018.09.012 |
| Keywords: | k-d tree; NN; kNN; RNN |
| ID Code: | 984418 |
| Deposited By: | Monique Lane |
| Deposited On: | 20 Sep 2018 20:28 |
| Last Modified: | 06 Sep 2020 00:00 |
References:
P.K. Agarwal, B. Aronov, S. Har-Peled, J.M. Phillips, K. Yi, W. Zhang Nearest-neighbor searching under uncertainty ii ACM Transactions on Algorithms (TALG), 13 (1) (2016), p. 3A. Andoni, P. Indyk Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions Communications of the ACM, 51 (1) (2008), pp. 117-122
C.B. Barber, D.P. Dobkin, H. Huhdanpaa The quickhull algorithm for convex hulls
ACM Transactions on Mathematical Software (TOMS), 22 (4) (1996), pp. 469-483
M. Bawa, T. Condie, P. Ganesan Lsh forest: self-tuning indexes for similarity search Proceedings of the 14th international conference on World Wide Web, ACM (2005), pp. 651-660
A. Becker, L. Ducas, N. Gama, T. Laarhoven New directions in nearest neighbor searching with applications to lattice sieving Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics (2016), pp. 10-24
J.L. Bentley Multidimensional binary search trees used for associative searching
Communications of the ACM, 18 (9) (1975), pp. 509-517
T. Bernecker, T. Emrich, H.-P. Kriegel, N. Mamoulis, M. Renz, A. Züfle A novel probabilistic pruning approach to speed up similarity queries in uncertain databases IEEE International Conference on Data Engineering (2011), pp. 339-350
A. Beygelzimer, S. Kakade, J. Langford Cover trees for nearest neighbor Proceedings of the 23rd international conference on Machine learning, ACM (2006), pp. 97-104
R.A. Brown Building kd tree in o (knlog n) time Journal of Computer Graphics Techniques., 4 (1) (2015), pp. 50-68
J. Cai, Y. Wang, Y. Liu, J.-Z. Luo, W. Wei, X. Xu Enhancing network capacity by weakening community structure in scale-free network Future Generation Computer Systems. DOI: 10.1016/j.future.2017.08.014 (2017)
Y. Cao, Z. Zhou, X. Sun, C. Gao Coverless information hiding based on the molecular structure images of material Computers Materials & Continua, 54 (2) (2015), pp. 197-207
Y. Chen, J.P. Singh, L. Zhou, N. Bouguila Frs: Fast range search by pruning unnecessary distance computations based on k-d tree IEEE International Conference on Data Mining Workshops (2017), pp. 1160-1165
Y. Chen, S. Tang, N. Bouguila, C. Wang, J. Du, H.L. Li A fast clustering algorithm based on pruning unnecessary distance computations in dbscan for high-dimensional data
Pattern Recognition (2018 (in press)
Y. Chen, S. Tang, L. Zhou, C. Wang, J. Du, T. Wang, S. Pei Decentralized clustering by finding loose and distributed density cores Information Sciences, 433-434 (2018), pp. 649-660
R. Cheng, J. Chen, M. Mokbel, C.-Y. Chow Probabilistic verifiers: Evaluating constrained nearest-neighbor queries over uncertain data IEEE International Conference on Data Engineering (2008), pp. 973-982
R. Cheng, D.V. Kalashnikov, S. Prabhakar Querying imprecise data in moving object environments IEEE Transactions on Knowledge and Data Engineering, 16 (9) (2004), pp. 1112-1127
M. De Berg, M. Van Kreveld, M. Overmars, O.C. Schwarzkopf Computational geometry
Computational geometry, Springer (2000), pp. 1-17
L. Fan, X. Lei, N. Yang, T.Q. Duong, G.K. Karagiannidis Secrecy cooperative networks with outdated relay selection over correlated fading channels IEEE Transactions on Vehicular Technology, 66 (8) (2017), pp. 7599-7603
J.H. Friedman, J.L. Bentley, R.A. Finkel An algorithm for finding best matches in logarithmic expected time ACM Transactions on Mathematical Software (TOMS), 3 (3) (1977), pp. 209-226
C. Gao, S. Lv, Y. Wei, Z. Wang, X.C. Zheli Liu M-sse: An effective searchable symmetric encryption with enhanced security for mobile devices IEEE ACCESS, (2018)
F. Gieseke, J. Heinermann, C.E. Oancea, C. Igel Buffer kd trees: Processing massive nearest neighbor queries on gpus. ICML (2014), pp. 172-180
P. He, Z. Deng, C. Gao, X. Wang, J. Li Model approach to grammatical evolution: deep-structured analyzing of model and representation Soft Computing, 21 (18) (2017), pp. 5413-5423
G.R. Hjaltason, H. Samet Distance browsing in spatial databases ACM Transactions on Database Systems (TODS), 24 (2) (1999), pp. 265-318
H. Hu, D.L. Lee Range nearest-neighbor query IEEE Transactions on Knowledge and Data Engineering, 18 (1) (2006), pp. 78-91
Y. Huang, W. Li, Z. Liang, Y. Xue, X. Wang Efficient business process consolidation: combining topic features with structure matching Soft Computing, 22 (2) (2016), pp. 645-657
H. Jegou, M. Douze, C. Schmid Product quantization for nearest neighbor search IEEE Transactions on Pattern Analysis And Machine Intelligence, 33 (1) (2011), pp. 117-128
B. Leibe, K. Mikolajczyk, B. Schiele Efficient clustering and matching for object class recognition. BMVC (2006), pp. 789-798
J. Li, Z. Liu, X. Chen, F. Xhafa, X. Tan, D.S. Wong L-encdb: A lightweight framework for privacy-preserving data queries in cloud computing Knowledge-Based Systems, 79 (2015), pp. 18-26
Y. Li, G. Wang, L. Nie, Q. Wang, W. Tan Distance metric optimization driven convolutional neural network for age invariant face recognition Pattern Recognition, 75 (2018), pp. 51-62
T. Liu, A.W. Moore, A.G. Gray, K. Yang An investigation of practical approximate nearest neighbor algorithms. NIPS, 12 (2004), p. 2004
D.G.L. Marius Muja Scalable nearest neighbor algorithms for high dimensional data IEEE Transactions on Pattern Analysis And Machine Intelligence, 36 (11) (2014), pp. 2227-2240
A.W. Moore The anchors hierarchy: Using the triangle inequality to survive high dimensional data Proceedings of the Sixteenth conference on Uncertainty in artificial intelligence, Morgan Kaufmann Publishers Inc. (2000), pp. 397-405
M. Muja, D.G. Lowe Fast approximate nearest neighbors with automatic algorithm configuration VISAPP (1), 2 (331-340) (2009), p. 2
M. Muja, D.G. Lowe Scalable nearest neighbor algorithms for high dimensional data
IEEE Transactions on Pattern Analysis and Machine Intelligence, 36 (11) (2014), pp. 2227-2240
J. Philbin, O. Chum, M. Isard, J. Sivic, A. Zisserman Object retrieval with large vocabularies and fast spatial matching Computer Vision and Pattern Recognition, IEEE Conference on, IEEE (2007), pp. 1-8
A. Reiss, D. Stricker Introducing a new benchmarked dataset for activity monitoring
2012 16th International Symposium on Wearable Computers, IEEE (2012), pp. 108-109
A. Rodriguez, A. Laio Clustering by fast search and find of density peaks Science, 344 (6191) (2014), pp. 1492-1496
G. Schindler, M. Brown, R. Szeliski City-scale location recognition IEEE Conference on Computer Vision and Pattern Recognition (2007), pp. 1-7
C. Silpa-Anan, R. Hartley Optimised kd-trees for fast image descriptor matching IEEE Conference on Computer Vision and Pattern Recognition (2008), pp. 1-8
J.E. Stone, D. Gohara, G. Shi Opencl: A parallel programming standard for heterogeneous computing systems Computing in science & engineering, 12 (3) (2010), pp. 66-73
Y. Tao, D. Papadias, Q. Shen Continuous nearest neighbor search Proceedings of the 28th international conference on Very Large Data Bases, VLDB Endowment (2002), pp. 287-298
H. Wang, W. Wang, Z. Cui, X. Zhou, J. Zhao, Y. Li A new dynamic firefly algorithm for demand estimation of water resources Information Sciences, 438 (2018), pp. 95-106
J. Wang, N. Wang, Y. Jia, J. Li, G. Zeng, H. Zha, X.-S. Hua Trinary-projection trees for approximate nearest neighbor search IEEE Transactions on Pattern Analysis And Machine Intelligence, 36 (2) (2014), pp. 388-403
Z. Wu, L. Tian, P. Li, T. Wu, M. Jiang, C. Wu Generating stable biometric keys for flexible cloud computing authentication using finger vein Information Sciences (2016), pp. 431-447
L. Yang, Z. Han, Z. Huang, J. Ma A remotely keyed file encryption scheme under mobile cloud computing Journal of Network & Computer Applications (106) (2018), pp. 90-99
P.N. Yianilos Data structures and algorithms for nearest neighbor search in general metric spaces SODA, 93 (1993) 311–21
S. Zhang, Z. Yang, X. Xing, Y. Gao, D. Xie, H.S. Wong Generalized pair-counting similarity measures for clustering and cluster ensembles IEEE Access (5) (2017), pp. 16904-16918
Y. Zhang, N. Wang, S. Zhang, J. Li, X. Gao Fast face sketch synthesis via kd-tree search European Conference on Computer Vision, Springer (2016), pp. 64-77
Z. Zhou, M. Dong, K. Ota, G. Wang, L.T. Yang Energy-efficient resource allocation for d2d communications underlaying cloud-ran-based lte-a networks IEEE Internet of Things Journal, 3 (3) (2016), pp. 428-438
Y. Zhu, Y. Zhang, X. Li, J.L. Hongyang Yan Improved collusion-resisting secure nearest neighbor query over encrypted data in cloud Concurrency and Computation: Practice and Experience, (2018)
All items in Spectrum are protected by copyright, with all rights reserved. The use of items is governed by Spectrum's terms of access.
Repository Staff Only: item control page
Download Statistics
Download Statistics