Brodal, GS and Wild, S 
ORCID: 0000-0002-6061-9177
(2024)
Deterministic Cache-Oblivious Funnelselect.
.
Abstract
In the multiple-selection problem one is given an unsorted array S of N elements and an array of q query ranks r1 < · · · < rq, and the task is to return, in sorted order, the q elements in S of rank r1, . . ., rq, respectively. The asymptotic deterministic comparison complexity of the problem was settled by Dobkin and Munro [JACM 1981]. In the I/O model an optimal I/O complexity was achieved by Hu et al. [SPAA 2014]. Recently [ESA 2023], we presented a cache-oblivious algorithm with matching I/O complexity, named funnelselect, since it heavily borrows ideas from the cache-oblivious sorting algorithm funnelsort from the seminal paper by Frigo, Leiserson, Prokop and Ramachandran [FOCS 1999]. Funnelselect is inherently randomized as it relies on sampling for cheaply finding many good pivots. In this paper we present deterministic funnelselect, achieving the same optimal I/O complexity cache-obliviously without randomization. Our new algorithm essentially replaces a single (in expectation) reversed-funnel computation using random pivots by a recursive algorithm using multiple reversed-funnel computations. To meet the I/O bound, this requires a carefully chosen subproblem size based on the entropy of the sequence of query ranks; deterministic funnelselect thus raises distinct technical challenges not met by randomized funnelselect. The resulting worst-case I/O bound is O(<sup>Pq</sup><inf>i</inf><inf>=1</inf><sup>+1 ∆</sup><inf>B</inf><sup>i</sup> · log<inf>M/B</inf><inf>∆</inf><sup>N</sup><inf>i</inf> +<sup>N</sup><inf>B)</inf>, where B is the external memory block size, M ≥ B<sup>1+ε</sup> is the internal memory size, for some constant ε > 0, and ∆i = ri − ri−1 (assuming r0 = 0 and rq+1 = N + 1).
| Item Type: | Conference Item (Unspecified) |
|---|---|
| Divisions: | Faculty of Science and Engineering Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 26 Sep 2024 15:54 |
| Last Modified: | 09 Jun 2025 14:39 |
| DOI: | 10.4230/LIPIcs.SWAT.2024.17 |
| Open Access URL: | https://doi.org/10.4230/LIPIcs.SWAT.2024.17 |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3184761 |
Altmetric
Altmetric