2026-08-15T05:21:48Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20057 2024-05-31T13:11:11Z ddc:004 open_access

Deterministic Cache-Oblivious Funnelselect Brodal, Gerth Stølting Wild, Sebastian Multiple selection cache-oblivious algorithm entropy bounds In the multiple-selection problem one is given an unsorted array S of N elements and an array of q query ranks r_1 < ⋯ < r_q, and the task is to return, in sorted order, the q elements in S of rank r_1, …, r_q, 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(∑_{i = 1}^{q+1} Δ_i/B ⋅ log_{M/B} N/Δ_i + N/B), where B is the external memory block size, M ≥ B^{1+ε} is the internal memory size, for some constant ε > 0, and Δ_i = r_i - r_{i-1} (assuming r_0 = 0 and r_{q+1} = N + 1). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Gerth Stølting Brodal and Sebastian Wild 2024 Is Part Of LIPIcs, Volume 294, 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SWAT.2024.17 urn:nbn:de:0030-drops-200576 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.17 eng https://creativecommons.org/licenses/by/4.0/legalcode