Review of Three Algorithms That Build k-d Trees
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866915697509007360 |
|---|---|
| author | Brown, Russell A. |
| author_facet | Brown, Russell A. |
| contents | The original description of the k-d tree recognized that rebalancing techniques, such as used to build an AVL tree or a red-black tree, are not applicable to a k-d tree. Hence, in order to build a balanced k-d tree, it is necessary to find the median of a set of data for each recursive subdivision of that set. The sort or selection used to find the median, and the technique used to partition the set about that median, strongly influence the computational complexity of building a k-d tree. This article describes and contrasts three k-d tree-building algorithms that differ in their technique used to partition the set, and compares the performance of the algorithms. In addition, dual-threaded execution is proposed for one of the three algorithms. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_20687 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Review of Three Algorithms That Build k-d Trees Brown, Russell A. Data Structures and Algorithms The original description of the k-d tree recognized that rebalancing techniques, such as used to build an AVL tree or a red-black tree, are not applicable to a k-d tree. Hence, in order to build a balanced k-d tree, it is necessary to find the median of a set of data for each recursive subdivision of that set. The sort or selection used to find the median, and the technique used to partition the set about that median, strongly influence the computational complexity of building a k-d tree. This article describes and contrasts three k-d tree-building algorithms that differ in their technique used to partition the set, and compares the performance of the algorithms. In addition, dual-threaded execution is proposed for one of the three algorithms. |
| title | Review of Three Algorithms That Build k-d Trees |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2506.20687 |