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 r<inf>1</inf> < · · · < r<inf>q</inf>, and returns in sorted order the q input elements of rank r<inf>1</inf>, . . ., r<inf>q</inf>, respectively. The algorithm uses expected and with high probability O (∑q+1<inf>i=1</inf>∆i/B · log<inf>M/B</inf> N/∆i + N/B ) I/Os, where B is the external memory block size, M ≥ B<sup>1+ε</sup> is the internal memory size, for some constant ε > 0, and ∆<inf>i</inf> = ri − r<inf>i−1</inf> (assuming r<inf>0</inf> = 0 and r<inf>q+1</inf> = 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 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 2025 14:36 |
| DOI: | 10.4230/LIPIcs.ESA.2023.25 |
| Open Access URL: | https://drops.dagstuhl.de/opus/volltexte/2023/1867... |
| Related Websites: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3172686 |
Altmetric
Altmetric