Optimal cache-aware suffix selection

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 $\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.
Type de document :
Communication dans un congrès
Susanne Albers and Jean-Yves Marion. 26th International Symposium on Theoretical Aspects of Computer Science - STACS 2009, Feb 2009, Freiburg, Germany. IBFI Schloss Dagstuhl, pp.457-468, 2009, Proceedings of the 26th Annual Symposium on the Theoretical Aspects of Computer Science
Liste complète des métadonnées

Littérature citée [12 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00359742
Contributeur : Publications Loria <>
Soumis le : mardi 10 février 2009 - 17:20:02
Dernière modification le : mardi 3 octobre 2017 - 15:34:20
Document(s) archivé(s) le : mardi 8 juin 2010 - 19:15:50

Fichiers

franceschiniFINAL_new.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

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

Collections

Citation

Gianni Franceschini, Roberto Grossi, S. Muthukrishnan. Optimal cache-aware suffix selection. Susanne Albers and Jean-Yves Marion. 26th International Symposium on Theoretical Aspects of Computer Science - STACS 2009, Feb 2009, Freiburg, Germany. IBFI Schloss Dagstuhl, pp.457-468, 2009, Proceedings of the 26th Annual Symposium on the Theoretical Aspects of Computer Science. 〈inria-00359742〉

Partager

Métriques

Consultations de la notice

67

Téléchargements de fichiers

117