Name
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. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1007/11561071_29 | ESA |
Keywords | Field | DocType |
constant factor,cache-oblivious comparison-based algorithm,deterministic algorithm,lg lg,block size,cache size,randomized method,optimal algorithm,constant additive error,cache complexity,sublogarithmic factor,lower bound | Block size,Randomized algorithm,Cache-oblivious algorithm,CPU cache,Cache,Multiset,Computer science,Upper and lower bounds,Parallel computing,Algorithm,Deterministic algorithm | Conference |
Volume | ISSN | ISBN |
3669 | 0302-9743 | 3-540-29118-0 |
Citations | PageRank | References |
2 | 0.42 | 8 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Arash Farzan | 1 | 136 | 11.07 |
| Paolo Ferragina | 2 | 2220 | 130.64 |
| Gianni Franceschini | 3 | 158 | 13.45 |
| J. Ian Munro | 4 | 3010 | 462.97 |