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

Xin, Dong; Shao, Zheng; Han, Jiawei; Liu, Hongyan

Permalink

https://hdl.handle.net/2142/11115 Copy

Description

Title

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

Author(s)

• Xin, Dong
• Shao, Zheng
• Han, Jiawei
• Liu, Hongyan

Issue Date

2005-10

Keyword(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.

Type of Resource

text

Permalink

http://hdl.handle.net/2142/11115

Copyright and License 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).

Owning Collections