Parallel multiple selection by regular sampling

Abstract

In this paper we present a deterministic parallel algorithm solving the multiple selection problem in congested clique model. In this problem for given set of elements S and a set of ranks $K=\{k_1,k_2,...,k_r\}$ we are asking for the $k_i$-th smallest element of $S$ for $1\le i\le r$. The presented algorithm is deterministic, time optimal , and needs $O({\log }_{r+1}^{\ast }(n))$ communication rounds, where $n$ is the size of the input set, and $r$ is the size of the rank set. This algorithm may be of theoretical interest, as for $r=1$ (classic selection problem) it gives an improvement in the asymptotic synchronization cost over previous $O(\log \log p)$ communication rounds solution, where $p$ is size of clique.