TCS -TR-A-06-12

TCS Technical ReportZBDD-growth: An Eﬃcient Method for Frequent
Pattern Mining and Knowledge Indexingby

Shin-ichi Minato and Hiroki Arimura

Division of Computer Science
Report Series A
April 10, 2006

Hokkaido University
Graduate School ofInformation Science and Technology
Email:

minato@ist.hokudai.ac.jp

Phone:+81-011-706-7682

Fax:+81-011-706-7682

ZBDD-growth: An Eﬃcient Method for Frequent Pattern Mining andKnowledge Indexing
Shin-ichi Minato

Hiroki Arimura

Division of Computer Science, Hokkaido University
North 14, West 9, Sapporo, 060-0814 Japan

Division of Computer Science, Hokkaido University
North 14, West 9, Sapporo, 060-0814 Japan

April 10, 2006

ever, most of such pattern mining algorithms focused on just enumerating or listing the patterns
which satisfy the given conditions and it was a different matter how to store and index the result of
patterns for eﬃcient data analysis.

(Abstract) Frequent pattern mining is one of thefundamental techniques for knowledge discovery
and data mining. In the last decade, a number
of eﬃcient algorithms for frequent pattern mining
have been presented, but most of them focusedon just enumerating the patterns which satisfy thegiven conditions, and it was a diﬀerent matter how
to store and index the result of patterns for eﬃcient data analysis. In this paper, we propose afast algorithm of extracting all/maximal frequent
patterns from transaction databases and simultaneously indexing the result of huge patterns using Zero-suppressed BDDs (ZBDDs). Our method,ZBDD-growth, is fast as competitive to the existingstate-of-the-art algorithms, and not only enumerating/listing the patterns but also indexing the output data compactly on the memory. After mining,
the result of patterns can eﬃciently be analyzed
by using algebraic operations. The data structuresof BDDs have already been used in VLSI logic design systems successively, but our method will be
the ﬁrst practical work of applying the BDD-based
techniques for data mining area.

1

In this paper, we propose a fast algorithm of extracting all/maximal frequent patterns from transaction databases, and simultaneously indexing theresult of huge patterns on the computer memory
using Zero-suppressed BDDs. Our method does
not only enumerate/list the patterns but also indexes the output data compactly on the memory.
After mining, the result of patterns can eﬃciently
be analyzed by using algebraic operations.
The key of our method is to use BDD-based
data structure for representing sets of patterns.
BDDs[4] are graph-based representation of Booleanfunctions, now widely used in VLSI logic designand veriﬁcation area. For the data mining applications, it is important to use Zero-suppressed BDDs(ZBDDs)[12], a special type of BDDs, which aresuitable for handling large-scale sets of combinations. Using ZBDDs, we can implicitly enumeratecombinatorial item set data and eﬃciently computeset operations over the ZBDDs. The preliminary
idea of using ZBDDs is presented in our last workshop paper[15], and after that we developed a fast
pattern mining algorithm based on this data structure. Our work will be the ﬁrst practical result ofapplying the BDD-based technique for data miningarea.

Introduction

Frequent pattern mining is one of the fundamental
techniques for knowledge discovery and data mining. Since the introduction by Agrawal et al.[1], thefrequent pattern mining and association rule analysis have been received much attentions from many
researchers, and a number of papers have been published about the new algorithms or improvements
for solving such mining problems[7, 9, 19]. How-For a related work, FP-growth[9] is received agreat deal of attention because it supports fast manipulation of large-scale item set data using com1

2

Shin-ichi Minato and Hiroki Arimura

pact tree structure on the main memory. Our
method is a similar approach to handle sets of combinations on the main memory, but will be more
eﬃcient in the following points:

F
a

F

1
0

• ZBDDs are a kind of DAGs for representing
item sets, while FP-growth uses a tree representation for the same objects. In general,
DAGs can be more compact than trees.
• ZBDD-growth uses ZBDDs not only as internal data structure but also as output data
structure. It provides an eﬃcient knowledge
index for consequent analysis.
ZBDD-growth algorithm is based on a recursive
depth-ﬁrst search of the database represented by
ZBDDs. We show two versions of algorithms, generating all frequent patterns and generating maximal ones. Our experimental result shows that
ZBDD-growth is fast as competitive to the existing state-of-the-art algorithms, such as FP-growth.
Especially for the cases where the ZBDD nodes
are well shared, exponential speed up are observed
comparing to the existing algorithms based on explicit table/tree representation.
Recently, the data mining methods are often discussed in the context of Inductive Databases[3, 11],the integrated processes of knowledge discovery. In
this paper, we place the ZBDD-based method as abasis of integrated discovery processes to eﬃciently
execute various operations ﬁnding interest patterns
and analyzing information involved in large-scale
combinatorial item set databases.

2

BDDs
BDDs

and

Zero-suppressed

Here we brieﬂy describe the basic techniques of
BDDs and Zero-suppressed BDDs for representing
sets of combinations eﬃciently.

2.1

BDDs

BDD (Binary Decision Diagram) is a directed
graph representation of the Boolean function, as
illustrated in Fig. 1(a). It is derived by reducing

a

0

0

b

1

b 1

0

b 1

0

1

c

0

1

0

0

1

1

c

c
1 0

