C-Cubing: Efficient Computation of Closed Cubes by Aggregation-Based Checking

It is well recognized that data cubing often produces huge outputs. Two popular efforts devoted to this problem are (1) iceberg cube, where only significant cells are kept, and (2)closed cube, where a group of cells which preserve roll-up/drill-down semantics are losslessly compressed to one cell. While numerous studies have been reported on the iceberg cube computation, there is only limited work on efficient computation of closed cubes. Previous work on closedness pruning and checking have developed two different approaches, output-based vs. raw-data-bases. While these method either need to check output data or row data, it contribute a lot to the entire computation time. In this paper, we propose an aggregation-based approach, named C-Cubing, to compute closed iceberg cube more efficiently. Using this method, neither the existing output nor the raw data is needed to be checked for closedness. Integrating this method with two successful iceberg cubing algorithms, MMCubing and StarCubing, we propose and implement three algorithms, MMClose, StarClose and StarArray. A through performance study is conducted and shows that this method runs almost one order of magnitude faster then those previous approaches. Finally, how the performance of these algorithms varies with the properties of data set is further demonstrated and analyzed