Title :
Parallel construction of multidimensional binary search trees
Author :
Al-Furajh, I. ; Aluru, Srinivas ; Goil, Sanjay ; Ranka, Sanjay
Author_Institution :
Dept. of Electr. Eng. & Comput. Sci., Syracuse Univ., NY, USA
fDate :
2/1/2000 12:00:00 AM
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 :
distributed memory systems; hypercube networks; parallel algorithms; tree searching; visual databases; CM-5; coarse-grained distributed memory parallel computers; data structure; databases; graph partitioning; k-d tree; molecular dynamics; multidimensional binary search trees; n-body simulations; parallel construction; parallel k-d tree construction; spatial data; Application software; Binary search trees; Computational modeling; Concurrent computing; Data structures; Multidimensional systems; Partitioning algorithms; Spatial databases; Tree data structures; Tree graphs;
Journal_Title :
Parallel and Distributed Systems, IEEE Transactions on