1

0

(a) BDD.

1 0

0

1

c
1

0

0

1

c

1

1

(b) Binary tree.

Figure 1: BDD and binary tree: F = (a ∧ b) ∨ c .

x
0

jump
1

f

f

(a) Node deletion.

xx

x share

0 1

0 1

0 1

f0

f1

f0

f1

(b) Node sharing.

Figure 2: Reduction rules of ordinary BDDsa binary tree graph representing recursive Shannon’s expansion, indicated in Fig. 1(b). The following reduction rules yield a Reduced Ordered
BDD (ROBDD), which can eﬃciently represent theBoolean function. (see [4] for details.)• Delete all redundant nodes whose two edges
point to the same node. (Fig. 2(a))• Share all equivalent sub-graphs. (Fig. 2(b))
ROBDDs provide canonical forms for Booleanfunctions when the variable order is ﬁxed. Most
researches on BDDs are based on the above reduction rules. In the following sections, ROBDDs will
be referred to as BDDs (or ordinary BDDs) for thesake of simpliﬁcation.
As shown in Fig. 3, a set of multiple BDDs canbe shared each other under the same ﬁxed variable
ordering. In this way, we can handle a number ofBoolean functions simultaneously in a monolithic
memory space.
Using BDDs, we can uniquely and compactly
represent many practical Boolean functions includ-ZBDD-growth: An Eﬃcient Method for Frequent Pattern Mining and Knowledge Indexing

F1
a

F2
a

1
0

0

F3

1

F4

0

a
1

b
0

0

1

1

b
0

1

F1 = a ∧ b
F2 = a ⊕ b
F3 = b
F4 = a ∨ b

Figure 3: Shared multiple BDDs.

ing AND, OR, parity, and arithmetic adder functions. Using Bryant’s algorithm[4], we can eﬃciently construct a BDD for the result of a binary
logic operation (i.e. AND, OR, XOR), for given apair of operand BDDs. This algorithm is based onhash table techniques, and the computation timeis almost linear to the data size unless the data
overﬂows the main memory. (see [13] for details.)
Based on these techniques, a number of BDD
packages have been developed in 1990’s and widelyused for large-scale Boolean function manipulation,
especially popular in VLSI CAD area.

2.2

3

Sets of Combinations and ZBDDs

BDDs are originally developed for handling
Boolean function data, however, they can also be
used for implicit representation of sets of combinations. Here we call “sets of combinations” for a setof elements each of which is a combination out ofn items. This data model often appears in reallife problems, such as combinations of switching
devices(ON/OFF), fault combinations, and sets ofpaths in the networks.
A combination of n items can be represented by
an n-bit binary vector, (x1 x2 . . . xn ), where each
bit, xk ∈ {1, 0}, expresses whether or not the item
is included in the combination. A set of combinations can be represented by a list of the combination vectors. In other words, a set of combinations
is a subset of the power set of n items.
A set of combinations can be mapped into
Boolean space by using n-input variables for each
bit of the combination vector. If we choose any

Figure 4: Set of combinations and Boolean function.

x
0

f

Jump
1

0

f

Figure 5: ZBDD reduction rule.

one combination vector, a Boolean function determines whether the combination is included in theset of combinations. Such Boolean functions arecalled characteristic functions. For example, Fig. 4
shows a truth-table representing a Boolean function (abc) ∨ (bc), but also represents a set of combination {ab, ac, c}. Using BDDs for characteristic functions, we can implicitly and compactly represent sets of combinations. The logic operations
AND/OR for Boolean functions correspond to theset operations intersection/union for sets of combinations. By using BDDs for characteristic functions, we can manipulate sets of combinations eﬃciently. They can be generated and manipulated
within a time roughly proportional to the BDD
size. When we handle many combinations including similar patterns (sub-combinations), BDDs are
greatly reduced by node sharing eﬀect, and sometimes an exponential reduction beneﬁt can be obtained.
Zero-suppressed BDD (ZBDD)[12, 14] isa special type of BDDs for eﬃcient manipulationof sets of combinations. ZBDDs are based on thefollowing special reduction rules.
• Delete all nodes whose 1-edge directly points

4Shin-ichi Minato and Hiroki Arimura

Figure 6: Eﬀect of ZBDD reduction rule.

deleted by ZBDD reduction rule. In ordinary BDDs, irrelevant nodes still remain andthey may spoil the reduction beneﬁt of sharing
nodes.

Figure 7: Explicit representation by ZBDD.

