Optimal Cache-Aware Suffix Selection

Gianni Franceschini, Roberto Grossi & S. Muthukrishnan
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...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.