TY - GEN
T1 - Deterministic Cache-Oblivious Funnelselect
AU - Brodal, Gerth Stølting
AU - Wild, Sebastian
N1 - Publisher Copyright:
© Gerth Stølting Brodal and Sebastian Wild; licensed under Creative Commons License CC-BY 4.0.
PY - 2024/6
Y1 - 2024/6
N2 - 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(Pqi=1+1 ∆Bi · logM/B∆Ni +NB), 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).
AB - 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(Pqi=1+1 ∆Bi · logM/B∆Ni +NB), 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).
KW - cache-oblivious algorithm
KW - entropy bounds
KW - Multiple selection
U2 - 10.4230/LIPIcs.SWAT.2024.17
DO - 10.4230/LIPIcs.SWAT.2024.17
M3 - Article in proceedings
AN - SCOPUS:85195409147
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 19th Scandinavian Symposium on Algorithm Theory, SWAT 2024
A2 - Bodlaender, Hans L.
PB - Dagstuhl Publishing
CY - Wadern
T2 - 19th Scandinavian Symposium on Algorithm Theory, SWAT 2024
Y2 - 12 June 2024 through 14 June 2024
ER -