to the 0-terminal node, and jump through to
the 0-edge’s destination, as shown in Fig. 5.
• Share equivalent nodes as well as ordinary
BDDs.
Notice that we do not delete the nodes whose twoedges point to the same node, which used to bedeleted by the original rule. The zero-suppressed
deletion rule is asymmetric for the two edges, as
we do not delete the nodes whose 0-edge points
to a terminal node. It is proved that ZBDDs arealso gives canonical forms as well as ordinary BDDs
under a ﬁxed variable ordering.
Here we summarize the features of ZBDDs.
• In ZBDDs, the nodes of irrelevant items (neverchosen in any combination) are automaticallyAn example is shown in Fig. 6. In thiscase, the item d is irrelevant, but ordinary
BDD for characteristic function F z(a, b, c)and F z(a, b, c, d) become diﬀerent forms. On
the other hand, ZBDDs for F z(a, b, c) andF z(a, b, c, d) become identical forms and completely shared.
• ZBDDs are especially eﬀective for representing sparse combinations. For instance, sets ofcombinations selecting 10 out of 1000 items
can be represented by ZBDDs up to 100 times
more compact than ordinary BDDs.
• Each path from the root node to the 1-terminal
node corresponds to each combination in theset. Namely, the number of such paths in the
ZBDD equals to the number of combinationsin the set. In ordinary BDDs, this property
does not always hold.
• When no equivalent nodes exist in a ZBDD,
that is the worst case, the ZBDD structure
explicitly stores all items in all combinations,as well as using an explicit linear linked list
data structure. An example is shown in Fig. 7.
Namely, (the order of) ZBDD size never exceeds the explicit representation. If moreZBDD-growth: An Eﬃcient Method for Frequent Pattern Mining and Knowledge Indexing

Table 1: Primitive ZBDD operations“∅”
Returns empty set.
(0-termial
node)
“1”

Returns the set of only nullcombination. (1-terminal node)

P .topReturns the item-ID at the root
node of P .
Selects the subset of combinations
each of which does not include itemv.
Selects the subset of combinations
including item v, and then delete v
from each combination.
Inverts existence of v (add / delete)on each combination.
Returns union set.
Returns intersection set.
Returns diﬀerence set. (in P but
not in Q.)

P .oﬀset(v)P .onset(v)P .change(v)
P ∪Q
P ∩Q
P −Q
P .count

Counts number of combinations.

nodes are shared, the ZBDD is more compact than linear list. Ordinary BDDs havelarger overhead to represent sparser combinations while ZBDDs have no such overhead.
Table 1 shows the most of primitive operationsof ZBDDs. In these operations, ∅, 1, P.top are executed in a constant time, and the others are almost
linear to the size of graph. We can describe various
processing on sets of combinations by composing ofthese primitive operations.

2.3

ZBDD-based Database Analysis

In this paper, we discuss the method of manipulating large-scale transaction databases using ZBDDs.
Here we consider binary item set databases, eachrecord of which holds a combination of items chosen from a given item list. Such a combination iscalled a tuple (or a transaction).
For analyzing those large-scale transaction
databases, frequent pattern mining[2] and maximum frequent pattern mining[5] are especially important and they have been discussed actively in5

the last decade. Since the introduction by Agrawal
et al.[1], a number of papers have been published
about the new algorithms or improvements forsolving such mining problems[7, 9, 19]. Recently,
graph-based methods, such as FP-growth[9], arereceived a great deal of attention, since they canquickly manipulate large-scale tuple data by constructing compact graph structure on the main
memory.
ZBDD-based method is a similar approach tohandle sets of combinations on the main memory,
but will be more eﬃcient because ZBDDs are akind of DAGs for representing item sets, while FPgrowth uses a tree representation for the same objects. In general, DAGs can be more compact thantrees.
Another important point is that our method
uses ZBDDs not only as internal data structure
but also as output data structure. The most of
existing state-of-the-art pattern mining algorithms
focused on just enumerating or listing the patterns
which satisfy the given conditions, and it was adiﬀerent matter how to store and index the resultof patterns for eﬃcient data analysis. In this paper, we present a fast algorithm of pattern mining and simultaneously indexing the result of hugepatterns compactly on the main memory for consequent analysis. The results can be analyzed ﬂexibly by using algebraic operations implemented on
ZBDDs.
In addition, we show here why we use ZBDDs
instead of ordinary BDDs in this application. Table 2 lists the basic statistics of typical benchmark data[7] often used for data mining/analysis
problems. #I shows the number of items used in
the data, #T is the number of tuples included in
the data, avg|T | is the average number of items
per tuple, and avg|T |/#I is the average appearance ratio of each item. From this table, we canobserve that the item’s appearance ratio is verysmall in many cases. This is reasonable as considering real-life problems, for example, the numberof items in a basket purchased by one customer isusually much less than all the items displayed in a
shop. This observation means that we often handle
very sparse combinations in many practical data
mining/analysis problems, and in such cases, the6Shin-ichi Minato and Hiroki Arimura

Table 2: Statistics of typical benchmark data.
Data name#I#T
total|T | avg|T | avg|T |/#I
T10I4D100K
870 100,000 1,010,228
10.1
1.16%
T40I10D100K
942 100,000 3,960,507
39.6
4.20%
chess
75
3,196
118,25237.0
49.30%
connect
129 67,557 2,904,951
43.0
33.33%
mushroom
119
8,124
186,852
23.0
19.32%
pumsb
2,113 49,046 3,629,404
74.0
3.50%
pumsb star
2,088 49,046 2,475,947
50.5
2.42%
BMS-POS
1,657 515,597 3,367,020
6.5
0.39%
BMS-WebView-1 497 59,602
149,639
2.5
0.51%
BMS-WebView-2 3,340 77,512
358,278
4.6
0.14%
accidents
468 340,183 11,500,870
33.8
7.22%

Figure 9: ZBDD vector for tuple-histogram.
Figure 8: Database example and tuple-histogram.

