Pre-computing Shell Fragments For Fast High-dimensional Olap


Recall the reason that we are interested in pre-computing data cubes: Data cubes facilitate fast on-line analytical processing (OLAP) in a multidimensional data space. However, a full data cube of high dimensionality needs massive storage space and unrealistic computation time.

Iceberg cubes provide a more feasible alternative, as we have seen wherein the iceberg condition is used to specify the computation of only a subset of the full cube’s cells. However, although an iceberg cube is smaller and requires less computation time than its corresponding full cube, it is not an ultimate solution. For one, the computation and storage of the iceberg cube can still be costly. For example, if the

Algorithm: Star-Cubing. Compute iceberg cubes by Star-Cubing.


R: a relational table

min support: minimum support threshold for the iceberg condition (taking count as the measure).

Output: The computed iceberg cube.

Method: Each star-tree corresponds to one cuboid tree node, and vice versa.


scan R twice, create star-table S and star-tree T;

output count of T.root;

call starcubing(T, T.root);


procedure starcubing(T, cnode)// cnode: current node


1.       for each non-null child C of T’s cuboid tree

2.       insert or aggregate cnode to the corresponding

3.       position or node in C’s star-tree;

4.       if (cnode.count  min support) then f

5.       if (cnode 6= root) then

6.       output cnode.count;

7.       if (cnode is a leaf) then

8.       output cnode.count;

9.       else { // initiate a new cuboid tree

10.   create CC as a child of T’s cuboid tree;

11.   let TC be CC’s star-tree;

12.   TC:root0s count = cnode:count;

13.   }

14.   }

15.   if (cnode is not a leaf) then

16.   starcubing(T, cnode.first child);

17.   if (CC is not null) then f

18.   starcubing(TC;TC:root);

19.   remove CC from T’s cuboid tree; g

20.   if (cnode has sibling) then

21.   starcubing(T, cnode.sibling);

22.   remove T;

23.   }