A New Method to Construct the KD Tree Based on Presorted Results. (23rd December 2020)
- Record Type:
- Journal Article
- Title:
- A New Method to Construct the KD Tree Based on Presorted Results. (23rd December 2020)
- Main Title:
- A New Method to Construct the KD Tree Based on Presorted Results
- Authors:
- Cao, Yu
Wang, Huizan
Zhao, Wenjing
Duan, Boheng
Zhang, Xiaojiang - Other Names:
- Cheng Shi Academic Editor.
- Abstract:
- Abstract : 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 (KNlog2 N) level to O (Nlog2 N) 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.
- Is Part Of:
- Complexity. Volume 2020(2020)
- Journal:
- Complexity
- Issue:
- Volume 2020(2020)
- Issue Display:
- Volume 2020, Issue 2020 (2020)
- Year:
- 2020
- Volume:
- 2020
- Issue:
- 2020
- Issue Sort Value:
- 2020-2020-2020-0000
- Page Start:
- Page End:
- Publication Date:
- 2020-12-23
- Subjects:
- Chaotic behavior in systems -- Periodicals
Complexity (Philosophy) -- Periodicals
003 - Journal URLs:
- https://onlinelibrary.wiley.com/journal/10990526 ↗
http://onlinelibrary.wiley.com/ ↗
https://www.hindawi.com/journals/complexity/ ↗ - DOI:
- 10.1155/2020/8883945 ↗
- Languages:
- English
- ISSNs:
- 1076-2787
- Deposit Type:
- Legaldeposit
- View Content:
- Available online (eLD content is only available in our Reading Rooms) ↗
- Physical Locations:
- British Library DSC - 3364.585500
British Library HMNTS - ELD Digital store - Ingest File:
- 15714.xml