MM-cubing: Computing iceberg cubes by factorizing the lattice space

Zheng Shao, Jiawei Han, Dong Xin

Research output: Contribution to journalConference article

Abstract

The data cube and iceberg cube computation problem has been studied by many researchers. There are three major approaches developed in this direction: (1) top-down computation, represented by MultiWay array aggregation, which utilizes shared computation and performs well on dense data sets; (2) bottom-up computation, represented by BUC, which takes advantage of Apriori Pruning and performs well on sparse data sets; and (3) integrated top-down and bottom-up computation, represented by Star-Cubing, which takes advantages of both and has high performance in most cases. However, the performance of Star-Cubing degrades in very sparse data sets due to the additional cost introduced by the tree structure. None of the three approaches achieves uniformly high performance on all kinds of data sets. In this paper, we present a new approach that compute Iceberg Cubes by factorizing the lattice space according to the frequency of values. This approach, different from all the previous dimension-based approaches where the importance of data distribution is not recognized, partitions the cube lattice into one dense subspace and several sparse subspaces. With this approach, a new method called MM-Cubing has been developed. MM-Cubing is highly adaptive to dense, sparse or skewed data sets. Our performance study shows that MM-Cubing is efficient and achieves high performance over all kinds of data distributions.

Original languageEnglish (US)
Pages (from-to)213-222
Number of pages10
JournalProceedings of the International Conference on Scientific and Statistical Database Management, SSDBM
Volume16
StatePublished - Oct 25 2004
EventProceedings - 16th International Conference on Scientific and Statistical Databse Management, SSDBM 2004 - Santorini Island, Greece
Duration: Jun 21 2004Jun 23 2004

ASJC Scopus subject areas

  • Software
  • Applied Mathematics

Fingerprint Dive into the research topics of 'MM-cubing: Computing iceberg cubes by factorizing the lattice space'. Together they form a unique fingerprint.

  • Cite this