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 = Ω (B1+∈), 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. © G. Franceschini, R. Grossi, and S. Muthukrishnan.
Optimal Cache-Aware Suffix Selection / FRANCESCHINI, GIANNI; ROBERTO, GROSSI; S., MUTHUKRISHNAN. - ELETTRONICO. - 3(2009), pp. 457-468. ((Intervento presentato al convegno STACS tenutosi a Freiburg; Germany nel February 26-28 [10.4230/LIPIcs.STACS.2009.1845].
Titolo: | Optimal Cache-Aware Suffix Selection | |
Autori: | ||
Data di pubblicazione: | 2009 | |
Citazione: | Optimal Cache-Aware Suffix Selection / FRANCESCHINI, GIANNI; ROBERTO, GROSSI; S., MUTHUKRISHNAN. - ELETTRONICO. - 3(2009), pp. 457-468. ((Intervento presentato al convegno STACS tenutosi a Freiburg; Germany nel February 26-28 [10.4230/LIPIcs.STACS.2009.1845]. | |
Handle: | http://hdl.handle.net/11573/58694 | |
ISBN: | 9783939897095 | |
Appartiene alla tipologia: | 04b Atto di convegno in volume |