3.1
ZBDD reduction rule is extremely eﬀective. If theaverage appearance ratio of each item is 1%, ZBDDs may be more compact than ordinary BDDs
up to 100 times. In the literature, there is a ﬁrst
report by Jiang et al.[10] applying BDDs to data
mining problems, but the result seems not excellent
due to the overhead of ordinary BDDs. We must
use ZBDDs in stead of ordinary BDDs for successin many practical data mining/analysis problems.

3

ZBDD-growth: ZBDD-based
pattern mining algorithm

In this section, we describe our new algorithm,
ZBDD-growth, which extract all frequent patterns
from a given transaction database using ZBDDs.

Tuple-Histograms and ZBDD vectors

A Tuple-histogram is the table for counting thenumber of appearance of each tuple in the given
database. An example of tuple-histogram is shownin Fig. 8. This is just a compressed table of thedatabase to combine the same tuples appearing
more than once into one line with the frequency.
Our pattern mining algorithm manipulates
ZBDD-based tuple-histogram representation as theinternal data structure. Here we describe how torepresent tuple-histograms using ZBDDs. Since
ZBDDs are representation of sets of combinations,a simple ZBDD distinguishes only existence ofeach tuple in the database. In order to represent the numbers of tuple’s appearances, we decompose the number into m-digits of ZBDD vector {F0 , F1 , . . . , Fm−1 } to represent integers up to(2m −1), as shown in Fig. 9. Namely, we encode theappearance numbers into binary digital code, as F0
represents a set of tuples appearing odd times (LSBZBDD-growth: An Eﬃcient Method for Frequent Pattern Mining and Knowledge Indexing

7= 1), F1 represents a set of tuples whose appearance number’s second lowest bit is 1, and similar
way we deﬁne the set of each digit up to Fm−1 .
In the example of Fig. 9, The tuple frequencies are decomposed as: F0 = {abc, ab, c}, F1 ={ab, bc}, F2 = {abc}, and then each digit can be
represented by a simple ZBDD. The three ZBDDs
are shared their sub-graphs each other.
Now we explain the procedure for constructing a ZBDD-based tuple-histogram from original
database. We read a tuple data one by one fromthe database, and accumulate the single tuple data
to the histogram. More concretely, we generate a
ZBDD of T for a single tuple picked up from thedatabase, and accumulate it to the ZBDD vector.
The ZBDD of T can be obtained by starting from“1” (a null-combination), and applying “Change”
operations several times to join the items in thetuple. Next, we compare T and F0 , and if they
have no common parts, we just add T to F0 . If
F0 already contains T , we eliminate T from F0 andcarry up T to F1 . This ripple carry procedure continues until T and Fk have no common part. After ﬁnishing accumulations for all data records, thetuple-histogram is completed.
Using the notation F .add(T ) for addition of atuple T to the ZBDD vector F , we describe the procedure of generating tuple-histogram H for given
database D.
H =0
forall T ∈ D do
H = H.add(T )return H
When we construct a ZBDD vector of tuplehistogram, the number of ZBDD nodes in each
digit is bounded by total appearance of items in
all tuples. If there are many partially similar tuples in the database, the sub-graphs of ZBDDs areshared very well, and compact representation is obtained. The bit-width of ZBDD vector is boundedby log Smax , where Smax is the appearance of mostfrequent items.
Once we have generated a ZBDD vector forthe tuple-histogram, various operations can be executed eﬃciently. Here are the instances of operations used in our pattern mining algorithm.

Figure 10: Example of FP-tree.

• H.factor0(v): Extracts sub-histogram of tuples without item v.
• H.factor1(v): Extracts sub-histogram of tuples including item v and then delete v fromthe tuple combinations. (also considered as
the quotient of H/v)
• v · H: Attaches an item v on each tuple combinations in the histogram F .
• H1 + H2 : Generates a new tuple-histogramwith sum of the frequencies of corresponding
tuples.
• H.tuplecount: The number of tuples appearing at least once.
These operations can be composed as a sequenceof ZBDD operations. The result is also compactly
represented by a ZBDD vector. The computation
time is bounded by roughly linear to total ZBDD
sizes.

3.2

ZBDD vectors and FP-trees

FP-growth[9], one of the state-of-the-art algorithm, constructs ”FP-tree” for a given transaction database, and then searches frequent patterns
using this data structure. An example of FPtree is shown in Fig. 10. We can see that FPtree is a trie of tuples with their frequencies. In
other words, FP-growth is based on the tree
representation of tuple-histograms. Namely,
ZBDD-growth is based on logically same internal
data structure as FP-growth. This is the reason
why we call this algorithm ZBDD-growth. However, ZBDD-based method will be more eﬃcient8

Shin-ichi Minato and Hiroki Arimura

