2026-07-20T05:27:35Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:1845 2024-03-06T10:33:12Z ddc:004 open_access

Optimal Cache-Aware Suffix Selection Franceschini, Gianni Grossi, Roberto Muthukrishnan, S. Given string $S[1..N]$ and integer $k$, the {\em suffix selection} problem is to determine the $k$th lexicographically smallest amongst the suffixes $S[i\ldots N]$, $1 \leq i \leq N$. We study the suffix selection problem in the cache-aware model that captures two-level memory inherent in computing systems, for a \emph{cache} of limited size $M$ and block size $B$. The complexity of interest is the number of block transfers. We present an optimal suffix selection algorithm in the cache-aware model, requiring $\Theta\left(N/B\right)$ block transfers, for any string $S$ over an unbounded alphabet (where characters can only be compared), under the common tall-cache assumption (i.e. $M=\Omega\left(B^{1+\epsilon}\right)$, where $\epsilon<1$). Our algorithm beats the bottleneck bound for permuting an input array to the desired output array, which holds for nearly any nontrivial problem in hierarchical memory models. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Gianni Franceschini and Roberto Grossi and S. Muthukrishnan 2009 Is Part Of LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2009.1845 urn:nbn:de:0030-drops-18452 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1845 eng https://creativecommons.org/licenses/by-nd/3.0/legalcode