TCS -TR-A-07-27

TCS Technical Report

A Theoretical Study on Variable Ordering of ZBDDs
for Representing Frequent ItemsetsbyShin-ichi Minato

Division of Computer Science
Report Series A
May 18, 2007

Hokkaido University
Graduate School ofInformation Science and Technology
Email:

minato@ist.hokudai.ac.jp

Phone:+81-011-706-7682

Fax:+81-011-706-7682

A Theoretical Study on Variable Ordering of ZBDDs
for Representing Frequent Itemsets
Shin-ichi Minato
Division of Computer Science
Hokkaido University
North 14, West 9
Sapporo 060-0814, JapanMay 18, 2007
(Abstract) Recently, an eﬃcient method of
database analysis using Zero-suppressed Binary
Decision Diagrams (ZBDDs) has been proposed.
BDDs are a graph-based representation of Booleanfunctions, now widely used in system design andveriﬁcation. Here we focus on ZBDDs, a special type of BDDs, which are suitable for handlinglarge-scale combinatorial itemsets in frequent itemset mining. In general, it is well-known that thesize of ZBDDs greatly depends on variable ordering; however, in the speciﬁc cases of applying ZBDDs to data mining, the eﬀect of variable ordering
has not been studied well. In this paper, we presenta theoretical study on ZBDD variable ordering forrepresenting frequent itemsets. We show two typical databases we found out, where the ZBDD sizes
are exponentially sensitive to the variable ordering.
We also show that there is a case where the ZBDD
size must be exponential in any variable ordering.
Our theoretical results are helpful for developing agood heuristic method of variable ordering.

Recently, we have attacked the problem of eﬃciently generating the frequent patterns in a transaction database by using a data structure called
Zero-suppressed Binary Decision Diagrams (abbr.
ZBDDs), see [7, 8]. ZBDDs are a special case of
Binary Decision Diagrams (abbr. BDDs)[2]. Using ZBDDs one can implicitly enumerate sets ofcombinations. Moreover, one can then perform efﬁciently various operations including the discovery
and analysis of frequent patterns.

1

2

In general, it is well-known that the size of ZBDDs greatly depends on variable ordering, however,in the speciﬁc cases of applying ZBDDs to data
mining, the eﬀect of variable ordering has not beenstudied well. In this paper, we present a theoretical
study on ZBDD variable ordering for representing
frequent itemsets. We show two typical databases
we found out, where the ZBDD sizes are exponentially sensitive to the variable ordering. We also
show that there is a case where the ZBDD size must
be exponential in any variable ordering.

Introduction

Discovering useful knowledge from large-scale
databases has attracted a considerable attention
during the last decade. Frequent pattern mining
is one of the fundamental problems for knowledge
discovery. Since the pioneering paper by Agrawal
et al.[1], various algorithms have been proposed
to solve the frequent pattern mining problem (cf.,e.g., [11, 5]).

Database Representation Using ZBDDs

In this section, we ﬁrst describe the database representation to be discussed. Here we consider
databases of the following type. Let M = ∅ be
any set. We refer to the elements of M as to items.
In our examples below, we use M = {a, b, c}. Thenthe set of all possible combinations is the powerset ℘(M ) of M . Any subset C ⊆ ℘(M ) is said to1

2

Shin-ichi Minato

Figure 1: Binary Decision Tree, BDDs and ZBDDs

be a set of combinations. The elements of a setof combinations are sets of items, e.g., {a, c}. To
simplify notation, we write ac instead of {a, c} andwe refer to the elements of a set of combinations as
to tuples. A transaction database is just a list oftuples.

2.1

BDDs and ZBDDs

A Binary Decision Diagram (BDD) is a graph representation for a Boolean function. An Example isshown in Fig. 1 for F (a, b, c) = abc ∨ abc.
Given a variable ordering (in our example
a, b, c), one can use Bryant’s algorithm[2] to construct the BDD for any given Boolean function.
For many Boolean functions appearing in practicethis algorithm is quite eﬃcient and the resulting
BDDs are much more eﬃcient representations thanbinary decision trees.
BDDs were originally invented to represent
Boolean functions. But we can also map a setof combinations into Boolean space of n variables,
where n is the cardinality of the item set M (seeFig. 2). So, one could also use BDDs to represent
sets of combinations. However, one can even obtain a more eﬃcient representation by using Zerosuppressed BDDs (ZBDDs)[7].
If there are many similar combinations then thesubgraphs are shared resulting in a smaller representation. In addition, ZBDDs have a special typeof node deletion rule. As shown in Fig. 3, All nodes
whose 1-edge directly points to the 0-terminal node
are deleted. Because of this, the nodes of items that
do not appear in any sets of combinations are automatically deleted as shown in Fig.1. This ZBDD

