TCS -TR-A-06-22

TCS Technical Report

Symmetric Item Set Mining Method Using ZBDDs
and Application to Biological Databy

Shin-ichi Minato and Kimihito Ito

Division of Computer Science
Report Series A
November 11, 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

Symmetric Item Set Mining Method Using ZBDDs
and Application to Biological Data
Shin-ichi Minato

Kimihito Ito

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

Research Center for Zoonosis Control
Hokkaido University
North 18, West 9
Sapporo 060-0818, Japan

November 11, 2006

After generating frequent item set data, wesometimes faced with the problem that the resultsof item sets are too large and complicated to retrieve useful information. Therefore, it is important for practical data mining to extract the key
structures from the item set data. Closed/maximal
item set mining[16] is one of the useful methods toﬁnd important item sets. Disjoint decomposition ofitem set data[13] is another powerful method for extracting hidden structures from frequent item sets.

(Abstract) In this paper, we present a methodof ﬁnding symmetric items in a combinatorial item
set database. The techniques for ﬁnding symmetric variables in Boolean functions have been studied
for long time in the area of VLSI logic design, andthe BDD (Binary Decision Diagram) -based methods are presented to solve such a problem. Recently, we have developed an eﬃcient method forhandling databases using ZBDDs (Zero-suppressed
BDDs), a particular type of BDDs. In our ZBDDbased data structure, the symmetric item sets canbe found eﬃciently as well as for Boolean functions. We implemented the program of symmetric
item set mining, and applied it to actual biological data on the amino acid sequences of inﬂuenza
viruses. We found a number of symmetric items
from the database, some of which indicate interesting relationships in the amino acid mutation patterns. The result shows that our method is helpful for extracting hidden interesting information in
real-life databases.

1

In this paper, we propose one more interesting
method for ﬁnding hidden structure from largescale item set data. Our method is based on thesymmetry of items. It means that the exchange ofa pair of symmetric items has completely no eﬀect
for the database information. This is a very strict
property and it will be a useful association rule forthe database analysis.
The symmetry of variables is a fundamental concept in the theory of Boolean functions, and themethod of symmetry checking has been studied forlong time in VLSI logic design area. There aresome state-of-the-art algorithms[14, 7] using BDDs
(Binary Decision Diagrams)[2] to solve such a problem. The BDD-based techniques can be applied todata mining area. Recently, we found that ZBDDs (Zero-suppressed BDDs)[9] are very suitable
for representing large-scale item set data used intransaction database analysis[12].

Introduction

Frequent item set mining is one of the fundamental
techniques for knowledge discovery. Since the introduction by Agrawal et al.[1], the frequent item
set 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[3].

In this paper, we discuss the property of symmetric items in transaction database, and thenpresent an eﬃcient algorithm to ﬁnd all symmetric1

2

Shin-ichi Minato and Kimihito Itoitem sets using ZBDDs. We also show the experimental result for an actual biological database on
the amino acid sequences of inﬂuenza viruses[8][6].
We found a number of symmetric items from thedatabase, some of which indicate an interesting relationship of amino acid mutation patterns. The
result shows that our method is helpful for extracting hidden information in real-life databases.

2

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

Preliminaries