ZBDDgrowth(H, α){if(H has only one item v)
if(v appears more than α ) return v ;else return “0” ;F ← Cache(H) ;if(F exists) return F ;v ← H.top ; /* Top item in H */H1 ← H.factor1(v) ;H0 ← H.factor0(v) ;F1 ←ZBDDgrowth(H1 , α) ;F0 ←ZBDDgrowth(H0 + H1 , α) ;F ← (v · F1 ) ∪ F0 ;Cache(H) ← F ;return F ;}ZBDDgrowthMax(H, α){if(H has only one item v)
if(v appears more than α ) return v ;else return “0” ;F ← Cache(H) ;if(F exists) return F ;v ← H.top ; /* Top item in H */H1 ← H.factor1(v) ;H0 ← H.factor0(v) ;F1 ←ZBDDgrowthMax(H1 , α) ;F0 ←ZBDDgrowthMax(H0 + H1 , α) ;F ← (v · F1 ) ∪ (F0 − F0 .permit(F1 )) ;Cache(H) ← F ;return F ;}Figure 11: ZBDD-growth algorithm.
because ZBDDs can share the equivalent subgraphs
and computation time is bounded by the ZBDD
size. The beneﬁt of ZBDDs is especially remarkable when a huge number of patterns are produced.

3.3

Frequent Pattern Mining Algorithm

Our algorithm, ZBDD-growth, is based on a recursive depth-ﬁrst search over the ZBDD-based tuplehistogram representation. The basic algorithm isshown in Fig. 11.
In this algorithm, we choose an item v used in
the tuple-histogram H, and compute the two subhistograms H1 and H0 . (Namely, H = (v · H1 ) ∪H0 .) As v is the top item in the ZBDD vector,
H1 and H0 can be obtained just by referring the1-edge and 0-edge of the highest ZBDD-node, so
the computation time is constant for each digit of
ZBDD.
The algorithm consists of the two recursive calls,
one of which computes the subset of patterns including v, and the other computes the patterns
excluding v. The two subsets of patterns can beobtained as a pair of pointers to ZBDDs, and thenthe ﬁnal result of ZBDD is computed. This procedure may require an exponential number of recursive calls, however, we prepare a hash-based cacheto store the result of each recursive call. Each entry
in the cache is formed as pair (H, F ), where H isthe pointer to the ZBDD vector for a given tuplehistogram, and F is the pointer to the result of

Figure 12: ZBDD-growth-max algorithm.
ZBDD. On each recursive call, we check the cache
to see whether the same histogram H has alreadyappeared, and if so, we can avoid duplicate processing and return the pointer to F directly. By using
this technique, the computation time becomes almost linear to the total ZBDD sizes.
In our implementation, we use some simple techniques to prune the search space. For example, if
H1 and H0 are equivalent, we may skip to compute F0 . For another case, we can stop the recursive calls if total frequencies in H is no more thanα. There are some other elaborate pruning techniques, but they needs additional computation costfor checking the conditions, so sometimes eﬀective
but not always.

3.4

Extension
MiningforMaximalPattern

We can extend the ZBDD-growth algorithm to extract only the maximal frequent patterns[5], eachof which is not included in any other frequent patterns. The algorithm is shown in Fig. 12.
The diﬀerence from the original algorithm isonly one line, written in the frame box. In thispart, we check each pattern in F0 , and delete it if
the pattern is included in one of patterns of F1 . In
this way, we can generate only maximal frequent
patterns. This is basically the same approach as
used in MAFIA[5].

ZBDD-growth: An Eﬃcient Method for Frequent Pattern Mining and Knowledge Indexing

P .permit(Q){
if(P =“0” or Q =“0”) return “0” ;if(P = Q) return F ;if(P =“1”) return “1” ;if(Q =“1”)if(P include “1” ) return “1” ;else return “0” ;R ← Cache(P, Q) ;if(R exists) return R ;v ←TopItem(P, Q) ; /* Top item in P, Q */(P0 , P1 ) ←factors of P by v ;(Q0 , Q1 ) ←factors of Q by v ;R ← (v · P1 .permit(Q1 )) ∪ (P0 .permit(Q0 ∪ Q1 ));Cache(P, Q) ← R ;return R ;}Figure 13: Permit operation.
The process of deleting non-maximal patterns
is basically a very time consuming task, however,
we found that one of the ZBDD-based operation,
called permit operation by Okuno et al.[17], can beused for solving this problem1 . P .permit(Q) returns a set of combinations in P each of which isa subset of some combinations in Q. For example,
when P = {ab, abc, bcd} and Q = {abc, bc}, thenP .permit(Q) returns {ab, abc}. The permit operation is eﬃciently implemented as a recursive procedure of ZBDD manipulation, as shown in Fig. 13.
The computation time of permit operation is almost linear to the ZBDD size.

4

Experimental Results

Here we show the experimental results to evaluate our new method. We used a Pentium-4 PC,
800MHz, 1.5GB of main memory, with SuSE Linux9. We can deal with up to 20,000,000 nodes of ZBDDs in this machine.

4.1

Experiment for Mathematical Example

First, we present the experiment for a set of artiﬁcial examples where ZBDD-growth is extremely ef1

Permit operation is basically same as SubSet operation
by Coudert et al.[6], defined for ordinary BDDs.

9

Table 3: Results for ”one-pair-missing” with α = 1.
n#Patterns

858,9749242,460
10
989,52611
4,017,156
12
16,245,774
13
65,514,540
14 263,652,486
15 1,059,392,916
16 4,251,920,574(output)|ZBDD|
35
40
45
50
55
60
65
70
75

ZBDD-growthTime(sec)
0.01
0.01
0.01
0.01
0.01
0.01
0.02
0.02
0.02

