NPAC Technical Report SCCS-753
Parallel Construction of Multidimensional Binary Search Trees
Ibraheem Al-furaih, Srinivas Aluru, Sanjay Goil, Sanjay Ranka
Submitted January 31 1996
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 present several algorithms for parallel k-d tree
construction and analyze them theoretically and experimentally. We have
implemented our algorithms on the CM-5 and report on the experimental
results.