2026-08-07T12:10:52Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18678 2024-03-06T11:02:26Z ddc:004 open_access

Funnelselect: Cache-Oblivious Multiple Selection Brodal, Gerth Stølting Wild, Sebastian Multiple selection cache-oblivious algorithm randomized algorithm entropy bounds We present the algorithm funnelselect, the first optimal randomized cache-oblivious algorithm for the multiple-selection problem. The algorithm takes as input an unsorted array of N elements and q query ranks r_1 < ⋯ < r_q, and returns in sorted order the q input elements of rank r_1, …, r_q, respectively. The algorithm uses expected and with high probability O(∑_{i = 1}^{q+1} Δ_i/B ⋅ log_{M/B} N/(Δ_i) + N/B) I/Os, where B is the external memory block size, M ≥ B^{1+ε} is the internal memory size, for some constant ε > 0, and Δ_i = r_i - r_{i-1} (assuming r_0 = 0 and r_{q+1} = N + 1). This is the best possible I/O bound in the cache-oblivious and external memory models. The result is achieved by reversing the computation of the cache-oblivious sorting algorithm funnelsort by Frigo, Leiserson, Prokop and Ramachandran [FOCS 1999], using randomly selected pivots for distributing elements, and pruning computations that with high probability are not expected to contain any query ranks. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Gerth Stølting Brodal and Sebastian Wild 2023 Is Part Of LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2023.25 urn:nbn:de:0030-drops-186789 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.25 eng https://creativecommons.org/licenses/by/4.0/legalcode