FP-growthTime(sec)
0.11
0.47
1.93
7.81
32.20
131.15518.901966.53(timeout)

fective. The database, named “one-pair-missing,”
has the following form for a given integer n > 0.
a2 b2 a3 b3 · · ·an−1 bn−1 an bn
a1 b1
a3 b3 · · ·an−1 bn−1 an bn
a1 b1 a2 b2· · ·an−1 bn−1 an bn
..
..
..
.
.
.
a1 b1 a2 b2 a3 b3 · · ·an bn
a1 b1 a2 b2 a3 b3 · · ·an−1 bn−1
Namely, this database has n records each of whichcontains (n − 1) pairs of items but only one pair is
missing. It may produce an exponential number of
frequent patterns. The experimental results withfrequency threshold α = 1 are shown in Table 3.
We can observe the exponential explosion of thenumber of patterns, but only linear size of ZBDDs
are needed for representing such a huge numberof patterns. In such cases, ZBDD-growth runs extremely fast, while FP-growth requires exponential
time depending on the output data size.

4.2

Experiments for Benchmark Examples

Next we show the results for the benchmark
examples[8], written in previous section.
Table 4 shows the time and space for generating ZBDD vectors of tuple-histograms. In thistable, #T shows the number of tuples, total|T |is the total of tuple sizes (total appearances of
items), and |ZBDD| is the number of ZBDD nodes
for the tuple-histograms. We can see that tuplehistograms can be constructed for all instances in10Shin-ichi Minato and Hiroki Arimura

Table 4: Generation of tuple-histograms.
Data name#T
total|T |T10I4D100K
100,000 1,010,228
T40I10D100K 100,000 3,960,507
chess
3,196
118,252
connect
67,557 2,904,951
mushroom
8,124
186,852
pumsb
49,046 3,629,404
pumsb star
49,046 2,475,947
BMS-POS
515,597 3,367,020
BMS-WebView-1 59,602
149,639
BMS-WebView-2 77,512
358,278
accidents
340,183 11,500,870

a feasible time and space. The ZBDD sizes arealmost same or less than total|T |.
After generating ZBDD vectors for the tuplehistograms, we applied ZBDD-growth algorithm togenerate frequent patterns. Table 5 show the results for the selected benchmark examples, “mushroom,” “T10I4D100K,” and “BMS-WebView-1.”
The execution time includes the time for generating
the initial ZBDD vectors for tuple-histograms.
The results shows that ZBDD-growth is much
faster than FP-tree for “mushroom,” but not eﬀective for ”T10I4D100K.” ”T10I4D100K” is known
as an artiﬁcial database, consists of randomly generated combinations, so there are almost no relationship between the tuples. In such cases, ZBDD
nodes cannot be shared well, and only the overhead factor is revealed. For “BMS-WebView-1,”
ZBDD-growth is slower than FP-growth when the
output size is small, however, an exponential factorof reduction is observed for the cases of generating huge patterns. Especially for α = 31, 30, morethan 1 Tera patterns are generated and compactly
stored in the memory, that has never been possible
by using conventional data structures.

4.3

Maximal Frequent Pattern Mining

We also show the experimental results of maximal frequent pattern mining using ZBDD-growthmax algorithm. In Table 6, we show the results for the same examples as used in the experiment of original ZBDD-growth. The last column|ZBDD Vector| Time(s)552,42943.2
3,396,395
150.2
40,0281.4
309,075
58.1
8,006
1.5
1,750,883
188.5
1,324,502
123.6
1,350,970
895.0
46,14818.3
198,471138.0
3,877,333
107.0

T ime(max) /T ime(all) shows the ratio of computation time between the ZBDD-growth-max and theoriginal ZBDD-growth algorithm. We can observethat the computation time is almost the same (upto twice) between the two algorithms. In otherwords, the additional computation cost for ZBDDgrowth-max is almost the same order as the originalalgorithm. Our ZBDD-based ”permit” operation
can eﬃciently ﬁlter the maximal patterns within atime depending on the ZBDD size, which is almost
the same cost as manipulating ZBDD vectors oftuple-histograms.

5

Post Processing for Generated
Frequent Patterns

Our ZBDD-based method features that the algorithm uses ZBDDs not only as internal data structure but also as output data structure indexing ahuge number of patterns compactly on the main
memory. The results can be analyzed ﬂexibly byusing algebraic operations implemented on ZBDDs.
Here we show several examples of the post processing operations for the output data.

Sub-pattern matching for the frequent patterns
For the result of frequent patterns F , we can eﬃciently ﬁlter a subset S, such that each pattern in
S contains a given sub-pattern P .

ZBDD-growth: An Eﬃcient Method for Frequent Pattern Mining and Knowledge Indexing

11

Table 5: Results for benchmark examples.
Data name:Min. freq. α#Frequentpatterns(output) ZBDD|ZBDD| growthTime(s)mushroom:
8,124
1
1
5,000
41
11
1,000
123,277
1,417
200
18,094,821
12,34050
198,169,865
36,65216
1,176,182,553
53,804
4
3,786,792,695
59,9701
5,574,930,437
40,557
T10I4D100K:
100,000
0
0
5,000
10
10
1,000
385
382
200
13,2554,288
50
53,38520,36416
175,915
89,423
4
3,159,067 1,108,723
12,217,324,767 (mem.out)
BMSWebView-1:
59,602
0
0
1,000
31
31
200
372
309
50
8,191
3,753
40
48,543
12,176
36
461,52134,79035
1,177,607
47,45734
4,849,465
64,601
33
69,417,073
80,60432
1,531,980,297
97,692
31 8,796,564,756,112
117,101
30 35,349,566,550,691
152,431

