On the design space of MapReduce ROLLUP aggregates

We define and explore the design space of efficient algorithms to compute ROLLUP aggregates, using the MapReduce pro-gramming paradigm. Using a modeling approach, we ex-plain the non-trivial trade-off that exists between parallelism and communication costs that is inherent to a MapReduce implementation of ROLLUP. Furthermore, we design a new family of algorithms that, through a single parameter, allow to find a “sweet spot ” in the parallelism vs. communication cost trade-off. We complement our work with an experimen-tal approach, wherein we overcome some limitations of the model we use. Our results indicate that efficient ROLLUP aggregates require striking the good balance between paral-lelism and communication for both one-round and chained algorithms. 1