Chen, Yewang, Zhou, Lida, Tang, Yi, Singh, Jai Puneet, Bouguila, Nizar ORCID: https://orcid.org/0000000172247940, Wang, Cheng, Wang, Huazhen and Du, Jixiang (2018) Fast Neighbor Search By Using Revised KD Tree. Information Sciences . ISSN 00200255 (In Press)
Preview 
Text (in press, accepted version) (application/pdf)
3MBFastNeighborSearchByUsingRevisedKDTree_2018_InformationSciences.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 kd 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 kd tree, C version is to improve kNearest neighbor query (kNN) which is based on buffer kd 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 kd 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:  kd 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. HarPeled, J.M. Phillips, K. Yi, W. Zhang Nearestneighbor searching under uncertainty ii ACM Transactions on Algorithms (TALG), 13 (1) (2016), p. 3A. Andoni, P. Indyk Nearoptimal hashing algorithms for approximate nearest neighbor in high dimensions Communications of the ACM, 51 (1) (2008), pp. 117122
C.B. Barber, D.P. Dobkin, H. Huhdanpaa The quickhull algorithm for convex hulls
ACM Transactions on Mathematical Software (TOMS), 22 (4) (1996), pp. 469483
M. Bawa, T. Condie, P. Ganesan Lsh forest: selftuning indexes for similarity search Proceedings of the 14th international conference on World Wide Web, ACM (2005), pp. 651660
A. Becker, L. Ducas, N. Gama, T. Laarhoven New directions in nearest neighbor searching with applications to lattice sieving Proceedings of the TwentySeventh Annual ACMSIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics (2016), pp. 1024
J.L. Bentley Multidimensional binary search trees used for associative searching
Communications of the ACM, 18 (9) (1975), pp. 509517
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. 339350
A. Beygelzimer, S. Kakade, J. Langford Cover trees for nearest neighbor Proceedings of the 23rd international conference on Machine learning, ACM (2006), pp. 97104
R.A. Brown Building kd tree in o (knlog n) time Journal of Computer Graphics Techniques., 4 (1) (2015), pp. 5068
J. Cai, Y. Wang, Y. Liu, J.Z. Luo, W. Wei, X. Xu Enhancing network capacity by weakening community structure in scalefree 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. 197207
Y. Chen, J.P. Singh, L. Zhou, N. Bouguila Frs: Fast range search by pruning unnecessary distance computations based on kd tree IEEE International Conference on Data Mining Workshops (2017), pp. 11601165
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 highdimensional 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, 433434 (2018), pp. 649660
R. Cheng, J. Chen, M. Mokbel, C.Y. Chow Probabilistic verifiers: Evaluating constrained nearestneighbor queries over uncertain data IEEE International Conference on Data Engineering (2008), pp. 973982
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. 11121127
M. De Berg, M. Van Kreveld, M. Overmars, O.C. Schwarzkopf Computational geometry
Computational geometry, Springer (2000), pp. 117
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. 75997603
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. 209226
C. Gao, S. Lv, Y. Wei, Z. Wang, X.C. Zheli Liu Msse: 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. 172180
P. He, Z. Deng, C. Gao, X. Wang, J. Li Model approach to grammatical evolution: deepstructured analyzing of model and representation Soft Computing, 21 (18) (2017), pp. 54135423
G.R. Hjaltason, H. Samet Distance browsing in spatial databases ACM Transactions on Database Systems (TODS), 24 (2) (1999), pp. 265318
H. Hu, D.L. Lee Range nearestneighbor query IEEE Transactions on Knowledge and Data Engineering, 18 (1) (2006), pp. 7891
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. 645657
H. Jegou, M. Douze, C. Schmid Product quantization for nearest neighbor search IEEE Transactions on Pattern Analysis And Machine Intelligence, 33 (1) (2011), pp. 117128
B. Leibe, K. Mikolajczyk, B. Schiele Efficient clustering and matching for object class recognition. BMVC (2006), pp. 789798
J. Li, Z. Liu, X. Chen, F. Xhafa, X. Tan, D.S. Wong Lencdb: A lightweight framework for privacypreserving data queries in cloud computing KnowledgeBased Systems, 79 (2015), pp. 1826
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. 5162
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. 22272240
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. 397405
M. Muja, D.G. Lowe Fast approximate nearest neighbors with automatic algorithm configuration VISAPP (1), 2 (331340) (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. 22272240
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. 18
A. Reiss, D. Stricker Introducing a new benchmarked dataset for activity monitoring
2012 16th International Symposium on Wearable Computers, IEEE (2012), pp. 108109
A. Rodriguez, A. Laio Clustering by fast search and find of density peaks Science, 344 (6191) (2014), pp. 14921496
G. Schindler, M. Brown, R. Szeliski Cityscale location recognition IEEE Conference on Computer Vision and Pattern Recognition (2007), pp. 17
C. SilpaAnan, R. Hartley Optimised kdtrees for fast image descriptor matching IEEE Conference on Computer Vision and Pattern Recognition (2008), pp. 18
J.E. Stone, D. Gohara, G. Shi Opencl: A parallel programming standard for heterogeneous computing systems Computing in science & engineering, 12 (3) (2010), pp. 6673
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. 287298
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. 95106
J. Wang, N. Wang, Y. Jia, J. Li, G. Zeng, H. Zha, X.S. Hua Trinaryprojection trees for approximate nearest neighbor search IEEE Transactions on Pattern Analysis And Machine Intelligence, 36 (2) (2014), pp. 388403
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. 431447
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. 9099
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 paircounting similarity measures for clustering and cluster ensembles IEEE Access (5) (2017), pp. 1690416918
Y. Zhang, N. Wang, S. Zhang, J. Li, X. Gao Fast face sketch synthesis via kdtree search European Conference on Computer Vision, Springer (2016), pp. 6477
Z. Zhou, M. Dong, K. Ota, G. Wang, L.T. Yang Energyefficient resource allocation for d2d communications underlaying cloudranbased ltea networks IEEE Internet of Things Journal, 3 (3) (2016), pp. 428438
Y. Zhu, Y. Zhang, X. Li, J.L. Hongyang Yan Improved collusionresisting secure nearest neighbor query over encrypted data in cloud Concurrency and Computation: Practice and Experience, (2018)
Repository Staff Only: item control page