S=F
forall v ∈ P do:
S = S.onset(v).change(v)return S
Inversely, we can extract a subset of patterns notsatisfying the given conditions. It is easily doneby computing F − S. The computation time forthe sub-pattern matching is much smaller than thetime for frequent pattern mining.
The above operations are sometimes called constraint pattern mining. In conventional method, it
is too time consuming to generate all frequent pat-

FPgrowth
Time(s)

1.2
1.2
3.7
9.7
10.2
7.7
4.3
1.8

0.1
0.1
0.3
5.4
44.6
244.1
891.3
1,322.5

78.5
81.3
135.5
279.4
408.7
543.3
646.0
−

0.7
0.7
3.1
4.5
6.7
13.7
38.8
317.1

27.3
0.2
27.8
0.2
31.3
0.4
49.0
0.8
46.6
1.2
102.4
2.7
111.4
4.2
120.8
8.3
130.0
28.1
133.7
345.3
138.1 (timeout)
143.9 (timeout)

terns before ﬁltering. Therefore, many researchersconsider the direct methods of constraint patternmining without generating all patterns. However,using ZBDD-based method, a huge number of patterns can be stored and indexed compactly on thememory, so in many cases, it is possible to generate all frequent patterns and then processing themusing algebraic ZBDD operations.
Extracting Long/Short Patterns
Sometimes we are interested in the long/short patterns, consists of a large/small number of items.
Using ZBDDs, all combinations of less than k out of12

Shin-ichi Minato and Hiroki Arimura

Table 6: Results of maximal pattern mining.
Data name: #Maximal (output)
ZBDD- T ime(max)Min. freq. αfrequent |ZBDD| growth-max /T ime(all)patterns
Time(s)mushroom:
8,124
1
1
1.2
0.99
5,000
3
10
1.2
1.00
1,000
467
744
4.1
1.10
200
3,111
4,173
10.7
1.10
50
9,857
10,22311.0
1.08
16
24,06013,1218.1
1.06
4
39,456
14,051
4.2
0.98
1
8,124
8,006
1.2
0.70
T10I4D100K:
5,000
10
10
107.1
1.32
1,000
370
376
203.1
1.50
200
1,938
2,609
462.8
1.66
50
12,062
13,259
787.8
1.93
16
68,096
66,274922.4
1.70
4400,730 372,993
1141.21.77
177,443 532,061
140.5−
BMSWebView-1:
1,000
29
30
34.9
1.25
200
264
289
41.2
1.32
50
3,546
3,064
71.2
1.45
40
9,827
8,260
110.1
1.44
36
15,17914,345
149.5
1.46
35
15,725
15,713
161.5
1.45
34
15,877
16,854
173.1
1.43
33
15,753
16,854
183.8
1.41
32
15,252
17,680
196.6
1.47
31
13,63917,383
208.7
1.51
30
11,371
16,323219.7
1.53

n items are eﬃciently represented in a polynomialsize, bounded by O(k · n). This ZBDD represents
a length constraint of patterns. We then apply intersection (or diﬀerence) operation to the frequent
patterns with the length constraint of ZBDD. In
this way, we can easily extract a set of long/shortfrequent patterns.

Comparison of Two Sets of Frequent Patterns
Our ZBDD manipulation environment can eﬃciently store more than one results of frequent pattern mining together. So, we can compare the two
sets of frequent patterns generated with diﬀerent

conditions. For example, if the database is gradually changing as time passing, the tuple-histograms
and frequent patterns are not the same forever.
Our ZBDD-based method can store and index anumber of snapshot of pattern sets and easily show
the intersection, union, and diﬀerence between any
pair of snapshots. When many similar ZBDDs are
generated, their ZBDD nodes are eﬀectively sharedinto a monolithic multi-rooted graph, so the memory requeirement is much less than storing each
ZBDD separately.

ZBDD-growth: An Eﬃcient Method for Frequent Pattern Mining and Knowledge Indexing

Calculating Statistical Data
After generating a ZBDD for a set of patterns, we
can quickly count a number of patterns by usinga primitive ZBDD operation S.count. The computation time is linearly bounded by ZBDD size,
not depending on the amount of pattern counts.
We can also eﬃciently calculate other statisticalmeasures, such as Support and Confidence, which
are often used in probabilistic analysis and machinelearning.

Finding Disjoint Decompositions in Frequent Patterns
In the recent paper[16], we presented an eﬃcient
ZBDD-based method for ﬁnding all possible simple
disjoint decompositions in a set of combinations. If
a given set of patterns f can be decomposed asf (X, Y ) = g(h(X), Y ), and X and Y has no common items, we then call it a simple disjoint decomposition.

13

