Funnelselect: Cache-Oblivious Multiple Selection



Brodal, GS and Wild, S ORCID: 0000-0002-6061-9177
(2023) Funnelselect: Cache-Oblivious Multiple Selection. In: European Symposium on Algorithms (ESA) 2023, 2023-9-3 - 2023-9-5.

Access the full-text of this item by clicking on the Open Access link.

Abstract

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 r1 < · · · < rq, and returns in sorted order the q input elements of rank r1, . . ., rq, respectively. The algorithm uses expected and with high probability O (∑q+1i=1∆i/B · logM/B N/∆i + N/B ) I/Os, where B is the external memory block size, M ≥ B1+ε is the internal memory size, for some constant ε > 0, and ∆i = ri − ri−1 (assuming r0 = 0 and rq+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.

Item Type: Conference or Workshop Item (Unspecified)
Divisions: Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User: Symplectic Admin
Date Deposited: 12 Sep 2023 07:45
Last Modified: 09 Jun 2024 14:24
DOI: 10.4230/LIPIcs.ESA.2023.25
Open Access URL: https://drops.dagstuhl.de/opus/volltexte/2023/1867...
Related URLs:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3172686