Optimal cache-aware suffix selection

Details Optimal cache-aware suffix selection Optimal cache-aware suffix selection

2009-02-10

arxiv.org/abs/0902.1737v1

26th International Symposium on Theoretical Aspects of Computer Science - STACS 2009 (2009) 457-468

Computer Science

Data Structures and Algorithms

Scientific paper

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... 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.

Affiliated with

Also associated with

No associations

Rating

Optimal cache-aware suffix selection does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Optimal cache-aware suffix selection, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimal cache-aware suffix selection will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-486729