Optimal cache-aware suffix selection
| dc.creator | Franceschini, Gianni | |
| dc.creator | Grossi, Roberto | |
| dc.creator | Muthukrishnan, S. | |
| dc.date | 2009-02-10 | |
| dc.date.accessioned | 2026-07-07T12:39:57Z | |
| dc.date.available | 2026-07-07T12:39:57Z | |
| dc.description | 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... 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 $\Thetah{N/B}$ 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=\Omegah{B^{1+ε}}$, where $ε<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. | |
| dc.identifier | https://arxiv.org/abs/0902.1737 | |
| dc.identifier | http://arxiv.org/abs/0902.1737 | |
| dc.identifier | 26th International Symposium on Theoretical Aspects of Computer Science - STACS 2009 (2009) 457-468 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/219299 | |
| dc.subject | Data Structures and Algorithms | |
| dc.subject | Hardware Architecture | |
| dc.title | Optimal cache-aware suffix selection | |
| dc.type | text |