reduction rule is extremely eﬀective if we handle a
set of sparse combinations. If the average appearance ratio of each item is 1%, ZBDDs are possibly more compact than ordinary BDDs, up to 100
times.
ZBDD representation has another good property that each path from the root node to the 1terminal node corresponds to each combination in
the set. Namely, the number of such paths in the
ZBDD equals to the number of combinations inthe set. This beautiful property indicates that,even if there are no equivalent nodes to be shared,
the ZBDD structure explicitly stores all items ofeach combination, as well as using an explicit linear linked list data structure. In other words, (theorder of) ZBDD size never exceeds the explicit representation. If more nodes are shared, the ZBDD
is more compact than linear list.

2.2

ZBDD-based representation for frequent itemsets

Frequent itemset mining (or frequent pattern mining) is the problem to enumerate all possible subsets of itemset M (also called patterns) which appear more than or equal to α times in the database,for given α. Since their introduction by Agrawal
et al.[1], many papers have been published about
new algorithms and improvements for solving suchmining problems[4, 5, 11]. Recently, graph-based
methods, such as FP-growth[5], have received agreat deal of attention, because they can quickly
manipulate large-scale itemset data by constructing compact graph structures in main memory.

A Theoretical Study on Variable Ordering of ZBDDs for Representing Frequent Itemsets

a
0
0
0
0
1
1
1
1

b
0
0
1
1
0
0
1
1

c
0
1
0
1
0
1
0
1

F
0
0
1
0
0
1
0
0

3

→S
→b

As a Boolean function:
F = abc ∨ abc→ ac

As a set of combinations:
S = {ac, b}

Figure 2: Correspondence of Boolean functions and sets of combinations.

Figure 3: BDD and ZBDD reduction rule.

The ZBDD-based method is a similar approachto handling sets of combinations in main memory
but is more eﬃcient because ZBDD is a kind of
DAG for representing itemsets, while FP-growthuses a tree representation for the same objects. In
general, DAGs can be more compact than trees.

Recently, our research group has developed aneﬃcient algorithm ZBDD-growth[9] to generate ZBDDs compactly representing all frequent itemsets
for given databases. Our method is not only enumerating/listing the frequent patterns but also eﬃciently analyzing the huge size of mining results byusing ZBDD operations. For example, extracting
all patterns including a certain items, or computing
the intersection/union/diﬀerence set for given two
sets of patterns. The computation time of those
operations does not directly depend on the numberof patterns but almost linear to the (compressed)
ZBDD size. It is an important advantage of using
ZBDDs.

3

Variable Ordering of ZBDDs
for Representing Frequent
Itemsets

As described above, it is possible for us to represent histograms of frequent pattern sets compactly
by using the ZBDD data structure. However, theZBDD size is quite sensitive with respect to theunderlying ordering of the variables. So, it is important to ﬁnd a good variable ordering such thatthe resulting ZBDD size is close to the smallest size
possible.

3.1

Properties of Variable Ordering in
Ordinary BDDs

In the ﬁeld of logic VLSI circuit design, many researchers have dealt with the problem of ﬁnding
good variable orderings for BDDs. For ordinary
BDDs, two features of the variable ordering are
known that aﬀect the size of the resulting BDDs [3].
(1) Pairs of inputs having the local computability property had better be kept close to one

4Shin-ichi Minato

another in the ordering.
(2) Inputs having a strong controllability to the
output had better be located at higher order.
As a typical example where the local computability dominates the BDD size, the following
AND-OR two-level logic function is known.
x1 x2 ∨ x3 x4 ∨ x5 x6 ∨ · · · x2n−1 x2nThis function can be represented by only
2n BDD nodes with the variable order:
x1 , x2 , x3 , x4 , . . . , x2n , where each pair of variables in the same product term are kept together,while we need (2n+1 −2) BDD nodes with the order:
x1 , x3 , . . . , x2n−1 , x2 , x4 , . . . , x2n , where those pairs
are kept away from each other. (see Fig. 4.)
On the other hand, the data-selector function is
known as another example where the output controllability dominates the BDD size. For example,
8-bit data-selector with three control inputs andeight data inputs has the function that one of thedata input is just selected by the 3-bit binary codeof control inputs. In this case, the function canbe represented by a linear size of BDDs when thecontrol inputs are higher than data inputs, but the
BDD becomes an exponential size in the reversal
order. (see Fig. 5.)
As shown the above, each of the both properties
may have an exponential impact to the BDD size.
Although one should try to come up with orderings obeying these two features, it may be diﬃcult
to do so, since these requirements are sometimes
contradictory. The problem of ﬁnding the optimalvariable ordering for BDDs is known to be NPcomplete [10]. In addition, there exist the functions which always require an exponential numberof BDD nodes for any variable ordering, so in suchcases, it is no use to make ordering.

