Deterministic sorting and randomized median finding on the BSP model

Alexandros Gerbessiotis, Constantinos J. Siniolakis

Research output: Chapter in Book/Report/Conference proceedingConference contribution

34 Scopus citations

Abstract

We present new BSP algorithms for deterministic sorting and randomized median finding. We sort n general keys by using a partitioning scheme that achieves the requirements of efficiency (one-optimality) and insensitivity against data skew (the accuracy of the splitting keys depends solely on the step distance, which can be adapted to meet the worst-case requirements of our application). Although we employ sampling in order to realize efficiency, we can give a precise worst-case estimation of the maximum imbalance which might occur. We also investigate optimal randomized BSP algorithms for the problem of finding the median of n elements that require, with high-probability, 3n/(2p)+o(n/p) number of comparisons, for a wide range of values of n and p. Experimental results for the two algorithms are also presented.

Original languageEnglish (US)
Title of host publicationAnnual ACM Symposium on Parallel Algorithms and Architectures
Editors Anon
Pages223-232
Number of pages10
StatePublished - Dec 1 1996
Externally publishedYes
EventProceedings of the 1996 8th Annual ACM Symposium on Parallel Algorithms and Architectures - Padua, Italy
Duration: Jun 24 1996Jun 26 1996

Other

OtherProceedings of the 1996 8th Annual ACM Symposium on Parallel Algorithms and Architectures
CityPadua, Italy
Period6/24/966/26/96

All Science Journal Classification (ASJC) codes

  • Software
  • Safety, Risk, Reliability and Quality

Fingerprint

Dive into the research topics of 'Deterministic sorting and randomized median finding on the BSP model'. Together they form a unique fingerprint.

Cite this