Optimal cache-aware suffix selection - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2009

Optimal cache-aware suffix selection

Roberto Grossi
  • Fonction : Auteur
  • PersonId : 857937
S. Muthukrishnan
  • Fonction : Auteur
  • PersonId : 857938

Résumé

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 $\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+\epsilon}}$, 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.
Fichier principal
Vignette du fichier
franceschiniFINAL_new.pdf (274.5 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00359742 , version 1 (10-02-2009)

Identifiants

  • HAL Id : inria-00359742 , version 1
  • ARXIV : 0902.1737

Citer

Gianni Franceschini, Roberto Grossi, S. Muthukrishnan. Optimal cache-aware suffix selection. 26th International Symposium on Theoretical Aspects of Computer Science - STACS 2009, Feb 2009, Freiburg, Germany. pp.457-468. ⟨inria-00359742⟩

Collections

STACS2009
43 Consultations
63 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More