TCS -TR-A-04-01

TCS Technical Report

Combinatorial Item Set Analysis Based on
Zero-Suppressed BDDs
by

Shin-ichi Minato and Hiroki Arimura

Division of Computer Science
Report Series A
December 8, 2004

Hokkaido University

Graduate School ofInformation Science and Technology
Email:

minato@ist.hokudai.ac.jp

Phone:+81-011-706-7682

Fax:+81-011-706-7682

Combinatorial Item Set Analysis Based on Zero-Suppressed BDDs
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

December, 8, 2004

rithms or improvements for solving such mining
problems[7, 9, 17].

(Abstract) Manipulation of large-scale combinatorial data is one of the important fundamental
technique for web information retrieval, integration, and mining. In this paper, we propose a
new approach based on BDDs (Binary Decision Diagrams) for database analysis problems. BDDs aregraph-based representation of Boolean functions,
now widely used in system design and veriﬁcation
area. Here we focus on Zero-suppressed BDDs (ZBDDs), a special type of BDDs, which are suitablefor handling large-scale sets of combinations. Using ZBDDs, we can implicitly enumerate combinatorial item set data and eﬃciently compute set
operations over the ZBDDs. We present some encouraging experimental results of frequent item set
mining problem for practical benchmark examples,some of which have never been generated by previous method.

1

In this paper, we propose a new approach basedon BDDs (Binary Decision Diagrams) for database
analysis problems. BDDs are graph-based representation of Boolean functions, now widely used insystem design and veriﬁcation area. Here we focus
on Zero-suppressed BDDs (ZBDDs), a special typeof BDDs, which are suitable for handling largescale sets of combinations. Using ZBDDs, we canimplicitly enumerate combinatorial item set dataand eﬃciently compute set operations over the ZBDDs.
For a related work, FP-Tree[9] is recently received a great deal of attention because it supports
fast manipulation of large-scale item set data using
compact tree structure on the main memory. Our
ZBDD-based method is a similar approach to handle sets of combinations on the main memory, butwill be more eﬃcient in the following points:

Introduction• ZBDDs are a kind of DAGs for representing
item sets, while FP-Trees are tree representation for the same objects. In general, DAGs
can be more compact than trees.

Manipulation of large-scale combinatorial data is
one of the fundamental technique for web information retrieval integration, and mining[16]. In
particular, frequent item set analysis is importantin many tasks that try to ﬁnd interesting patterns
from web documents and databases, such as association rules, correlations, sequences, episodes,
classiﬁers, and clusters. Since the introduction by
Agrawal et al.[2], the frequent item set and association rule analysis have been received much attentions from many researchers, and a number of
papers have been published about the new algo-• ZBDD-based method provides not only compact data structures but also eﬃcient item set
operations written in a simple mathematical
set algebra.
We present some encouraging experimental resultsof frequent item set mining problem for practicalbenchmark examples, some of which have neverbeen generated by previous method.
1

2

Shin-ichi Minato and Hiroki Arimura

Recently, the data mining methods are often discussed in the context of Inductive Databases[4, 12],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.

F

F

a

1
0

b

BDDs and ZBDDs

2.1

BDDs

BDD is a directed graph representation of theBoolean function, as illustrated in Fig. 1(a). It
is derived by reducing a binary tree graph representing recursive Shannon’s expansion, indicated inFig. 1(b). The following reduction rules yield a
Reduced Ordered BDD (ROBDD), which can eﬃciently represent the Boolean function. (see [5] fordetails.)• 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
research 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 including AND, OR, parity, and arithmetic adder functions. Using Bryant’s algorithm[5], 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 time

1

b 1

0

b 1

0

1

c

0

1

c

0

0

1

c
1 0

1

(a) BDD.

2

a

0

0

1

0

1 0

0

1

c
1

0

0

1

c

1

1

(b) Binary tree.

Figure 1: BDD and binary tree for 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 BDDs

