when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-18452
URL:

; ;

### Optimal Cache-Aware Suffix Selection

 pdf-format:

### Abstract

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.

### BibTeX - Entry

@InProceedings{franceschini_et_al:LIPIcs:2009:1845,
author =	{Gianni Franceschini and Roberto Grossi and S. Muthukrishnan},
title =	{{Optimal Cache-Aware Suffix Selection}},
booktitle =	{26th International Symposium on Theoretical Aspects of Computer Science},
pages =	{457--468},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-939897-09-5},
ISSN =	{1868-8969},
year =	{2009},
volume =	{3},
editor =	{Susanne Albers and Jean-Yves Marion},
publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},