Parallel construction of multidimensional binary search trees |
| |
Authors: | Al-Furajh I. Aluru S. Goil S. Ranka S. |
| |
Affiliation: | Dept. of Electr. Eng. & Comput. Sci., Syracuse Univ., NY; |
| |
Abstract: | Multidimensional binary search tree (abbreviated k-d tree) is a popular data structure for the organization and manipulation of spatial data. The data structure is useful in several applications including graph partitioning, hierarchical applications such as molecular dynamics and n-body simulations, and databases. In this paper, we study efficient parallel construction of k-d trees on coarse-grained distributed memory parallel computers. We consider several algorithms for parallel k-d tree construction and analyze them theoretically and experimentally, with a view towards identifying the algorithms that are practically efficient. We have carried out detailed implementations of all the algorithms discussed on the CM-5 and report on experimental results |
| |
Keywords: | |
|
|