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.


PostScript version of the paper