1 Search Results for "Franceschini, Gianni"


Document
Optimal Cache-Aware Suffix Selection

Authors: Gianni Franceschini, Roberto Grossi, and S. Muthukrishnan

Published in: LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (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[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.

Cite as

Gianni Franceschini, Roberto Grossi, and S. Muthukrishnan. Optimal Cache-Aware Suffix Selection. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 457-468, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)


Copy BibTex To Clipboard

@InProceedings{franceschini_et_al:LIPIcs.STACS.2009.1845,
  author =	{Franceschini, Gianni and Grossi, Roberto and Muthukrishnan, S.},
  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 =	{Albers, Susanne and Marion, Jean-Yves},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1845},
  URN =		{urn:nbn:de:0030-drops-18452},
  doi =		{10.4230/LIPIcs.STACS.2009.1845},
  annote =	{Keywords: }
}
  • Refine by Author
  • 1 Franceschini, Gianni
  • 1 Grossi, Roberto
  • 1 Muthukrishnan, S.

  • Refine by Classification

  • Refine by Keyword

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2009

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail