Parallel multiple selection by regular sampling

2016/11/17 by Krzysztof Nowicki, Nowicki, Krzysztof
Computer Science · #Complexity and Algorithms in Graphs #Distributed #FOS: Computer and information sciences #Machine Learning and Algorithms #Optimization and Search Problems #Parallel #and Cluster Computing (cs.DC) #cs.DC

paper · pdf · doi:10.48550/arxiv.1611.05549

openalex publication_date 2016/11/17 · arxiv created 2016/11/18 · arxiv updated 2016/11/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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₁ , k₂ , ..., k_r \ we are asking for the k_i-th smallest element of S for 1 ≤ i ≤ r. The presented algorithm is deterministic, time optimal , and needs O(log^*_r+1 (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.

Related

• Parallel Algorithms for Select and Partition with Noisy Comparisons
• Randomized selection with quintary partitions
• Communication Efficient Algorithms for Top-k Selection Problems
• Selection Algorithms with Small Groups
• Multiparty Selection