Page 246 -

12-ch05-187-242-9780123814791
2011/6/1
3:19 Page 209
HAN
#23
5.2 Data Cube Computation Methods 209

Algorithm: Star-Cubing. Compute iceberg cubes by Star-Cubing.
Input:
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.

BEGIN
scan R twice, create star-table S and star-tree T;
output count of T.root;
call starcubing(T, T.root);
END

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
position or node in C’s star-tree;
(3) if (cnode.count ≥ min support) then {
(4) if (cnode 6= root) then
(5) output cnode.count;
(6) if (cnode is a leaf) then
(7) output cnode.count;
(8) else { // initiate a new cuboid tree
(9) create C C as a child of T’s cuboid tree;
(10) let T C be C C ’s star-tree;
(11) T C .root’s count = cnode.count;
(12) }
(13) }
(14) if (cnode is not a leaf) then
(15) starcubing(T, cnode.first child);
(16) if (C C is not null) then {
(17) starcubing(T C ,T C .root);
(18) remove C C from T’s cuboid tree; }
(19) if (cnode has sibling) then
(20) starcubing(T, cnode.sibling);
(21) remove T;
}

Figure 5.13 Star-Cubing algorithm.