Mining Long Patterns - Frequent Pattern Mining - page 88

Fig. 4.2 Table transformation
Fig. 4.3 Row enumeration tree
enumeration. Column enumeration works best in data settings with a large number
of rows but a small number of columns as their running time increases exponentially
with increasing average number of columns. However, the growth of bioinformat-
ics has presented datasets which typically contain a large number of columns and
a small number of rows. For example, many gene expression datasets may contain
10,000-100,000 columns but only 100-1000 rows. This has inspired algorithms like
CARPENTER [ 18 ] to explore row enumeration.
CARPENTER discovers frequent closed patterns by performing depth-first row-
wise enumeration instead of the usual column enumeration, and is combined with
efficient search pruning techniques. The algorithm starts with transforming the orig-
inal data table, which corresponds to a column pattern enumeration tree, into a
transposed data table where the rows are the columns in the original table, which
corresponds to a row enumeration tree. Figure 4.2 illustrates the table transformation
and Fig. 4.3 shows the corresponding row enumeration tree.