A New Method to Construct the KD Tree Based on Presorted Results
Joint Authors
Duan, Boheng
Zhao, Wenjing
Cao, Yu
Wang, Huizan
Zhang, Xiaojiang
Source
Issue
Vol. 2020, Issue 2020 (31 Dec. 2020), pp.1-7, 7 p.
Publisher
Hindawi Publishing Corporation
Publication Date
2020-12-23
Country of Publication
Egypt
No. of Pages
7
Main Subjects
Abstract EN
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.
American Psychological Association (APA)
Cao, Yu& Wang, Huizan& Zhao, Wenjing& Duan, Boheng& Zhang, Xiaojiang. 2020. A New Method to Construct the KD Tree Based on Presorted Results. Complexity،Vol. 2020, no. 2020, pp.1-7.
https://search.emarefa.net/detail/BIM-1145140
Modern Language Association (MLA)
Cao, Yu…[et al.]. A New Method to Construct the KD Tree Based on Presorted Results. Complexity No. 2020 (2020), pp.1-7.
https://search.emarefa.net/detail/BIM-1145140
American Medical Association (AMA)
Cao, Yu& Wang, Huizan& Zhao, Wenjing& Duan, Boheng& Zhang, Xiaojiang. A New Method to Construct the KD Tree Based on Presorted Results. Complexity. 2020. Vol. 2020, no. 2020, pp.1-7.
https://search.emarefa.net/detail/BIM-1145140
Data Type
Journal Articles
Language
English
Notes
Includes bibliographical references
Record ID
BIM-1145140