{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,5]],"date-time":"2025-11-05T11:19:17Z","timestamp":1762341557681,"version":"3.37.3"},"reference-count":20,"publisher":"Wiley","license":[{"start":{"date-parts":[[2020,12,22]],"date-time":"2020-12-22T00:00:00Z","timestamp":1608595200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"National Key R&D Program of China","award":["2018YFC1406202","41830964"],"award-info":[{"award-number":["2018YFC1406202","41830964"]}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["2018YFC1406202","41830964"],"award-info":[{"award-number":["2018YFC1406202","41830964"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Complexity"],"published-print":{"date-parts":[[2020,12,22]]},"abstract":"<jats:p>Searching is one of the most fundamental operations in many complex systems. However, the complexity of the search process would increase dramatically in high-dimensional space. K-dimensional (KD) tree, as a classical data structure, has been widely used in high-dimensional vital data search. However, at present, common methods proposed for KD tree construction are either unstable or time-consuming. This paper proposed a new algorithm to construct a balanced KD tree based on presorted results. Compared with previous similar method, the new algorithm could reduce the complexity of the construction process (excluding the presorting process) from O (KNlog2N) level to O (Nlog2N) level, where K is the number of dimensions and N is the number of data. In addition, with the help of presorted results, the performance of the new method is no longer subject to the initial conditions, which expands the application scope of KD tree.<\/jats:p>","DOI":"10.1155\/2020\/8883945","type":"journal-article","created":{"date-parts":[[2020,12,23]],"date-time":"2020-12-23T19:50:18Z","timestamp":1608753018000},"page":"1-7","source":"Crossref","is-referenced-by-count":9,"title":["A New Method to Construct the KD Tree Based on Presorted Results"],"prefix":"10.1155","volume":"2020","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4451-2756","authenticated-orcid":true,"given":"Yu","family":"Cao","sequence":"first","affiliation":[{"name":"College of Meteorology and Oceanography, National University of Defense Technology, Changsha, Hunan Province, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4334-3882","authenticated-orcid":true,"given":"Huizan","family":"Wang","sequence":"additional","affiliation":[{"name":"College of Meteorology and Oceanography, National University of Defense Technology, Changsha, Hunan Province, China"}]},{"given":"Wenjing","family":"Zhao","sequence":"additional","affiliation":[{"name":"College of Meteorology and Oceanography, National University of Defense Technology, Changsha, Hunan Province, China"}]},{"given":"Boheng","family":"Duan","sequence":"additional","affiliation":[{"name":"College of Meteorology and Oceanography, National University of Defense Technology, Changsha, Hunan Province, China"}]},{"given":"Xiaojiang","family":"Zhang","sequence":"additional","affiliation":[{"name":"College of Meteorology and Oceanography, National University of Defense Technology, Changsha, Hunan Province, China"}]}],"member":"311","reference":[{"first-page":"902","article-title":"An advanced k nearest neighbor classification algorithm based on kd-tree","author":"W.-F. Hou","key":"1"},{"first-page":"77","article-title":"Parallel SAH k-D tree construction","author":"B. Choi","key":"2"},{"key":"3","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2007.01062.x"},{"key":"4","doi-asserted-by":"publisher","DOI":"10.1145\/361002.361007"},{"key":"5","doi-asserted-by":"publisher","DOI":"10.1137\/15m1026377"},{"first-page":"494","article-title":"PANDA: Extreme scale parallel K-nearest neighbor on distributed architectures","author":"Md. M. A. Patwary","key":"6"},{"key":"7","doi-asserted-by":"publisher","DOI":"10.1145\/355744.355745"},{"key":"8","first-page":"263","article-title":"An algorithm for the organization of information","volume":"146","author":"G. Adelson-velskii","year":"1962","journal-title":"Proceedings of the USSR Academy of Sciences"},{"author":"P. K. Agarwal","key":"9","article-title":"Parallel algorithms for constructing range and nearest-neighbor searching data structures"},{"key":"10","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/5.1.10"},{"key":"11","volume-title":"Introduction to Algorithms","author":"T. H. Cormen","year":"2009","edition":"3rd"},{"issue":"1403","key":"12","first-page":"24","article-title":"Algorithm improvement of two-way merge sort based on OpenMP","volume":"3682","author":"J. Zhang","year":"2015","journal-title":"Applied Mechanics and Materials"},{"key":"13","first-page":"50","article-title":"Building a Balanced k-d Tree in O(kn log n) Time","volume":"4","author":"R. A. Brown","year":"2015","journal-title":"Journal of Computer Graphics Techniques"},{"key":"14","first-page":"71","article-title":"An improved method to build the KD tree based on presorted results","volume-title":"\u201c","author":"Y. Cao"},{"first-page":"29","article-title":"Research on searching algorithms for unstructured grid remapping based on kd tree","author":"Y. Cao","key":"15"},{"issue":"11","key":"16","first-page":"3218","article-title":"Multi-dimensional cloud index based on KD-tree and R-tree","volume":"34","author":"J. He","year":"2014","journal-title":"Journal of Computer Applications"},{"first-page":"2478","article-title":"Dynamic load balancing in parallel kd-tree K-means","author":"G. D. Fatta","key":"17"},{"first-page":"2752","article-title":"Massively parallel KD-tree construction and nearest neighbor search algorithms","author":"L. Hu","key":"18"},{"key":"19","doi-asserted-by":"publisher","DOI":"10.1007\/s10766-018-0571-0"},{"key":"20","doi-asserted-by":"crossref","first-page":"3543","DOI":"10.4028\/www.scientific.net\/AMR.433-440.3543","article-title":"Parallel SAH based KD tree construction algorithm","volume":"433-440","author":"M. Cheng","year":"2012","journal-title":"Advanced Materials Research"}],"container-title":["Complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/downloads.hindawi.com\/journals\/complexity\/2020\/8883945.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/downloads.hindawi.com\/journals\/complexity\/2020\/8883945.xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/downloads.hindawi.com\/journals\/complexity\/2020\/8883945.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,12,23]],"date-time":"2020-12-23T19:50:31Z","timestamp":1608753031000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.hindawi.com\/journals\/complexity\/2020\/8883945\/"}},"subtitle":[],"editor":[{"given":"Shi","family":"Cheng","sequence":"additional","affiliation":[]}],"short-title":[],"issued":{"date-parts":[[2020,12,22]]},"references-count":20,"alternative-id":["8883945","8883945"],"URL":"https:\/\/doi.org\/10.1155\/2020\/8883945","relation":{},"ISSN":["1099-0526","1076-2787"],"issn-type":[{"type":"electronic","value":"1099-0526"},{"type":"print","value":"1076-2787"}],"subject":[],"published":{"date-parts":[[2020,12,22]]}}}