Files in this item



application/pdfC-Cubing Effici ... egation-Based Checking.pdf (209kB)
(no description provided)PDF


Title:C-Cubing: Efficient Computation of Closed Cubes by Aggregation-Based Checking
Author(s):Xin, Dong; Shao, Zheng; Han, Jiawei; Liu, Hongyan
Subject(s):computer science
Abstract: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.
Issue Date:2005-10
Genre:Technical Report
Other Identifier(s):UIUCDCS-R-2005-2648
Rights Information:You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format, BUT this permission is only for a period of 45 (forty-five) days from the most recent time that you verified that this technical report is still available from the University of Illinois at Urbana-Champaign Computer Science Department under terms that include this permission. All other rights are reserved by the author(s).
Date Available in IDEALS:2009-04-20

This item appears in the following Collection(s)

Item Statistics