We study three comparison-based problems related to multisets in the cache-oblivious model: Duplicate elimination, multisorting and finding the most frequent element (the mode). We are interested in minimizing the cache complexity (or number of cache misses) of algorithms for these problems in the context under which cache size and block size are unknown. We give algorithms with cache complexities within a constant factor of the optimal for all the problems. In the case of determining the mode, the optimal algorithm is randomized as the deterministic algorithm differs from the lower bound by a sublogarithmic factor. We can achieve optimality either with a randomized method or if given, along with the input, lg lg of relative frequency of the mode with a constant additive error. © Springer-Verlag Berlin Heidelberg 2005.

Cache-oblivious comparison-based algorithms on multisets / Arash, Farzan; Paolo, Ferragina; Franceschini, Gianni; J., Ian Munro. - STAMPA. - 3669:(2005), pp. 305-316. (Intervento presentato al convegno ESA tenutosi a Palma de Mallorca) [10.1007/11561071_29].

Cache-oblivious comparison-based algorithms on multisets

FRANCESCHINI, GIANNI;
2005

Abstract

We study three comparison-based problems related to multisets in the cache-oblivious model: Duplicate elimination, multisorting and finding the most frequent element (the mode). We are interested in minimizing the cache complexity (or number of cache misses) of algorithms for these problems in the context under which cache size and block size are unknown. We give algorithms with cache complexities within a constant factor of the optimal for all the problems. In the case of determining the mode, the optimal algorithm is randomized as the deterministic algorithm differs from the lower bound by a sublogarithmic factor. We can achieve optimality either with a randomized method or if given, along with the input, lg lg of relative frequency of the mode with a constant additive error. © Springer-Verlag Berlin Heidelberg 2005.
2005
ESA
algorithms; data storage equipment; sorting algorithm
04 Pubblicazione in atti di convegno::04b Atto di convegno in volume
Cache-oblivious comparison-based algorithms on multisets / Arash, Farzan; Paolo, Ferragina; Franceschini, Gianni; J., Ian Munro. - STAMPA. - 3669:(2005), pp. 305-316. (Intervento presentato al convegno ESA tenutosi a Palma de Mallorca) [10.1007/11561071_29].
File allegati a questo prodotto
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/58690
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 0
social impact