Database Reference
In-Depth Information
Fig. 4.4
COBBLER
main
algorithm
Feature to Row Enumeration Switch.
This operation starts with first creating a
transposed table for the current feature set, such that we have a tuple for each fea-
ture having lower rank than all those in the current feature set; and then performing
row enumeration on the transposed table as in
CARPENTER
.
Row to Feature Enumeration Switch.
This operation creates a conditional table
such that all feature combinations that is a superset of the feature set represented
by the nearest ancestor of the current row enumeration node but a subset of the
feature set of the current row enumeration node can be tested systematically based
on feature enumeration.
The main algorithm of
COBBLER
is shown in Fig.
4.4
.
COBBLER
performs a
recursive computation of conditional tables and conditional transposed tables for
performing a depth-first traversal of the dynamic enumeration tree. Each conditional
table represents a feature enumerated node while each conditional transposed table
represents a row enumerated node.
One more factor to consider here is the switching condition which are used to
decide whether to switch from row enumeration to feature enumeration or vice versa.
The main idea adopted in
COBBLER
is to estimate the enumeration cost for the
subtree at a node and select the smaller one between a feature enumeration subtree
and a row enumeration subtree.
While
COBBLER
takes the best part of both the column and row enumeration ap-
proach and outperforms previous closed frequent pattern mining algorithms, it has not
resolved the inherent complexity barrier for mining large frequent patterns because
smaller patterns still need to be generated before larger ones in both enumeration
approaches.
6
Pattern Merge Approach
To avoid enumerating all the smaller pattern candidates before reaching the larger
ones, a number of algorithms have been proposed which adopt a pattern merge
approach. The general idea is to first mine a set of small frequent patterns, and then
