On the design space of MapReduce ROLLUP aggregates

We dene and explore the design space of ecient algorithms to compute ROLLUP aggregates, using the MapReduce programming paradigm. Using a modeling approach, we explain 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 nd a \sweet spot" in the parallelism vs. communication

cost trade-o. We complement our work with an experimental approach, wherein we overcome some limitations of the model we use. Our results indicate that ecient ROLLUP aggregates require striking the good balance between parallelism and communication for both one-round and chained algorithms.