Here we brieﬂy describe the basic techniques of
BDDs and ZBDDs for representing combinatorial
item sets 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 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 [2] for details.)• Delete all redundant nodes whose two edges
point to the same node. (Fig. 3(a))• Share all equivalent sub-graphs. (Fig. 3(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. 2, 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[2], we can eﬃciently construct a BDD for the result of a binary

2.2

ZBDDs and combinatorial item sets

BDDs are originally developed for handling
Boolean function data, however, they can also be
used for implicit representation of combinatorial
item sets. Here we call “combinatorial item set”
for a set of elements each of which is a combinationout of n items. This data model often appears inreal-life problems, such as combinations of switching devices(ON/OFF), fault combinations, and setsof paths 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 combinatorial item
set is a subset of the power set of n items.
A combinatorial item set 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
combinatorial item set. Such Boolean functions arecalled characteristic functions. For example, theleft side of Fig. 5 shows a truth-table representing
a Boolean function (abc) ∨ (bc), but also represents
a combinatorial item set {ab, ac, c}. Using BDDs
for characteristic functions, we can implicitly andcompactly represent combinatorial item sets. The
logic operations AND/OR for Boolean functions
correspond to the set operations intersection/unionfor combinatorial item sets. By using BDDs forcharacteristic functions, we can manipulate combinatorial item sets eﬃciently. They can be generated and manipulated within a time roughlySymmetric Item Set Mining Method Using ZBDDs and Application to Biological Data

F
a

F

1

a

0

0

1

F1
0

c

3

b

b 1

0

0

1
0

1

0

0

1

1

c

c

1 0

1 0

1

0

0

1

F2

F3

c
1

0

0

1

c

a
1

1

a

1
0

0

1

0

a
1

b

1

1

0

(a) BDD.

F4

b 1

b
0

(b) Binary tree.
10

F 1 = a∧b
F 2 = a⊕b
F3 = b
F 4 = a∨b

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

x
0

jump
1

x

x

x share

0 1

0 1

0 1

x
f

f

f0

(a) Node deletion.

f1

f0

0

f1

(b) Node sharing.
f

Figure 3:
BDDs

Jump
1

0

f

Reduction rules of ordinary

proportional to the BDD size. When we handle many combinations including similar patterns(sub-combinations), BDDs are greatly reduced bynode sharing eﬀect, and sometimes an exponential
reduction beneﬁt can be obtained.

Figure 4: ZBDD reduction rule.

canonical forms as well as ordinary BDDs under aﬁxed variable ordering.
Here we summarize the features of ZBDDs.

• Share equivalent nodes as well as ordinary
BDDs.

• In ZBDDs, the nodes of irrelevant items (neverchosen in any combination) are automaticallydeleted 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. In
this case, 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.

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 aterminal node. It is proved that ZBDDs also give

• 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.

Zero-suppressed BDD (ZBDD)[9] is a special type of BDDs for eﬃcient manipulation of combinatorial item sets. ZBDDs are based on the following special reduction rules.
• 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.

4Shin-ichi Minato and Kimihito Ito

Figure 5: Eﬀect of ZBDD reduction rule.

• 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. Namely, (the order of) ZBDD
size never exceeds the explicit representation.
If more nodes are shared, the ZBDD is morecompact than linear list.
The detailed techniques of ZBDD manipulation
are described in the articles[9, 11]. A typical ZBDD
package supports cofactoring operations to traverse
0-edge or 1-edge, and binary operations between
two combinatorial item sets, such as union, intersection, and diﬀerence. The computation time foreach operation is almost linear to the number of
ZBDD nodes related to the operation.

3

Symmetric item sets in transaction databases

3.1

Symmetry of variables in Booleanfunctions

The symmetry is a fundamental concept in the theory of Boolean functions. A symmetric Booleanfunction means that any exchange of input variables has no eﬀect for the output value. In otherwords, the output value is decided only by the total number of true assignments in the n-input variables. The parity check functions and threshold

Figure 6: Four sub-functions for symmetry checking.

functions are typical examples of symmetric functions.
When the function is not completely symmetric,
we sometimes ﬁnd partial groups of symmetric variables. If two variables are exchangeable without
any output change, we call them symmetric variables in the function. An obvious property holds
that if the pairs (a, b) and (a, c) are both symmetric, then any pair in (a, b, c) is symmetric.
As ﬁnding symmetric variables leads to compact
logic circuits, it has been studied for long timein VLSI logic design area. In order to check thesymmetry of the two variables v1 and v2 in thefunction F , as shown in Fig. 6, we ﬁrst extractfour sub-functions: F00 , F01 , F10 , and F11 by assigning all combinations of constant values 0/1 into v1
and v2 . We then compare of F01 and F10 . If thetwo are equivalent, we can see the two variables

Symmetric Item Set Mining Method Using ZBDDs and Application to Biological Data

5

item sets from the given databases. This method
can be used not only for original database but also
for frequent item set data to ﬁnd some relationships
between the items.

4

Figure 7: Four sub-combinations for symmetry
checking.

are symmetric. In principle, we need n(n − 1)/2
times of symmetry checks for all possible variable
pairs. There have been proposed some state-of-theart algorithms[14, 7] using BDDs (Binary Decision
Diagrams)[2] to solve such a problem eﬃciently.

3.2

Symmetric Items in combinatorial
item sets

Here we discuss the symmetry of items in a combinatorial item set. For example we consider thefollowing combinatorial item set:S = {abc, acd, ad, bcd, bd, c, cd}.
In this case, the item a and b are symmetric
but the other pairs of variables are not symmetric. The symmetry can be conﬁrmed as shownin Fig. 7. First we classify the combinations into
four categories: (1) both a and b included, (2)only a is included, (3) only b is included, and (4)neither included. Namely, it can be written as:
S = abS11 ∪ aS10 ∪ bS01 ∪ S00 . Then, we can determine the symmetry of a and b by comparing
S10 and S01 . If the two subsets are equivalent,a and b are exchangeable. For the above example, S11 = {c}, S10 = {cd, d}, S01 = {cd, d}, and
S00 = {c, cd}. We can see a and b are symmetricas S10 = S01 .
Even if we do not know the actual meaning of
the item a and b in the original database, we can
expect that a and b would have somehow strong
relationship if the symmetric property holds. It isa kind of hidden information. It would be a usefuland interesting task to ﬁnd all possible symmetric

ZBDD-based algorithm forfinding symmetric item sets

As shown in article[12], the ZBDD-based data
structure is quite eﬀective (exponentially in extreme cases) for handling transaction databases,
especially when the item sets include many similar partial combinations. Now we show an eﬃcientalgorithm of ﬁnding symmetric item sets based on
ZBDD operations.
First we explain the cofactor operation on ZBDDs. Cofactor(S, v) classiﬁes a combinatorial item
set S into the two subsets, one of which includes
the item v and the other does not. Namely, it extracts S1 and S0 such that S = vS1 ∪S0 . If the item
v is the top (highest ordered) item in the ZBDD,
then S1 and S0 are the two sub-graphs pointed by
1-edge and 0-edge of the top decision node, andthe cofactor operation can be done in a constanttime. Therefore, if the item v1 and v2 are the ﬁrst
and second top items in the ZBDD, the symmetry
checking is quite easy because S10 (subset with v1
but not v2 ) and S01 (subset with v2 but not v1 ) canbe extracted and compared in a constant time.
This “naive” checking method works quite efﬁciently only if the v1 and v2 are at the highest
positions. Otherwise, we have to generate temporary ZBDDs for S10 and S01 by cofactor operations. If S10 and S01 are quite diﬀerent, we mayeasily ﬁnd the asymmetry of two items by checking a small part of ZBDDs. However, the naive
method always generates the whole ZBDDs for S10
and S01 and then compare them. To address thisineﬃciency, we developed an eﬃcient recursive algorithm as presented in 8.
In this algorithm, ﬁrst we get the top item t in
the ZBDD S, and extract S1 and S0 as the cofactorsof S by t. We then recursively check the symmetryof (v1 , v2 ) for each subset S1 and S0 , and if they
are symmetric for the both, we can see they are
symmetric for S.

6Shin-ichi Minato and Kimihito Ito

SymChk(S, v1 , v2 ) /* Assume v1 higher than v2 in the ZBDD ordering.*/{
if (S = 0 or S = 1) return 1 ;r ← Cache(S, v1 , v2 ) ;if (r exists) return r ;t1 ← S.top ; /* Top item in S */if (t1 higher than v1 )(S1 , S0 ) ← (Cofactors of S by t1 ) ;r ← SymChk(S1 , v1 , v2 ) && SymChk(S0, v1 , v2 ) ;else(S1 , S0 ) ← (Cofactors of S by v1 ) ;t2 ← Max(S1 .top, S0 .top) ; /* Top item in S1 , S0 */if (t2 higher than v2 )(S11 , S10 ) ← (Cofactors of S1 by t2 ) ;(S01 , S00 ) ← (Cofactors of S0 by t2 ) ;r ← SymChk((t2 S11 ∪ S10 ), t2 , v2 ) && SymChk((t2 S01 ∪S00 ), t2 , v2 ) ;else(S11 , S10 ) ← (Cofactors of S1 by v2 ) ;(S01 , S00 ) ← (Cofactors of S0 by v2 ) ;r ← (S10 = S01 )? 1 : 0 ;
endif
endif
Cache(S, v1 , v2 ) ← r ;return r ;}Figure 8: Sketch of the symmetry checking algorithm.

This procedure may require an exponential
number of recursive calls in terms of the numberof items higher than v1 , v2 in the ZBDD, however,
we do not have to execute the procedure twice forthe same ZBDD node because the results will be
the same. Therefore, the number of recursive calls
is bounded by the ZBDD size, by using a hashbased cache to save the result of procedure for each
ZBDD node. In addition, if we found the two items
are asymmetric either for S1 or S0 , we may immediately quit the procedure and conclude they areasymmetric for S.
In our checking algorithm, the cofactor operation is always applied to the highest ordered items,
and each recursive procedure can be executed in aconstant time. Thus, the total computation time
is bounded by O(|G|), where |G| is the ZBDD sizefor S. Repeating this procedure for all item pairs
in S, we can extract all possible symmetric item
sets in O(n2 |G|) time, where n is number of items.
The time will be shorter in practice because themost of item pairs are asymmetric in usual cases.
In addition, the beneﬁt of hash-based cache can beshared in the repetition of checking diﬀerent item

pairs.
Lastly we note that there have been several efﬁcient symmetry checking algorithms for Booleanfunction data using ordinary BDDs[14, 7], but it is
not trivial to apply the techniques to the ZBDDs
since the primitive operations of ZBDDs are diﬀerent from those of ordinary BDDs. Our work is theﬁrst proposal of the eﬃcient symmetry checking algorithm for combinatorial item sets using ZBDDs.

5

Implementation and Application to biological data

We implemented our symmetric checking algorithm. The program is based on our own ZBDD
package, and additional 70 lines of C++ code forthe symmetry checking algorithm. We used a
Pentium-4 PC, 800MHz, 1.5GB of main memory,with SuSE Linux 9. We can manipulate up to
20,000,000 nodes of ZBDDs in this PC.

7

Symmetric Item Set Mining Method Using ZBDDs and Application to Biological Data

Table 1: Experimental result for basic performance evaluation
Data name#Item#Record#Tuplemushroom
T10I4D100K
pumsb
BMS-Web-View-1
accidents

119
870
2,113
497
468

8,124
100,000
49,04659,602
340,183

8,124
89,13548,474
18,473339,898

ZBDD
nodes
8,006
547,777
1,749,775
42,6293,876,468

Time(sec) for
ZBDD gen.
1.1
59.2
166.7
24.9
127.5

Sym.
pairs
19
0
90
6
11

Time(sec)
for sym.chk.
0.6
61.7
1,152.0
30.2
18.0

Table 2: Comparison to naive checking method.
Data namemushroom
T10I4D100K
pumsb
BMS-Web-View-1
accidents

5.1

Time(sec) for sym.chk.
our method naive method.
0.6
1.2
61.7
28,482.0
1,152.0(> 24h)
30.2
251.8
18.0
53,290.3

Experiment for basic performance
evaluation

For evaluating the basic performance, we applied
our method to the practical transaction databases
chosen from FIMI2003 benchmark set[4]. We ﬁrst
constructed a ZBDD for the set of all tuples inthe database, and then apply our symmetry checking algorithm for all item pairs. The results areshown in Table 1. “Sym. pairs” shows the numberof symmetric pairs we found. Our result demonstrates that we succeeded in extracting all symmetric item sets for a practical size of databases withina feasible computation time. We can see that nosymmetric pairs are found in “T10I4D100K.” It isa reasonable result because this data is randomly
generated and there is no strong relationship between any pair of items.

Table 2 shows the comparison of our symmetry
checking algorithm to the “naive” method, which
always generates the whole ZBDDs for S10 and
S01 and then compare them. The diﬀerences ofcomputation time are more than hundred times inlarger instances. This result shows that our recursive checking algorithm is remarkably eﬀective toﬁnd symmetric item pairs.

5.2

Experiment of biological data analysis

Hokkaido University Research Center for Zoonosis
Control is conducting a research project for analyzing the mutations in the hemagglutinins of inﬂuenza viruses, in order to predict possible structural changes in the future inﬂuenza viruses[6]. The
hemagglutinin (HA) is the major surface glycoprotein of inﬂuenza viruses and plays an importantrole in virus entry into host cells. The amino acidsequences of HAs mutate every year, and the continuously cause epidemic in the world.
We applied our method to a real-life biological
data, the amino acid sequences of the HA of humaninﬂuenza viruses.
The data we used are the 1,657 instances ofamino acid sequences of type “H3N2” HAs of human inﬂuenza viruses, isolated during 1968 to 2006
in the world. Each sequence has 328 positions ofamino acids, and each position has one of the 20
amino acid types: {R, K, H, P, A, L, G, V, I, W,
M, S, Y, Q, T, F, N, C, E, D}. Namely, the total
combinatorial space is as many as 20328 . The sequence data also has a ﬁeld of the year when thevirus was isolated. The data is available at the
public database of NCBI Inﬂuenza resources[15].
In our experiment, we prepared primitive items
as all possible pairs of a position and a amino acidtype. We used 20 × 328 = 6, 560 diﬀerent items in
total. For example, the item “125T” means that

8

1999

1998

1997

1996

1995

1994

1993

1992

1990
1991

1989

1988

1986
1987

1973
1974
1975
1976
1977
1978
1979
1980
1981
1982
1983
1984
1985

R
K
H
P
A
L
G
V
I
W
M
S
Y
Q
T
F
N
C
E
D
1968
1969
1970
1971
1972

amino acid

Shin-ichi Minato and Kimihito Ito

year

2006

2005

2004

2003

2002

2001

2000

1999

225
193

year

Figure 9: Mutations at the 225th and the 193rd amino acid positions.

the amino acid “T” appears at the 125th position.
We used the letter “X” when the data of a position is missing, for instance, “167X” means that
we don’t know the amino acid at the 167th position. The ﬁeld of the year is expressed as “Y1989.”
In this way, the sequence data can be represented
as follows:
Y1968 1Q 2D 3L 4P 5G ... 326K 327Q 328T
Y1973 1Q 2D 3F 4P 5G ... 326K 327Q 328T
Y1999 1Q 2K 3L 4P 5G ... 326K 327Q 328T···
The data contains 1,657 lines of such combinatorial
item sets.
We conducted an experiment of generating a
ZBDD for the amino acid sequence data and thenextracting all symmetric item sets from the ZBDDs. In our result, the number of ZBDD nodes
is 168,261. The CPU time just for ZBDD construction was 17.9 second. Next, we execute ouralgorithm of symmetric item set mining for the

ZBDD. The total computation time for checking
21,513,520(= 6560 C2 ) item pairs was 725 sec, andwe found 64 groups of symmetric items, as follows.
(324P 321R 320M 314L 306P 301T 296N 290N
287S 281C 277C 266S 256G 255R 254P 250N 241D
240G 237V 224R 200G 191Q 181G 166V 153W
147F 136S 134G 132Q 125F 123E 119E 116G 113A
111L 100Y 90R 89E 84W 76C 73D 71L 70L 69A
68D 66L 65T 64C 61G 52C 42L 39A 28T 26V
18H) (13W 12R 11Q 10R 9A 7T 6M) (309A 307X
303R 258X 232M 117X 24X) (303X 187M 180X
133X 120C 60X) (212L 210K 209C 108V 107C)(74X 62X 47X 21X 2X) (322Y 311P 310E 276S
86I) (322X 318X 294C 234X 19X) (328L 327K 326I
323E) (258S 238R 164V 1P) (173G 163M 104E
62A) (225A 211X 183Q 6D) (190N 186D 15M)
(203A 198P 11T) (235A 216Y 115P) (214V 23R
3M) (327R 127L 110L) (159R 118M 34T) (146R
139F 31V) (180W 120F 60D) (225N 193F) (225H
33R) (104G 93S) (298D 124R) (252T 152S) (218X
140I) (95C 94T) (131D 33N) (87I 80L) (275E 46L)
(304V 72X) (140T 139X) (328P 325X) (257F 98N)
(219T 2R) (327L 325Q) (193T 183P) (218A 205C)(21R 17R) (144A 126S) (328S 294Y) (187K 156S)

Symmetric Item Set Mining Method Using ZBDDs and Application to Biological Data

(311E 170H) (244M 83R) (53S 6K) (114L 9K)(309G 213R) (173R 124E) (212A 133G) (172A
80R) (292Q 291H) (15X 14X) (97S 96Y) (236T
226P) (319R 249A) (278V 169S) (319G 249G)(318T 234W) (257Y 98Y) (235T 115S) (232I 24T)
(210Q 108L) (127W 110S) (126T 83T)

In the result, the ﬁrst symmetric group of a large
number of items represents the items commonly appear in all the sequences, in other words, they are
the amino acid positions which have never changed.
The other symmetric groups are related to a partof sequences, and the pair of positions may havesome interesting biological relationship. For example, (225N 193F) is one of the symmetric item pair,
and we checked the mutations of the 225th and the193rd amino acid positions with our visualization
tool[5]. Some portions of the graphic output are
shown in Fig. 9. We can observe that the two aminoacid positions have a strong co-relation in the very
recent sequences after 2005.
There is a related work[6] to extract co-relatedamino acid positions based on mutual information
analysis. The calculation of mutual information
also gives a relationship between the two positions,however, it indicates the total behaviors of all sequence data, and would not be eﬀective to ﬁnd a
relationship sharply seen in a portion of sequence
instances. Our method will be useful to detect such
relationships.
The symmetric item sets extracted in our
method does not always correspond to biologicallymeaningful relationships, however, some of them
may have such interesting information. We have already known many kind of data mining techniquessuch as frequent pattern mining, closed patternmining, etc. Our symmetric item set mining will bea new alternative method for knowledge discovery.

6

Conclusion

In this paper, we presented an eﬃcient method
for extracting all symmetric item sets in transaction databases. The experimental results show that
our method eﬃciently extracts hidden informationfrom the large-scale database. It is applicable to9a real-life biological database, which includes 6,560
items and requires 21,513,520 pairs of symmetry
checking. Our method will be useful to detect a
sharp relationship hidden in a limited portion of
database and may also be useful for pruning noisydata.
As our future work, we are considering more efﬁcient algorithm to be applied for more larger ZBDDs, and it would also be interesting to develop“approximately” symmetry checking method whichallows some errors or noise in the data.

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 SIGMODInternational Conference on Management of
Data, Vol. 22(2) of SIGMOD Record, pp. 207–
216, ACM Press, 1993.
[2] Bryant, R. E., Graph-based algorithms for
Boolean function manipulation, IEEE Trans.
Comput., C-35, 8 (1986), 677–691.
[3] B. Goethals, “Survey on Frequent Pattern
Mining”, Manuscript, 2003.
http://www.cs.helsinki.fi/u/goethals/
publications/survey.ps[4] B. Goethals, M. Javeed Zaki (Eds.), Frequent
Itemset Mining Dataset Repository, Frequent
Itemset Mining Implementations (FIMI’03),
2003.
http://fimi.cs.helsinki.fi/data/[5] Hokkaido University Research Center for
Zoonosis Control, PlotH3N2, Available from:http://www.czc.hokudai.ac.jp/~murakami/
plot-H3N2/[6] K. Ito, M. Igarashi, H. Kida, and A.
Takada, “Computer Analysis of Structural
Changes in H3 Hemagglutinins of Human Inﬂuenza Viruses Isolated During 1968 to 2006,”
Thirteenth International Conference Negative
Strand Viruses 2006, p.28, 2006.

10[7] N. Kettle and A. King: “An Anytime Symmetry Detection Algorithm for ROBDDs,” In
Proc. IEEE/ACM 11th Asia and South Paciﬁc
Design Automation Conference (ASPDAC2006), pp. 243–248, Jan. 2006.
[8] Krug,
R.M.
and
Lamb,
R.A.,Orthomyxoviridae: The Viruses andTheir Replication, Fields Virology. 4thedition, editors: Knipe DM, Howley PM,.
Philadelphia: Lippincott Williams & Wilkins.
2001.
[9] Minato, S., Zero-suppressed BDDs for set manipulation in combinatorial problems, In Proc.
30th ACM/IEEE Design Automation Conf.
(DAC-93), (1993), 272–277.
[10] S. Minato: “Binary Decision Diagrams andApplications for VLSI CAD”, Kluwer Academic Publishers, November 1996.
[11] 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.
[12] S. Minato and H. Arimura: ”Eﬃcient Combinatorial Item Set Analysis Based on ZeroSuppressed BDDs”, IEEE/IEICE/IPSJ International Workshop on Challenges in Web Information Retrieval and Integration (WIRI2005), pp. 3–10, Apr., 2005.
[13] S. Minato: “Finding Simple Disjoint Decompositions in Frequent Itemset Data Using Zero-suppressed BDD,” In Proc. of IEEEICDM 2005 workshop on Computational Intelligence in Data Mining, pp. 3-11, ISBN-09738918-5-8, Nov. 2005.
[14] A. Mishchenko, “Fast Computation of Symmetries in Boolean Functions,” IEEE Trans.
Computer-Aided Design, Vol. 22, No. 11,
pp. 1588–1593, 2003.
[15] National Center for Biotechnology Information, “Inﬂuenza virus resource,” Jun 23, 2005.
Available from:

Shin-ichi Minato and Kimihito Ito

http://www.ncbi.nlm.nih.gov/genomes/
FLU/FLU.html[16] T. Uno, T. Asai, Y. Uchida and H. Arimura,“An Eﬃcient Algorithm for Enumerating
Closed Patterns in Transaction Databases,” In
Proc. of the 8th International Conference on
Discovery Science 2004 (DS-2004), 2004.