3.2

Consideration on ZBDDs Representing Frequent Patterns

Now we consider the eﬀect of variable ordering for
the ZBDDs representing frequent itemsets. For thesake of simple discussion, ﬁrst we assume the minimum frequency alpha = 1, namely, we consider

the ZBDD enumerating all possible patterns whichappear at least once in the database. In this case,each tuple with k items generates 2k patterns, andthe total number of patterns may become O(2n )when n is the size of database description. Thus,
the ZBDD size may become exponential in theworst case.
The ZBDD of all patterns in the given databasecan be generated by computing the union of P (Tk )for all tuples T1 , T2 , . . . , Tm in the database, where
P (Tk ) means the sets of all patterns included in atuple Tk . Here we can observe the following property. If an item x appears in a tuple Tk , the patterns in P (Tk ) may or may not include x, therefore,
the item x contributes to double the number of patterns in P (Tk ). On the other hand, if x does notappear in Tk , the patterns in P (Tk ) never include x,
and thus the item x does not contribute to increase
the patterns.
Let us consider the analogy with the process ofgenerating an ordinary BDD for a given logic expression. When an input variable x appears in a
product term Tk in the logic expression, the variable x should be true to satisfy Tk , so the variable
x does not contribute to increase the satisﬁable solutions for the logic of Tk . On the other hand, if x
does not appear in Tk , the value of x may be false
or true, both possible to satisfy Tk , so the numberof solutions becomes twice.
Consequently, we can observe the completely
opposite eﬀects between the two facts that a variable appears in a term of the logic expression, andthat an item appears in a tuple of the database.
This observation indicates that we may discuss theeﬀect of ZBDD variable ordering by looking themissing items in a tuple as well as the variables
appearing in the logic expressions.

3.3

A Typical Example Dominated by
Local Computability

Based on the above consideration, we made an artiﬁcial database where the property of local com-A Theoretical Study on Variable Ordering of ZBDDs for Representing Frequent Itemsets

5

Figure 4: Eﬀect of BDD variable ordering for the AND-OR two-level logic function.

Figure 5: Eﬀect of BDD variable ordering for the data-selector function.

putability dominates the ZBDD size, as follows.
T 1 a2 a3 a4 · · · an b 2 b 3 b 4 · · · b n
T 2 a1 a3 a4 · · · an b 1 b 3 b 4 · · · b n
T 3 a1 a2 a4 · · · an b 1 b 2 b 4 · · · b n.. .. .. ..
..
.. .. ..
..
. . . .
.
. . .
.
Tn a1 a2 a3 · · · an−1 b1 b2 b3 · · · bn−1

This database consists of the tuples Tk (k =1, ..., n) each of which has almost all items
a1 a2 ... an b1 b2 ... bn but only one pair of items
ak and bk are missing. If we consider the opposite
property of item appearance, this database corresponds to the AND-OR two-level logic expression
shown in Section 3.1, and we can expect that thepairs of two items missing from the same tuple havethe property of local computability.
To conﬁrm our consideration, we generated the
ZBDDs representing all patterns included in the
database. Table 1 shows the ZBDD size of the two
diﬀerent variable order. The result obviously shows
an exponential diﬀerence between the two ordering. It is intuitively explained as follows. In theorder2, the items a1 to ak are ordered in the higher
positions, but there is no opportunity to share the
ZBDD nodes only by the item a’s information without b’s, so just a binary tree are generated for theﬁrst n stages and thus at least (2n − 1) nodes are
generated. On the other hand, when we use the6Shin-ichi Minato

Table 1: Experimental results for the databases dominated by local computability.
Order1: a1 b1 a2 b2 . . . an bn
Order2: a1 a2 . . . an b1 b2 . . . bn
n ZBDD size (order1) ZBDD size (order2) Total patterns
3
10
16
37
4
15
39
175
5
20
86
781
6
25
181
3,367
7
25
372
14,197830
755
58,9759
35
1,522
242,46110
40
3,057
989,52711
45
6,1284,017,157
12
50
12,271
16,245,775
other order such that ak and bk are kept closer, theZBDD nodes can be shared by using combinatorial
information of ak and bk on each stage, thus the
ZBDD size becomes O(n).

3.4

A Typical Example Dominated by
Output Controllability

