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

Volume

11

Issue

2

fYear

2000

fDate

2/1/2000 12:00:00 AM

Firstpage

136

Lastpage

148

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;

fLanguage

English

Journal_Title

Parallel and Distributed Systems, IEEE Transactions on

Publisher

ieee

ISSN

1045-9219

Type

jour

DOI

10.1109/71.841750

Filename

841750