We consider the problem of computing the data-cube marginals of a fixed order @math (i.e., all marginals that aggregate over @math dimensions), using a single round of MapReduce. The focus is on the relationship between the reducer size (number of inputs allowed at a single reducer) and the replication rate (number of reducers to which an input is sent). We show that the replication rate is minimized when the reducers receive all the inputs necessary to compute one marginal of higher order. That observation lets us view the problem as one of covering sets of @math dimensions with sets of a larger size @math , a problem that has been studied under the name "covering numbers." We offer a number of constructions that, for different values of @math and @math meet or come close to yielding the minimum possible replication rate for a given reducer size.
@cite_16: Computing interesting measures for data cubes and subsequent mining of interesting cube groups over massive data sets are critical for many important analyses done in the real world. Previous studies have focused on algebraic measures such as SUM that are amenable to parallel computation and can easily benefit from the recent advancement of parallel computing infrastructure such as MapReduce. Dealing with holistic measures such as TOP-K, however, is nontrivial. In this paper, we detail real-world challenges in cube materialization and mining tasks on web-scale data sets. Specifically, we identify an important subset of holistic measures and introduce MR-Cube, a MapReduce-based framework for efficient cube computation and identification of interesting cube groups on holistic measures. We provide extensive experimental analyses over both real and synthetic data. We demonstrate that, unlike existing techniques which cannot scale to the 100 million tuple mark for our data sets, MR-Cube successfully and efficiently computes cubes with holistic measures over billion-tuple data sets.
@cite_16 considers constructing a data cube using a nonassociative aggregation function and also examines how to deal with nonuniformity in the density of tuples in the cube. Like all the other papers mentioned, it deals with constructing the entire data cube using multiple rounds of MapReduce. We consider how to compute only the marginals of one order, using one round. We may assume that locally, at each reducer, higher-order marginals are computed by aggregating lower-order marginals for efficiency, but this method does not result in additional MapReduce rounds.