is almost linear to the data size unless the data
overﬂows the main memory. (see [14] 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

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 combina-

3

Combinatorial Item Set Analysis Based on Zero-Suppressed BDDs

F1
a

F2

F3

a

1

1

0

0

F4

0

a
1

b

1

1

0

b
0

1

0

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

Figure 3: Shared multiple BDDs.

x
0

f

Jump

S(abc):
abc S
000 0
100 1
010 1
110 0
001 0
101 0
011 0
111 0

S(abcd):abcd S
0000 01000 10100 11100 00010 01010 00110 01110 00001 01001 00101 01101 00011 01011 00111 01111 0S(abcd)S(abc)
S(abcd)
a

a

0
1
1
b b
b
0 0 1
0
0 1
c
1 c 01
1 0
1
d
1
0
0
1

S(abc)

0
b

BDD

0

a
1

b
0 1
0

1
ZBDD

Figure 5: Example of ZBDD eﬀect.

1

0

f

Figure 4: ZBDD reduction rule.

tion 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 one
combination vector, a Boolean function determines
whether the combination is included in the set ofcombinations. Such Boolean functions are called
characteristic functions. The set operations suchas union, intersection, and diﬀerence can be performed by logic operations on characteristic functions.

• Delete all nodes whose 1-edge directly points
to the 0-terminal node, and jump through to
the 0-edge’s destination, as shown in Fig. 4.

By using BDDs for characteristic functions, we
can manipulate sets of combinations eﬃciently.
They can be generated and manipulated within atime 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.

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.

Zero-suppressed BDD (ZBDD)[13, 15] isa special type of BDDs for eﬃcient manipulationof sets of combinations. ZBDDs are based on thefollowing special reduction rules.

Here we summarise the features of ZBDDs.

Figure 6: Explicit representation by ZBDD.

• Share equivalent nodes as well as ordinary
BDDs.

• In ZBDDs, the nodes of irrelevant items (neverchosen in any combination) are automatically4Shin-ichi Minato and Hiroki Arimura

deleted by ZBDD reduction rule. In ordinary BDDs, irrelevant nodes still remain andthey may spoil the reduction beneﬁt of sharing
nodes. (An example is shown in Fig. 5.)• 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. 6.
Namely, (the order of) ZBDD size never exceeds the explicit representation. If morenodes 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.

3

ZBDD-based Database Analysis

In this section, we discuss the method of manipulating large-scale item set 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 tuple databases
eﬃciently, basic problems of data mining, such as“∅”

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.

Table 2: Statistics of typical benchmark data.
Data name#I#T avg|T | avg|T |/#I
T40I10D100K
942 100,000
39
4.14%
mushroom
119
8,124
23
19.32%BMS-WebView-1 497 59,602
2
0.40%
basket13,103 41,373
90.06%

frequent item set mining[3] and maximum frequent
item set mining[6], are very important and they
have been discussed actively in last decade. Recently, graph-based methods, such as FP-Tree[9],are received a great deal of attention, since theycan quickly manipulate large-scale tuple data by
constructing compact graph structure on the main
memory. ZBDD technique is a similar approach tohandle sets of combinations on the main memory,
so we hope to apply ZBDD-based method eﬀectively in this area.

Combinatorial Item Set Analysis Based on Zero-Suppressed BDDs

5

WebView-1” in Table 2 includes 59,602 records,
and the most frequent tuple appears 1,533 times
in the records. The top 10 frequent tuples appears
8,404 times in total. (Shares 14% in the records.)

Figure 7: ZBDD vector for tuple-histogram.

3.1

Property of Practical Databases

Table 2 shows 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 can observethat the item’s appearance ratio is very small inmany cases. This is reasonable as considering reallife problems, for example, the number of items in abasket purchased by one customer is usually muchless than all the items displayed in a shop. For another example, the number of links from one web
page is much less than all the web pages in the network. This observation means that we often handle
very sparse combinations in many practical data
mining/analysis problems, and in such cases, theZBDD 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.2

Tuple-Histograms based on ZBDDs

A Tuple-histogram is the table for counting thenumber of appearance of each tuple in the given
database. In practical databases, the same tuple
often appears many times. For example, ”BMS-

Here we present a method of representing tuplehistograms by using ZBDDs. Since ZBDDs are
representation of sets of combinations, a simple
ZBDD distinguishes only existence of each tuple inthe databases. In order to represent the numbersof 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. 7. Namely, we encode the appearance numbers into binary digital code, as F0 represents a setof tuples appearing odd times (LSB = 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. 7, 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-histgram from given tuple
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 FT for given
database D.
FT = 0
forall T ∈ D do

6Shin-ichi Minato and Hiroki Arimura

Figure 8: Tuple-histogram to pattern-histogram.

Figure 9: ZBDDs for a tuple and all sub-patterns

FT = FT .add(T )return FT

cases, it is diﬃcult to generate a complete patternhistogram for a practical size of tuple database.
Therefore, conventional methods extract only frequent patterns which appears more than α-times,
for a given thresholds α, within a feasible computation time and space[7].

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-based tuplehistogram, it is easy to extract the set of frequent
tuples which appears more than α times. By encoding the given threshold α into binary code, we
can compose an algorithm of bit-wise arithmetic
comparison between α and FT based on ZBDD operations. After execution of those ZBDD operations, the result of frequent tuples can be obtained
as a ZBDD. The computation time is almost linear
to total ZBDD size.

3.3

Pattern-Histograms based on ZBDDs

In this paper, a pattern means a subset of items
included in a tuple. A pattern-histogram is the table for counting the number of appearance of eachpatterns in any tuple in the given database. An
example is shown in Fig. 8.
In general, a tuple of k items includes 2k patterns, so computing a pattern-histogram is muchharder than computing a tuple-histogram. In many

Using the ZBDD-based data structure, we may
have more compact representation than previous methods, as a number of similar patterns
can be shared in ZBDDs, and in some cases,
this makes possible to generate complete patternhistograms which have never succeeded in previous methods. Figure 9 shows a ZBDD fora tuple T = abcde with ﬁve items and a
ZBDD representing a set of all 32 patterns P ={1, a, b, c, d, e, ab, ac, bc, cd, abc, . . . , abcde} included
in T . Clearly we can see that 2k patterns in a kitem tuple can be represented by only k nodes of
ZBDDs. As well as generating tuple-histograms,
we can generate pattern-histograms by accumulating such a single ZBDD P for a set of patterns
one by one, Here we summarise the procedure forcomputing a pattern-histogram FP from a given
database D as follows.
FP = 0
forall T ∈ D do
P =T
forall v ∈ T do
P = P ∪ P.onset(v)FP = FP .add(P )return FP
Unfortunately, ZBDDs grows larger as repeating accumulations, and eventually may overﬂow

Combinatorial Item Set Analysis Based on Zero-Suppressed BDDs

the memory for some large examples. While tuplehistgrams are bounded by the total items in thetuples, pattern-histograms are not bounded and somany patterns will be generated.
However, if we have succeeded in generating
a ZBDD-based pattern-histogram for a given instance, we can enjoy very powerful data processing
by using eﬃcient ZBDD operations. It is interesting and important how large-scale instances we cangenerate complete pattern-histograms. The experimental results will be shown in later section.
In addition, we present an alternative procedurefor generating ZBDD-based pattern-histograms.
We can generate a pattern-histgram FP from acomplete tuple-histogram FT .
FP = FT
forall v ∈ FT do:
FP = FP .add(FP .onset(v))
return FP
We have not determined which algorithm is fasterin practical environments. Anyway, the ﬁnal formof ZBDD vectors must be the same if the two algorithms are computing for the same instance.

3.4

Utilities
ofHistograms

Tuple/Pattern-Once we generate tuple-/pattern-histograms using ZBDDs, various operations can be executedeﬃciently. We show several examples in thissection. Suppose that we have obtained F :{F0 , F1 , . . . , Fm−1 }, the ZBDD vector representing
a tuple- or pattern-histogram.
• We can eﬃciently extract a subset of tuples/patterns including a given item or subpattern P .

7

Table 3: Generation of tuple-histograms.
Data name#T
total|T | |ZBDD| Time(s)T10I4D100K
100,000 1,010,228 552,429
43.2
T40I10D100K 100,000 3,960,507 3,396,395
895.0
chess
3,196
118,252
40,0281.4
connect
67,557 2,904,951 309,075
58.1
mushroom
8,124
186,852
8,006
1.5
pumsb
49,046 3,629,404 1,750,883
188.5
pumsb star
49,046 2,475,947 1,324,502
123.6
BMS-POS
515,597 3,367,020 1,350,970
895.0
BMS-WebView-1 59,602
149,639
46,148
18.3
BMS-WebView-2 77,512
358,278 198,471
138.0
accidents
340,183 11,500,870 3,877,333
107.0

After extracting a subset, we can quickly counta number of tuples/patterns by using a primitive ZBDD operation S.count. The computation time is linearly bounded by ZBDD size,
not depending on the amount of tuple/patterncounts.
• For given α, we can extract all frequent tuples/patterns appearing more than α times.
Computation time is almost linear to the
ZBDD size. Repeating this procedure with different α’s, we can determine the threshold αm
to pick up the top m frequent tuples/patterns.
After generating ZBDD-based histograms, it isquite easy to extract frequent sets with diﬀerent α’s, while previous methods need almost
recomputing again for each α.
• From ZBDD-based histograms, we can eﬃciently calculate indexes, such as Support andConfidence, which are often used in probabilistic/statistic analysis and machine learning
area.



S = Fkforall v ∈ P do:
S = S.onset(v).change(v)return S
Inversely, we can extract a subset of tuples/patterns not satisfying the given condi
tions. It is easily done by computing Fk − S.

A feature of ZBDD-based method is to constructpowerful data structure on the main memory, andwe can interactively execute various queries to the
database. Moreover, it is very interesting that thequeries can be speciﬁed by mathematical set operations.

8

Shin-ichi Minato and Hiroki Arimura

Table 4: Pattern-histogram for “mushroom”.
ZBDD nodes
513,762

Time(s)214.0#Pattern(> 2G)

Table 5: FP-Tree-based method for “mushroom”.
Threshold α
81
40
16
8
4
1

4

Time(s)22.60
67.96
244.06494.05891.31
1,322.48#Pattern
91,273,269
295,117,613
1,176,182,553
1,983,493,667(> 2G)(> 2G)

Experimental Results

For evaluation of our method, we conducted
experiments to construct ZBDD-based tupleand pattern-histograms for typical benchmark
examples[8] used in data mining/analysis problems.
We used a Pentium-4 PC, 800MHz, 512MB ofmain memory, with SuSE Linux 9. We can deal
with up to 10,000,000 nodes of ZBDDs in thismachine. Table 3 shows the results of generating tuple-histograms. In this table, #T shows thenumber of tuples, total|T | is the total of tuple sizes(total appearances of items), and |ZBDD| is thenumber of ZBDD nodes for the tuple-histograms.
We can see that tuple-histograms can be constructed for all instances in a feasible time andspace. The ZBDD sizes are almost same or lessthan total|T |.
On the other hand, we succeeded in constructing the complete pattern-histogram within a given
memory space, only for “mushroom”, which is a relatively small instance (Table 4). In this case, thepattern-histogram requires about 65 times more
ZBDD nodes than the tuple-histogram for the samedata. In other words, if the tuple-histogram can begenerated in a space tens or more times smaller
than main memory size, it may be possible to generate a complete pattern-histogram in the main
memory.

The “mushroom” pattern-histogram is implicitly representing at least 2,000,000,000 patterns.
(The counter overﬂows the range of 32-bit integers.) The number of ZBDD nodes are 4,000 times
smaller than number of patterns. This shows agreat beneﬁt of compression ratio obtained by ZBDDs.
To compare with a previous method, we applieda frequent pattern mining program based on FPTree[9], to extract the set of frequent patterns appearing more than α times, for the same example “mushroom”. The results are shown in Table 5. For smaller α’s, more patterns are extract,
and the computation time increases up to hundreds or thousands of seconds. Notice that the
FP-Tree-based method only extracts a set of frequent patterns for a given α, but does not generates a complete histogram for all possible patterns.
Our ZBDD-based method generates a complete histogram for all patterns in 214 seconds, and it corresponds to computing frequent pattern sets for all
α’s at once. Consequently, ZBDD-based method
is especially eﬀective for handling the sets of huge
number of patterns.

5Conclusion

In this paper, we presented a new method of using ZBDDs for database analysis problems. Our
work is just starting now, and we have many future
works to be considered, such as ZBDD variable ordering problem for reducing graph size, and more
eﬃcient implementation of ZBDD set operations.
We expect that it would be too memoryconsuming to construct ZBDDs of the complete
pattern-histograms for the large-scale benchmarks,
besides “mushroom”. However, hopefully we will
be able to handle those practical size of databases
by using well-known improvement techniques, suchas preprocessing of pruning not frequent items
and patterns, or handling only maximum item set
data[6], etc. ZBDD-based method will be usefulas a fundamental techniques for various processingof database analysis, and will be utilized for web
information retrieval and integration.

Combinatorial Item Set Analysis Based on Zero-Suppressed BDDs

Acknowledgment
This research is partially supported by Grant-inAid from Ministry of Education, Culture, Sports,
Science and Technology Japan.

References[1] Akers, S. B., Binary decision diagrams, IEEE
Trans. Comput., C-27, 6 (1978), 509–516.
[2] 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.

9[11] Lee, C. Y., Representation of switching circuits bybinary-decision programs, Bell Sys. Tech. Jour., 38(1959), 985–999.
[12] H. Mannila, H. Toivonen, Multiple Uses of Frequent Sets and Condensed Representations, In
Proc. KDD, 189–194, 1996.
[13] S. Minato: Zero-suppressed BDDs for set manipulation in combinatorial problems, In Proc. 30th
ACM/IEEE Design Automation Conf. (DAC-93),(1993), 272–277.
[14] S. Minato: “Binary Decision Diagrams and Applications for VLSI CAD”, Kluwer Academic Publishers, November 1996.
[15] 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.

[3] 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.

[16] Ricardo Baeza-Yates, Berthier Ribiero-Neto,“Modern Information Retrieval”, Addison Wesley,
1999.

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

[17] M. J. Zaki, Scalable Algorithms for Association
Mining, IEEE Trans. Knowl. Data Eng. 12(2),372–390, 2000.

[5] Bryant, R. E., Graph-based algorithms for Booleanfunction manipulation, IEEE Trans. Comput., C35, 8 (1986), 677–691.
[6] D. Burdick, M. Calimlim, J. Gehrke, MAFIA: A
Maximal Frequent Itemset Algorithm for Transactional Databases, In Proc. ICDE 2001, 443–452,
2001.
[7] B. Goethals, “Survey on Frequent Pattern Mining”, Manuscript, 2003.
http://www.cs.helsinki.fi/u/goethals/
publications/survey.ps[8] B. Goethals, M. Javeed Zaki (Eds.), Frequent
Itemset Mining Dataset Repository, Frequent
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.