A New Method to Construct the KD Tree Based on Presorted Results
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. Howeve...
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2020-01-01
|
| Series: | Complexity |
| Online Access: | http://dx.doi.org/10.1155/2020/8883945 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832560270894956544 |
|---|---|
| author | Yu Cao Huizan Wang Wenjing Zhao Boheng Duan Xiaojiang Zhang |
| author_facet | Yu Cao Huizan Wang Wenjing Zhao Boheng Duan Xiaojiang Zhang |
| author_sort | Yu Cao |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-b0a9685f0052434599b89d4abc5d82ed |
| institution | Kabale University |
| issn | 1076-2787 1099-0526 |
| language | English |
| publishDate | 2020-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Complexity |
| spelling | doaj-art-b0a9685f0052434599b89d4abc5d82ed2025-02-03T01:27:57ZengWileyComplexity1076-27871099-05262020-01-01202010.1155/2020/88839458883945A New Method to Construct the KD Tree Based on Presorted ResultsYu Cao0Huizan Wang1Wenjing Zhao2Boheng Duan3Xiaojiang Zhang4College of Meteorology and Oceanography, National University of Defense Technology, Changsha, Hunan Province, ChinaCollege of Meteorology and Oceanography, National University of Defense Technology, Changsha, Hunan Province, ChinaCollege of Meteorology and Oceanography, National University of Defense Technology, Changsha, Hunan Province, ChinaCollege of Meteorology and Oceanography, National University of Defense Technology, Changsha, Hunan Province, ChinaCollege of Meteorology and Oceanography, National University of Defense Technology, Changsha, Hunan Province, ChinaSearching 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.http://dx.doi.org/10.1155/2020/8883945 |
| spellingShingle | Yu Cao Huizan Wang Wenjing Zhao Boheng Duan Xiaojiang Zhang A New Method to Construct the KD Tree Based on Presorted Results Complexity |
| title | A New Method to Construct the KD Tree Based on Presorted Results |
| title_full | A New Method to Construct the KD Tree Based on Presorted Results |
| title_fullStr | A New Method to Construct the KD Tree Based on Presorted Results |
| title_full_unstemmed | A New Method to Construct the KD Tree Based on Presorted Results |
| title_short | A New Method to Construct the KD Tree Based on Presorted Results |
| title_sort | new method to construct the kd tree based on presorted results |
| url | http://dx.doi.org/10.1155/2020/8883945 |
| work_keys_str_mv | AT yucao anewmethodtoconstructthekdtreebasedonpresortedresults AT huizanwang anewmethodtoconstructthekdtreebasedonpresortedresults AT wenjingzhao anewmethodtoconstructthekdtreebasedonpresortedresults AT bohengduan anewmethodtoconstructthekdtreebasedonpresortedresults AT xiaojiangzhang anewmethodtoconstructthekdtreebasedonpresortedresults AT yucao newmethodtoconstructthekdtreebasedonpresortedresults AT huizanwang newmethodtoconstructthekdtreebasedonpresortedresults AT wenjingzhao newmethodtoconstructthekdtreebasedonpresortedresults AT bohengduan newmethodtoconstructthekdtreebasedonpresortedresults AT xiaojiangzhang newmethodtoconstructthekdtreebasedonpresortedresults |