Parallel sorting on a shared-nothing architecture using probabilistic splitting
David J. DeWitt, Jeffrey F. Naughton, Donovan A. Schneider · International Conference on Parallel and Distributed Information Systems · 2002
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.>
Cited by 142 works. doi:10.1109/pdis.1991.183115
Authors
References
- The Gamma database machine project
- The Case for Shared Nothing.
- Multi-disk management algorithms
- Design and implementation of the wisconsin storage system
- Join and Semijoin Algorithms for a Multiprocessor Database Machine
- A comparison of sorting algorithms for the connection machine CM-2
- The convoy phenomenon
- Sorting large files on a backend multiprocessor
- Samplesort: A Sampling Approach to Minimal Storage Tree Sorting
- Sorting by distributive partitioning