Coarse Grained Parallel Selection

2017/12/04 by Boxer, Laurence
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1712.00870

Abstract

We analyze the running time of the Saukas-Song algorithm for selection on a coarse grained multicomputer without expressing the running time in terms of communication rounds. This shows that while in the best case the Saukas-Song algorithm runs in asymptotically optimal time, in general it does not. We propose other algorithms for coarse grained selection that have optimal expected running time.

Related

• Efficient Ranking and Selection in Parallel Computing Environments
• Communication Efficient Algorithms for Top-k Selection Problems
• Distributed Selection in O ( log n ) Time with O ( n log log n ) Messages
• Parallel multiple selection by regular sampling
• Dualheap Selection Algorithm: Efficient, Inherently Parallel and Somewhat Mysterious