Database Reference
In-Depth Information
Fig. 2.14
The depth first
strategy
of the
DepthProject
algorithm is that the projection is performed only when the
transaction database reduces by a certain size. This is the
ProjectionCondition
in
Fig.
2.14
.
Most of the nodes in the lexicographic tree correspond to the lower levels. Thus,
the counting times at these levels account for most of the CPU times of the algorithm.
For these levels, a strategy called bucketing can substantially improve the counting
times. The idea is to change the counting technique at a node in the lexicographic
tree, if
is less than a certain value. In this case, an upper bound on the number
of distinct
projected
transactions is 2
|
E
(
P
)
|
. Thus, for example, when
|
E
(
P
)
|
is nine,
then there are only 512 distinct projected transactions at the node
P
. Clearly, this is
because the projected database contains several repetitions of the same (projected)
|
E
(
P
)
|
