MM-Cubing: Computing Iceberg Cubes by Factorizing the Lattice Space

Sep 17, 2026

Uploaded by Levi

Data cube and iceberg cube computation is commonly addressed via three dimension-based strategies: top-down MultiWay, bottom-up BUC using Apriori pruning, and integrated StarCubing that mixes both but can degrade on very sparse data because of tree-structure overhead. The paper proposes MM-Cubing, a density-based approach that factorizes the lattice space using value frequencies, splitting it into one dense subspace and multiple sparse subspaces. Experiments show MM-Cubing adapts well to dense, sparse, and skewed data distributions and delivers uniformly high performance.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages10

Reading Time25 min

AccessFree to download

Introduction

Background and prior approaches

Problem definition for iceberg cube computation

Dataset properties and performance comparison

Proposed approach and contribution

Paper organization

MM-Cubing: Computing Iceberg Cubes by Factorizing the Lattice Space¤ Zheng Shao Jiawei Han Dong Xin University of Illinois at Urbana-Champaign, Urbana, IL 61801, USA [zshao1@uiuc.edu](zshao1@uiuc.edu) [hanj@cs.uiuc.edu](hanj@cs.uiuc.edu) [dongxin@uiuc.edu](dongxin@uiuc.edu) 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 [22], which utilizes shared computation and performs well on dense data sets; (2) bottom-up computation, represented by BUC [6], which takes advantage of Apriori Pruning and performs well on sparse data sets; and (3) integrated top-down and bottom-up computation, represented by StarCubing [21], 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 MMCubing has been developed. MM-Cubing is highly adaptive to dense, sparse or skewed data sets. Our performance study shows that MM-Cubing is efﬁcient and achieves high performance over all kinds of data distributions. 1. Introduction Efﬁcient computation of data cubes has been one of the focusing points in research since the introduction of data warehousing, OLAP, and data cube[8] . The previous studies on data cubing mainly fall into 5 categories: (1) computation of full or iceberg cubes with simple or complex measures [1, 22, 15, 6, 9], (2) approximate computation ¤The work was supported in part by National Science Foundation under grants No. IIS-02-09199/IIS-03-08215 . Any opinions, ﬁndings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reﬂect the views of the funding agencies. of compressed data cubes, such as quasi-cubes, wavelet cubes, etc. [4, 19, 16, 5], (3) closed cube computation with index structure, such as condensed, dwarf, or quotient cubes [13, 20, 18], (4) selective materialization of views [11, 3, 17], and (5) cubes computation in stream data for multi-dimensional regression analysis [7] . Among these categories, the ﬁrst one, efﬁcient computation of full or iceberg cubes, is a fundamental problem to the other categories. Any new method developed here may strongly inﬂuence the developments in the other categories. Here is the deﬁnition of cube computation problem: Given a base relation R and n attributes, a cell a =(a1 ; a2 ; : : : ; an ; c) in an n-dimension data cube is a”GROUP BY” with measure c and n distinct attribute values a 1 ; a2 ; : : : ; an. A cell a is called an m-dimensional cell, if and only if there are exactly m (m · n) values among fa1 ; a2 ; : : : ; ang which are not ¤ (¤ is a wildcard for all values) . It is called a base cell ifm = n. Given a base relation, our task is to compute an iceberg cube, i.e., the set of cells which satisﬁes an iceberg condition, or the full cube if thereis no such condition. We study the case that the measure c is the count of base cells, and min sup (threshold) is the iceberg condition. We observed that any dataset could be classiﬁed into one of the following categories: dense, sparse and skewed (where dense and sparse portions coexist in the same dataset) . Previous studies on cube computation have developed three major approaches, each of which may work well on some kinds of dataset, but not all. The ﬁrst

FAQs

What are the three major existing approaches to iceberg cube computation?

The paper reviews top-down MultiWay, bottom-up BUC with Apriori pruning, and integrated StarCubing. Each approach performs well on some data types but not uniformly across all datasets.

How does MM-Cubing differ from prior dimension-based methods?

MM-Cubing is density-based: it factorizes the lattice space based on the frequency of values (major vs. minor), partitioning it into one dense subspace and several sparse subspaces, each handled with specialized methods.

Why can StarCubing perform poorly on very sparse datasets?

StarCubing introduces additional cost due to its tree structure, which causes performance degradation when data is extremely sparse.

Sep 17, 2026

Uploaded by Levi