Databases Reference
In-Depth Information
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
f
(1)
foreach
non-null
child C
of
T
's cuboid tree
(2)
insertoraggregate
cnode
to the corresponding
position or node in
C
's star-tree;
(3)
if
(
cnode.count
min support
)
then
f
(4)
if
(cnode 6D root)
then
(5)
output
cnode.count;
(6)
if
(cnode is a leaf)
then
(7)
output
cnode.count;
(8)
else
f // 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
D
cnode
.
count
;
(12)
g
(13) g
(14)
if
(
cnode
is not a leaf)
then
(15)
starcubing(T, cnode.first child)
;
(16)
if
(
C
C
is not null)
then
f
(17)
starcubing
.
T
C
,
T
C
.
root
/;
(18)
remove
C
C
from
T
's cuboid tree; g
(19)
if
(
cnode
has sibling)
then
(20)
starcubing(T, cnode.sibling)
;
(21)
remove
T
;
g
Figure 5.13
Star-Cubing algorithm.