Based on the above consideration, we made an artiﬁcial database where the property of output controllability dominates the ZBDD size. The following database corresponds to the 8-bit data-selector
function, shown in Section 3.1.
T0
T1
T2
T3
T4
T5
T6
T7

x1
x0
x0
x0
x0
x0
x0
x0

x2
x2
x1
x1
x1
x1
x1
x1

x3
x3
x3
x2
x2
x2
x2
x2

x4
x4
x4
x4
x3
x3
x3
x3

x5
x5
x5
x5
x5
x4
x4
x4

x6
x6
x6
x6
x6
x6
x5
x5

x7
x7
x7
x7
x7
x7
x7
x6

y0
y0
y0
y0
y1
y1
y1
y1

y2
y2
y3
y3
y2
y2
y3
y3

y4
y5
y4
y5
y4
y5
y4
y5

This database has the items x0 x1 . . . xn−1 asthe data inputs and y0 y1 . . . ym (m = 2log2 n)as the control inputs. The control inputs have thepair-wise structure as (y0 , y1 ), (y2 , y3 ), . . ., each ofwhich represents a digit of binary coded number.
Either of odd or even numbered y appears on eachtuple Tk in the database, to represent the value
0/1 of the binary code for k. The tuple Tk also includes all items x0 to xn except xk . With the opposite property of item appearance, we can consider

that this database selects one of the data input
xk according to the binary coded number speciﬁedby the control inputs, as well as the data-selector
function shown in Section 3.1.
When generating a ZBDD for the sets of all possible patterns included in this database, we can expect that the ZBDD will become a linear size when
the control inputs y’s are higher than data inputs
x’s, but it will become an exponential size in thereversal order. It is explained as follows. If we ﬁrst
assign a set of values into all the items y’s, the restof patterns of x’s are related only to one or twotuples in the database, so each ZBDD subgraphfor items x’s becomes a beautiful array structurewith n nodes. A pair of (yi , yi+1 ) may cause threepatterns: only yi appears, only yi+1 appears, orboth absent, so, the upper part of ZBDD for y’s
become a ternary tree for the log2 n-bit of binary code. The total ZBDD nodes are bounded byO(n · 3log2 n ) ≈ O(n2.7 ).
On the other hand, when we use the reversal
order such that x’s are higher than y’s, there is noopportunity to share the ZBDD nodes only by x’s
information without y’s, so just a binary tree are
generated for the ﬁrst n stages and thus at least(2n − 1) nodes are required.
To conﬁrm our consideration, we generated the
ZBDDs representing all patterns included in the
database. Table 2 shows the ZBDD size of thetwo diﬀerent variable order. The result obviously
shows an exponential diﬀerence between the two

A Theoretical Study on Variable Ordering of ZBDDs for Representing Frequent Itemsets

7

Table 2: Experimental results for the databases dominated by output controllability.
n (number of x’s) ZBDD size(y’s higher) ZBDD size(x’s higher) Total patterns
8
126
579
5,023
12
339
5,117
227,295
16
650
137,444
4,159,487
20
1,151
2,435,284
161,496,559
orders. Thus, we can see that there exists an example where the property of output controllability
has an exponential impact for the ZBDD size.

3.5

A Case of Generating Exponential
ZBDD in Any Variable Ordering

Based on the above observation, we can show that
there exists a database where the ZBDD representing the set of patterns must be an exponential
size in any variable ordering. The “data-selector”
database, shown in the last section, consists of thetwo sorts of items x’s and y’s. We must put they’s higher than x’s to avoid exponential explosionof ZBDD size. Now, let us deﬁne N as the total number of items (= n + 2log2 n), then we
make N copies of the databases with the N different variable orders by rotating the items one byone, as shown in Fig. 6, and ﬁnally we merge the
all N blocks into one database. If we generate a
ZBDD for the sets of all patterns in this database,any variable ordering cannot avoid a bad variable
order, because, at least one of the blocks, morethan N/2 items of x’s become higher than y’s. So,
we need O(2N/2 ) ZBDD nodes for representing thepatterns for one of the blocks with a bad variable
order. Since the initial data size of this databaseis O(N 3 ), we can conclude that this database requires an exponential size of ZBDD in any variable
ordering.

3.6

