Database Reference
In-Depth Information
Fig. 2.9
Suffix-based pattern
exploration
3.3.2
VIPER
The
VIPER
algorithm [
58
] uses a vertical approach to mining frequent patterns.
The basic idea in the
VIPER
algorithm is ro represent the vertical database in the
form of compressed bit vectors that are also referred to as
snakes
. These snakes are
then used for efficient counting of the frequent patterns. The different compressed
representation of the
tidlists
provide a number of optimization advantages that are
leveraged by the algorithm. Intrinsically,
VIPER
is not very different from
Eclat
in terms of the basic counting approach. The major difference is in terms of the
choice of the compressed bit vector representation, and the efficient handling of this
representation. Details may be found in [
58
].
4
Recursive Suffix-Based Growth
In these algorithms recursive suffix-based exploration of the patterns is performed.
Note that in most frequent pattern mining algorithms, the enumeration tree (execution
tree) of patterns explores the patterns in the form of a lexicographic tree of itemsets
built on the prefixes. Suffix-based methods use a different convention in which the
suffixes of frequent patterns are extended. As in all projection-based methods, one
only needs to use the transaction database containing itemset
P
in order to count
itemsets that have the suffix
P
. Itemsets are extended from the suffix backwards. In
each iteration, the conditional transaction database (or projected database) of trans-
actions containing the current suffix
P
being explored is an input to the algorithm.
Furthermore, it is assumed that the conditional database contains only frequent ex-
tensions of
P
. For the top-level call, the value of
P
is null, and the frequent items are
determined using a single preprocessing pass that is not shown in the pseudo-code.
Because each item is already known to be frequent, the frequent patterns
{
i
}∪
P
can be immediately generated for each item
i
. The database is projected further
to include only transactions containing
i
, and a recursive call is initiated with the
pattern
∈
T
{
i
}∪
P
. The projected database
T
i
corresponding to transactions containing
{
T
i
. Thus, the transactions
are recursively projected to reflect the addition of an item in the suffix. Thus, this is a
i
}∪
P
is determined. Infrequent items are removed from
