Parallel sorting on a shared-nothing architecture using probabilistic splitting
- 10 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 280-291
- https://doi.org/10.1109/pdis.1991.183115
Abstract
The authors consider the problem of external sorting in a shared-nothing multiprocessor. A critical step in the algorithms the authors consider is to determine the range of sort keys to be handled by each processor. They consider two techniques for determining these ranges of sort keys: exact splitting, using a parallel version of the algorithm proposed by Iyer, Ricard, and Varman; and probabilistic splitting, which uses sampling to estimate quantiles. They present analytic results showing that probabilistic splitting performs better than exact splitting. Finally, the authors present experimental results from an implementation of sorting probabilistic splitting in the Gamma parallel database machine.Keywords
This publication has 15 references indexed in Scilit:
- A comparison of sorting algorithms for the connection machine CM-2Published by Association for Computing Machinery (ACM) ,1991
- FastSort: a distributed single-input single-output external sortPublished by Association for Computing Machinery (ACM) ,1990
- The Gamma database machine projectIEEE Transactions on Knowledge and Data Engineering, 1990
- Parallel sorting methods for large data volumes on a hypercube database computerPublished by Springer Nature ,1989
- Parallel sorting algorithms for tightly coupled multiprocessorsParallel Computing, 1988
- Multi-disk management algorithmsPublished by Association for Computing Machinery (ACM) ,1987
- Design and implementation of the wisconsin storage systemSoftware: Practice and Experience, 1985
- An Adaptive Method for Unknown Distributions in Distributive Partitioned SortingIEEE Transactions on Computers, 1985
- The convoy phenomenonACM SIGOPS Operating Systems Review, 1979
- Sorting by distributive partitioningInformation Processing Letters, 1978