Eﬀect of the Minimum Frequency
ThresholdIn the above discussions, we assume the minimum
frequency threshold α = 1, it means that the ZBDDs represent the sets of all possible patterns included in the databases. However, in the real applications, we specify a larger α to reduce the numberof frequent patterns into a feasible amount, and thesize of the ZBDD is also reduced. If the number of
frequent patterns are not exponential for a given
large α, then the ZBDD size never become exponential, and in such cases, the variable ordering
does not have an exponential eﬀect to the ZBDD
size.
Table 3 is the experimental result for the same
database as shown in Section3.3 with a diﬀerent
threshold α = n/2, namely, representing the set of
frequent patterns which appears at more than halftuples in the database. The result shows that thevariable ordering still has an exponential impact tothe ZBDD size when α = n/2. In this example,
we expect that as long as we specify an α proportional to n, the similar exponential impact will beobserved.

4

Conclusion

In this paper, we presented a theoretical study
on ZBDD variable ordering for representing frequent itemsets. We found the two typical databases
where the ZBDD sizes are exponentially sensitive
to the variable ordering, and we discussed why sucha remarkable diﬀerence occurs. In addition, we
also showed that there is a case where the ZBDD
size must be exponential in any variable ordering. These discussions clarify the property of variable ordering when we apply the ZBDD-based data
structure to data mining problems. Recently, we
proposed a heuristic variable ordering method[6]that ﬁnds a good variable order before generating
ZBDDs, by using the structural information of thegiven database. Such a heuristic method is developed based on the theoretical results discussed inthis paper.

8Shin-ichi Minato

Figure 6: N copies of “data-selector” databases with the rotated variable orders.

Table 3: Same database as Table 1 with the diﬀerent threshold α = n/2.
Order1: a1 b1 a2 b2 . . . an bn
Order2: a1 a2 . . . an b1 b2 . . . bn
n ZBDD size (order1) ZBDD size (order2) Total patterns
3
8
8
67
4
16
30
106
5
22
47
781
6
33
142
694
7
42
222
1,156
8
56
616
7,459
9
68
969
12,89610
85
2,564
81,922
11
100
4,074
143,980
12120
10,503
912,718

Acknowledgment
The author would like to thank Thomas Zeugmannand Hiroki Arimura of Hokkaido University for theirvaluable discussions and comments. This research waspartially supported by Japan Society for the Promotion of Science, Grant-in-Aid for Scientiﬁc Research (B)on “ZBDD-based Database Analysis,” 17300041, 2007,
and Grant-in-Aid for Specially Promoted Research on“Semi-Structured Data Mining,” 17002008.

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, editors, Proc. of the 1993 ACM SIGMODInternational Conference on Management of
Data, Vol. 22(2) of SIGMOD Record, pages
207–216, 1993.

[2] R. E. Bryant. Graph-based algorithms forboolean function manipulation. IEEE Transactions on Computers, C-35(8):677–691, 1986.
[3] M. Fujita, H. Fujisawa, and N. Kawato. Evaluation and implementation of boolean comparison method based on binary decision diagrams. In Proc. of ACM/IEEE International
Conf. on Computer-Aided Design (ICCAD88), pages 2–5, 1988.
[4] B. Goethals. Survey on frequent patternmining, 2003. http://www.cs.helsinki.fi/
u/goethals/publications/survey.ps.
[5] J. Han, J. Pei, Y. Yin, and R. Mao. Mining
frequent patterns without candidate generation: a frequent-pattern tree approach. Data
Mining and Knowledge Discovery, 8(1):53–87,
2004.
[6] H. Iwasaki, S. Minato, and T. Zeugmann.
A method of variable orderingA Theoretical Study on Variable Ordering of ZBDDs for Representing Frequent Itemsets

for zero-suppressed binary decision diagramsin data mining applications. In Proc. of
The Third IEEE International Workshop on
Databases for Next-Generation Researchers(SWOD2007), collocated with ICDE-2007,
2007.
[7] S. Minato. Zero-suppressed BDDs for set manipulation in combinatorial problems. In Proc.
of 30th ACM/IEEE Design Automation Conference, pages 272–277, 1993.
[8] S. Minato. Zero-suppressed BDDs and theirapplications. International Journal on Software Tools for Technology Transfer (STTT),
Springer, 3(2):156–170, 2001.
[9] S. Minato and H. Arimura. Frequent pattern mining and knowledge indexing based on
zero-suppressed BDDs. In The 5th International Workshop on Knowledge Discovery in
Inductive Databases (KDID’06), pages 83–94,
9 2006.
[10] S. Tani, K. Hamaguchi, and S. Yajima. The
complexity of the optimal variable ordering
problems of shared binary decision diagrams.
In 4th International Symposium on Algorithms
and Computation, volume LNCS-762, pages
389–398. Springer, 1993.
[11] M. J. Zaki. Scalable algorithms for association mining. IEEE Trans. Knowl. Data Eng.,
12(2):372–390, 2000.

9