Parallel construction of multidimensional binary search trees
Authors:
- S. AluruSAS. Aluru
- S. GoilSGS. Goil
- S. RankaSRS. Ranka
- 1 February 2000
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Parallel and Distributed Systems
- Vol. 11 (2) , 136-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
This publication has 7 references indexed in Scilit:
- Many-to-many personalized communication with bounded traffic2002
- Parallel sorting by regular samplingJournal of Parallel and Distributed Computing, 1992
- Multidimensional Binary Search Trees in Database ApplicationsIEEE Transactions on Software Engineering, 1979
- Finding the medianJournal of Computer and System Sciences, 1976
- Multidimensional binary search trees used for associative searchingCommunications of the ACM, 1975
- Expected time bounds for selectionCommunications of the ACM, 1975
- Time bounds for selectionJournal of Computer and System Sciences, 1973