However, we do not have to use ZBDD-growthalgorithm for all instances. We may use the existing methods for the instances where they are more
eﬀective than ZBDD-growth. In addition, we candevelop a hybrid program that using FP-tree orsimple array for internal data structure, but theoutput is constructed as a ZBDD.
A ZBDD can be regarded as a compressed trie
for representing a set of patterns. ZBDD-based
method will be useful as a fundamental techniques
for database analysis and knowledge indexing, andwill be utilized for various data mining applications.

References[1] R. Agrawal, T. Imielinski, and A. N. Swami, Mining Association rules between sets of items in large
databases, In P. Buneman and S. Jajodia, edtors,
Proc. of the 1993 ACM SIGMOD International
Conference on Management of Data, Vol. 22(2) of
SIGMOD Record, pp. 207–216, ACM Press, 1993.

This decomposition method extracts another aspect of hidden structures from complicated itemset
data. The decomposition procedure is enough fast
for handling large-scale sets of patterns. It will be
a powerful tool for database analysis.

[2] R. Agrawal, H. Mannila, R. Srikant, H. Toivonenand A. I. Verkamo, Fast Discovery of Association
Rules, In Advances in Knowledge Discovery andData Mining, MIT Press, 307–328, 1996.

6[4] Bryant, R. E., Graph-based algorithms for Booleanfunction manipulation, IEEE Trans. Comput., C35, 8 (1986), 677–691.

Conclusion

In this paper, we presented a new method of
ZBDD-based frequent pattern mining algorithm.
Our method generates a ZBDD for a set frequent
patterns from the ZBDD vector for the tuplehistogram of a given transaction database. Our experimental result shows that our ZBDD-growth algorithm is fast as competitive to the existing stateof-the-art algorithms, such as FP-growth. Especially for the cases where the ZBDD nodes are wellshared, exponential speed up are observed comparing to the existing algorithms based on explicit table/tree representation. On the other hand, for thecases where ZBDDs are not well shared, or numberof patterns is very small, ZBDD-growth method is
not eﬀective and the overhead factor reveals.

[3] J.-F. Boulicaut, Proc. 2nd International Workshop
on Knowledge Discovery in Inductive Databases(KDID’03), Cavtat-Dubrovnik, 2003.

[5] D. Burdick, M. Calimlim, J. Gehrke, MAFIA: A
Maximal Frequent Itemset Algorithm for Transactional Databases, In Proc. ICDE 2001, 443–452,
2001.
[6] O. Coudert, J. C. Madre, H. Fraisse, A new viewpoint on two-level logic minimization, in Proc. of
30th ACM/IEEE Design Automation Conference,
pp. 625-630, 1993.
[7] B.
Goethals,“SurveyonFrequent
Pattern
Mining”,
Manuscript,
2003.
http://www.cs.helsinki.fi/
u/goethals/publications/survey.ps[8] B. Goethals, M. Javeed Zaki (Eds.),
Itemset Mining Dataset Repository,

Frequent
Frequent

14

Shin-ichi Minato and Hiroki Arimura

Itemset Mining Implementations (FIMI’03), 2003.
http://fimi.cs.helsinki.fi/data/[9] J. Han, J. Pei, Y. Yin, R. Mao, Mining Frequent Patterns without Candidate Generation: A
Frequent-Pattern Tree Approach, Data Mining
and Knowledge Discovery, 8(1), 53–87, 2004.
[10] L. Jiang, M. Inaba, and H. Imai: A BDD-based
Method for Mining Association Rules, in Proceedings of 55th National Convention of IPSJ, Vol. 3,
pp. 397-398, Sept. 1997, IPSJ.
[11] H. Mannila, H. Toivonen, Multiple Uses of Frequent Sets and Condensed Representations, In
Proc. KDD, 189–194, 1996.
[12] S. Minato: Zero-suppressed BDDs for set manipulation in combinatorial problems, In Proc. 30th
ACM/IEEE Design Automation Conf. (DAC-93),(1993), 272–277.
[13] S. Minato: “Binary Decision Diagrams and Applications for VLSI CAD”, Kluwer Academic Publishers, November 1996.
[14] S. Minato, Zero-suppressed BDDs and Their Applications, International Journal on Software Tools
for Technology Transfer (STTT), Springer, Vol. 3,
No. 2, pp. 156–170, May 2001.
[15] S. Minato and H. Arimura: Eﬃcient Combinatorial Item Set Analysis Based on Zero-Suppressed
BDDs”, In Proc. of IEEE/IEICE/IPSJ International Workshop on Challenges in Web Information Retrieval and Integration (WIRI-2005), pp. 310, Apr., 2005.
[16] S. Minato: Finding Simple Disjoint Decompositions in Frequent Itemset Data Using Zerosuppressed BDD, In Proc. of IEEE ICDM 2005
workshop on Computational Intelligence in Data
Mining, pp. 3-11, ISBN-0-9738918-5-8, Nov. 2005.
[17] H. Okuno, S. Minato, and H. Isozaki: On the Properties of Combination Set Operations, Information
Procssing Letters, Elsevier, 66 (1998), pp. 195-199,
1998.
[18] Ricardo Baeza-Yates, Berthier Ribiero-Neto,“Modern Information Retrieval”, Addison Wesley,
1999.
[19] M. J. Zaki, Scalable Algorithms for Association
Mining, IEEE Trans. Knowl. Data Eng. 12(2),372–390, 2000.