Catalogo dei prodotti della ricerca
IRIS è la soluzione IT che facilita la raccolta e la gestione dei dati relativi alle attività e ai prodotti della ricerca. Fornisce a ricercatori, amministratori e valutatori gli strumenti per monitorare i risultati della ricerca, aumentarne la visibilità e allocare in modo efficace le risorse disponibili.
EnglishGiven 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 |
File allegati a questo prodotto
Copyright © 2022