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.
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: | 29 Oct 2023 08:06 |
| 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 |
Dimensions
Dimensions
