| Optimal Cache-Aware Suffix Selection (2009) | |||||||||||||
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[ildots 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 $Thetaleft(N/Bright)$ 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=Omegaleft(B^{1+epsilon}right)$, where $epsilon. @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 (STACS 2009)}, pages = {457--468}, series = {Leibniz International Proceedings in Informatics}, year = {2009}, volume = {3}, editor = {Susanne Albers and Jean-Yves Marion}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany}, address = {Dagstuhl, Germany}, URL = {http://drops.dagstuhl.de/opus/volltexte/2009/1845}, URN = {urn:nbn:de:0030-drops-18452}, annote = {Keywords: } } | |||||||||||||
Details der Publikation | |||||||||||||
| |||||||||||||