### Abstract

Given string S[1⋯N] and integer k, the suffix selection problem is to determine the kth lexicographically smallest amongst the suffixes S[i ⋯ N], 1 ≤ i ≤ N. We study the suffix selection problem in the cache-aware model that captures two-level memory inherent in computing systems, for a 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 θ (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 = Ω (B^{1+∈}), where ∈ < 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.

Original language | English (US) |
---|---|

Title of host publication | STACS 2009 - 26th International Symposium on Theoretical Aspects of Computer Science |

Pages | 457-468 |

Number of pages | 12 |

State | Published - 2009 |

Event | 26th International Symposium on Theoretical Aspects of Computer Science, STACS 2009 - Freiburg, Germany Duration: Feb 26 2009 → Feb 28 2009 |

### Publication series

Name | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|

Volume | 3 |

ISSN (Print) | 1868-8969 |

### Conference

Conference | 26th International Symposium on Theoretical Aspects of Computer Science, STACS 2009 |
---|---|

Country | Germany |

City | Freiburg |

Period | 2/26/09 → 2/28/09 |

### ASJC Scopus subject areas

- Software

## Fingerprint Dive into the research topics of 'Optimal cache-aware suffix selection'. Together they form a unique fingerprint.

## Cite this

*STACS 2009 - 26th International Symposium on Theoretical Aspects of Computer Science*(pp. 457-468). (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 3).