Detailed Description of an Algorithm for Enumeration of Maximal
Frequent Sets with Irredundant Dualization
Takeaki Uno, Ken Satoh
National Institute of Informatics
2-1-2 Hitotsubashi, Chiyoda-ku, Tokyo, 101-8430, Japan
Email: uno, ksatoh@nii.ac.jp
Abstract

avoids checking all frequent item sets. However, thisalgorithm solves dualization problems many times,
hence it is not fast for practical purpose. Moreover,
the algorithm uses the dualization algorithm of Fredman and Khachiyan [Fredman96] which is said to be
slow in practice.
We improved the algorithm in [SatohUno03] byusing incremental dualization algorithms proposedby Kavvadias and Stavropoulos [Kavvadias99], andUno [Uno02]. We developed an algorithm by interleaving dualization with ﬁnding maximal frequent
sets. Roughly speaking, our algorithm solves one dualization problem with the size |Bd+ |, in which Bd+
is the set of maximal frequent sets, while the algorithm of Gunopulos et al. solves |Bd+ | dualization
problems with sizes from 1 through |Bd+ |. This reduces the computation time by a factor of 1/|Bd+|.
To reduce the computation time more, we used
Uno’s dualization algorithm [Uno02]. The experimental computation time of Uno’s algorithm is linear in the number of outputs, and O(|E|) per output, while that of Kavvadias and Stavropoulos seems
to be O(|E|2 ). This reduces the computation timeby a factor of 1/|E|. Moreover, we add an improvement based on sparseness of input. By this, theexperimental computation time per output is reduced to O(ave(Bd+ )) where ave(Bd+ ) is the average size of maximal frequent sets. In summary,
we reduced the computation time by a factor ofave(Bd+ ) / (|Bd+ | × |E|2 ) by using the combination of the algorithm of Gunopulos et al. and thealgorithm of Kavvadias and Stavropoulos.
In the following sections, we describe our algorithm
and the computational result. Section 2 describes
the algorithm of Gunopulos et al. and Section 3 describes our algorithm and Uno’s algorithm. Section 4
explains our improvement using sparseness. Computational experiments for FIMI’03 instances are shownin Section 5, and we conclude the paper in Section 6.

We describe an implementation of an algorithm forenumerating all maximal frequent sets using irredundant dualization, which is an improved version of thatof Gunopulos et al. The algorithm of Gunopulos etal. solves many dualization problems, and takes longcomputation time. We interleaves dualization withthe main algorithm, and reduce the computation time
for dualization by as long as one dualization. This
also reduces the space complexity. Moreover, we accelerate the computation by using sparseness.

1. Introduction
Let E be an item set and T be a set of transactions
deﬁned on E. For an item set S ⊆ E, we denote theset of transactions including S by X(S). We deﬁne
the frequency of S by |X(S)|. For a given constant α,
if an item set S satisﬁes |X(S)| ≥ α, then S is said tobe frequent. A frequent item set included in no otherfrequent item set is said to be maximal. An item set
not frequent is called infrequent. An infrequent item
set including no other infrequent item set is said tobe minimal.
This paper describes an implementation of an algorithm for enumerating all maximal frequent sets using dualization in detail presented at [SatohUno03].
The algorithm is an improved version of that ofGunopulos et al. [Gunopulos97a, Gunopulos97b].
The algorithm computes maximal frequent sets basedon computing minimal transversals of a hypergraph, computing minimal hitting set, or, inother words, computing a dualization of a monotone function [Fredman96]. The algorithm ﬁnds all
minimal item sets not included in any current obtained maximal frequent set by dualization. If a frequent item set is in those minimal item sets, then thealgorithm ﬁnds a new maximal frequent set including the frequent item set. In this way, the algorithm
1Dualize and Advance[Gunopulos97a]
1 Bd+ := {go up(∅)}
2 Compute M HS(Bd+ ).
3 If no set in M HS(Bd+ ) is frequent, output M HS(Bd+ ).
4 If there exists a frequent set S in M HS(Bd+ ), Bd+ := Bd+ ∪ {go up(S)} and go to 2.
Figure 1: Dualize and Advance Algorithm

2. Enumerating maximal frequent sets

Basically, the algorithm of Gunopulos et al. solves
dualization problems with sizes from 1 through|Bd+ |. Although we can terminate dualization when
we ﬁnd a new maximal frequent set, we may checkeach minimal infrequent item set again and again.
This is one of the reasons that the algorithm ofGunopulos et al. is not fast in practice. In the next
section, we propose a new algorithm obtained by interleaving gp up into a dualization algorithm. The
algorithm basically solves one dualization problem ofsize |Bd+ |.

by dualization
In this section, we describe the algorithm of Gunopulos et al. Explanations are also in [Gunopulos97a,
Gunopulos97b, SatohUno03], however, those are
written with general terms. In this section, we explain in terms of frequent set mining.
Let Bd− be the set of minimal infrequent sets. For
a subset family H of E, a hitting set HS of H is a set
such that for every S ∈ H, S ∩ HS = ∅. If a hitting
set includes no other hitting set, then it is said to beminimal. We denote the set of all minimal hitting
sets of H by M HS(H). We denote the complementof a subset S w.r.t. E by S. For a subset family H,
we denote {S|S ∈ H} by H.
There is a strong connection between the maximal
frequent sets and the minimal infrequent sets by theminimal hitting set operation.

3. Description of our algorithm
The key lemma of our algorithm is the following.
+
Lemma 1 [SatohUno03] Let Bd+
1 and Bd2 be sub+++sets of Bd . If Bd1 ⊆ Bd2 ,−+−M HS(Bd+1 ) ∩ Bd ⊆ M HS(Bd2 ) ∩ Bd

Proposition 1 [Mannila96] Bd− = M HS(Bd+ )Suppose that we have already found minimal hitting sets corresponding to Bd+ of a subset Bd+ of
the maximal frequent sets. The above lemma meansthat if we add a maximal frequent set to Bd+ , any
minimal hitting set we found which corresponds to aminimal infrequent set is still a minimal infrequent
set. Therefore, if we can use an algorithm to visit
each minimal hitting set based on an incremental addition of maximal frequent sets one by one, we nolonger have to check the same minimal hitting set
again even if maximal frequent sets are newly found.
The dualization algorithms proposed by Kavvadias
and Stavropoulos [Kavvadias99] and Uno[Uno02] aresuch kinds of algorithms. Using these algorithms, wereduce the number of checks.
Let us show Uno’s algorithm [Uno02]. This is
an improved version of Kavvadias and Stavropoulos’s algorithm [Kavvadias99]. Here we introduce
some notation. A set S ∈ H is called critical fore ∈ hs, if S ∩ hs = {e}. We denote a family ofcritical sets for e w.r.t. hs and H as crit(e, hs).
Note that mhs is a minimal hitting set of H if andonly if for every e ∈ mhs, crit(e, mhs) is not empty.

Using the following proposition, Gunopulos et al.
proposed an algorithm called Dualize and Advanceshown in Fig. 1 to compute the maximal frequent
sets [Gunopulos97a].
Proposition 2 [Gunopulos97a] Let Bd+ ⊆ Bd+ .
Then, for every S ∈ M HS(Bd+ ), either S ∈ Bd−
or S is frequent (but not both).
In the above algorithm, go up(S) for a subset S of
E is a maximal frequent set which is computed asfollows.
1. Select one element e from S and check the frequency of S ∪ {e}.
2. If it is frequent, S := S ∪ {e} and go to 1.
3. Otherwise, if there is no element e in S such thatS ∪ {e} is frequent, then return S.
Proposition 3 [Gunopulos97a] The number of frequency checks in the “Dualize and Advance” algorithm to compute Bd+ is at most |Bd+ | · |Bd− | +|Bd+ | · |E|2 .
2global S0 , ..., Sm;
compute mhs(i, mhs) /* mhs is a minimal hitting set of S0 , ..., Si */begin
1 if i == m then output mhs and return;2 else if Si+1 ∩ mhs = ∅ then compute mhs(i + 1, mhs);
else
begin
3 for every e ∈ Si+1 do
4
if for every e ∈ mhs, there exists Sj ∈ crit(e , mhs), j ≤ is.t. Sj does not contain e then5
comupute mhs(i + 1, mhs ∪ {e});endreturn;end
Figure 2: Algorithm to Enumerate Minimal Hitting Sets
Suppose that H = {S1 , ..., Sm}, and let M HSi be
M HS({S0 , ..., Si})(1 ≤ i ≤ n). We simply denote
M HS(H) by M HS. A hitting set hs for {S1 , ..., Si}is minimal if and only if crit(e, hs) ∩ {S1 , ..., Si} = ∅for any e ∈ hs.

following conditions.
(1) mhs = mhs(2) mhs = mhs ∪ {e}In particular, no mhs has a child satisfying (1) anda child satisfying (2).

Lemma 2 [Uno02] For any mhs ∈ M HSi (1 ≤ i ≤n), there exists just one minimal hitting set mhs ∈M HSi−1 satisfying either of the following conditions(but not both),If mhs ∩ Si+1 = ∅ then mhs ∈ M HSi+1 , and (1)holds. If mhs ∩ Si+1 = ∅, then mhs ∈ M HSi+1 , and(2) can hold for some e ∈ Si+1 . If mhs = mhs ∪ {e}is a child of mhs, then for any e ∈ mhs, there is
Sj ∈ crit(e , mhs), j ≤ i such that e ∈ Sj . From theseobservations, we obtain the algorithm described inFig. 2.
An iteration of the algorithm in Fig. 2 takes:• mhs = mhs.
• mhs = mhs \ {e} where crit(e, mhs) ∩{S0 , ..., Si} = {Si }.

• O(|mhs|) time for line 1.

We call mhs the parent of mhs, and mhs a child of
mhs . Since the parent-child relationship is not cyclic,
its graphic representation forms a forest in which eachof its connected components is a tree rooted at a minimal hitting set of M HS1 . We consider the trees as
traversal routes deﬁned for all minimal hitting setsof all M HSi . These transversal routes can be traced
in a depth-ﬁrst manner by generating children of thecurrent visiting minimal hitting set, hence we canenumerate
sets of M HS in linear
 all minimal hitting time of i |M HSi |. Although i |M HSi | can be exponential to |M HS|, such cases are expectedto be
exceptional in practice. Experimentally, i |M HSi |is linear in |M HS|.
To ﬁnd children of a minimal hitting set, we use thefollowing proposition that immediately leads fromthe above lemma.

• O(|Si+1 ∪ mhs|) time for line 2.
• O((|E| − |mhs|) ×e ∈mhs |crit(e , mhs) ∩{S0 , ..., Si}|) time for lines 3 to 5, except for thecomputation of crit.
To compute crit quickly, we store crit(e, mhs) inmemory, and update them when we generate a recursive call. Note that this takes O(m) memory. Sincecrit(e , mhs ∪ {e}) is obtained from crit(e , mhs) byremoving sets including e (i.e., crit(e , mhs ∪ {e}) ={S|S ∈ crit(e , mhs), e ∈ Si+1 }), crit(e , mhs ∪ {e})for all e can be computed in O(m) time. Hencethe computation time of an iteration is bounded by
O(|E| × m).
Based on this dualization algorithm, we developed a maximal frequent sets enumeration algorithm.
First, the algorithm sets the input H of the dualization problem to the empty set. Then, the algorithm solves the dualization in the same way as the

Proposition 4 [Uno02]
Any child mhs of mhs ∈ M HSi satisfies one of the3

Irredundant Border Enumerator+
global integer bdpnum; sets bd+
0 , bd1 ....;
main()
begin
bdpnum := 0;
construct bdp(0, ∅);output all the bd+
j (0 ≤ j ≤ bdpnum);end
construct bdp(i, mhs)
begin
if i == bdpnum /* minimal hitting set for ∪bdpnum
bd+
j:=0
j is found */then goto 1 else goto 2
1.

if mhs is not frequent, return; /* new Bd− element is found */+bd+
bdpnum := go up2(mhs); /* new Bd element is found */bdpnum := bdpnum + 1; /* proceed to 2 */2.

if bd+i ∩ mhs = ∅ then construct bdp(i + 1, mhs);
else
begin
for every e ∈ bd+
i do
+
+
+
if bd+i ∪ {e} is a minimal hitting set of {bd0 , bd1 ..., bdi−1}) then construct bdp(i + 1, mhs ∪ {e});return;end
Figure 3: Algorithm to Check Each Minimal Hitting Set Only Onceabove algorithm. When a minimal hitting set mhs
is found, the algorithm checks its frequency. If mhs
is frequent, the algorithm ﬁnds a maximal frequent
set S including it, and adds S to H as a new elementof H. Now mhs is not a minimal hitting set sinceS ∩ mhs = ∅. The algorithm continues generating arecursive call to ﬁnd a minimal hitting set of the updated H. In the case that mhs is not frequent, from
Lemma 1, mhs continues to be a minimal hitting set
even when H is updated. Hence, we backtrack andﬁnd other minimal hitting sets.
When the algorithm terminates, H is the set of
maximal frequent sets, and the set of all minimal
hitting sets the algorithm found is the set of minimal
infrequent sets. The recursive tree the algorithm generated is a subtree of the recursive tree obtained by
Uno’s dualization algorithm inputting Bd+ , which isthe set of the complement of maximal frequent sets.
This algorithm is described in Fig. 3. We call thealgorithm Irredundant Border Enumerator (IBE algorithm, for short).

Theorem 1 The computation time of IBE is¯ + ) is theO(Dual(Bd+ ) + |Bd+ |g), where Dual(Bdcomputation time of Uno’s algorithm for dualizing
Bd+ , and g is the computation time for go up.
Note also that, the space complexity of the IBE
algorithm is O(ΣS∈Bd+ |S|) since all we need to memorize is Bd+ and once a set in Bd− is checked, it is
no longer need to be recorded. On the other hand,
Gunopulos et al. [Gunopulos97a] suggests a usageof Fredman and Khachiyan’s algorithm [Fredman96]
which needs a space of O(ΣS∈(Bd+ ∪Bd− ) |S|) since thealgorithm needs both Bd+ and Bd− at the last stage.

4. Using sparsenessIn this section, we speed up the dualization phaseof our algorithm by using a sparseness of H. In realdata, the sizes of maximal frequent sets are usuallysmall. They are often bounded by a constant. We use
this sparse structure for accelerating the algorithm.
4

global S0 , ..., Sm;
compute mhs(i, mhs) /* mhs is a minimal hitting set of S0 , ..., Si */begin
1 if uncov(mhs) == ∅ then output mhs and return;2 i := minimum index of uncov(mhs) ;3 for every e ∈ mhs do
4increase the counter of items in ∪S∈crit(mhs,e) S by one
end
5 for every e ∈ mhs s.t. counter is increased by |mhs| do /* items included in all ∪S∈crit(mhs,e) S */6
compute mhs(i + 1, mhs ∪ {e});return;end
Figure 4: Improved Dualization Algorithm Using SparsenessFirst, we consider a way to reduce the computation time of iterations. Let us see the algorithm
described in Fig. 2. The bottle neck part ofthe computation of an iteration of the algorithm islines 3 to 5, which check the existence of a critical set Sj ∈ crit(mhs, e ), j < i such that e ∈ Sj .
To check 
this condition for an item e ∈ mhs, wespend O( e ∈mhs |crit(mhs, e )|) time, hence thischeck
for all e ∈ mhs takes O((|E| − |mhs|) ×e ∈mhs |crit(mhs, e )|) time.
Instead of this, we compute S∈crit(mhs,e) S foreach e ∈ mhs. If and only if e ∈ S∈crit(mhs,e) S
the condition of “if” atfor all e ∈ mhs, e satisﬁesline 4. To compute S∈crit(mhs,e) S for all e ∈ mhs,

we take O( e∈mhs S∈crit(mhs,e) |S|) time. In thecase of IBE algorithm, S is a maximal frequent set,hence the average size of |S| is expected to be small.
The sizes of minimal infrequent sets are not greaterthan the maximum size of maximal frequent sets, andthey are usually smaller than the average size of the
maximal frequent sets. Hence, |mhs| is also expected
to be small.

sive call, we allocate memory for each variable usedin the recursive call. Hence, the memory requiredby the algorithm can be up to O(|E| × m). However,experimentally the required memory is always linear
in the input size. Note that we can reduce the worst
case memory complexity by some sophisticated algorithms.

5. Experiments
In this section, we show some results of the computational experiments of our algorithms. We implement our algorithm using C programming language, and examined instances of FIMI2003. For
instances of KDD-cup 2000[KDDcup00], we compared the results to the computational experiments of
CHARM[Zaki02], closed[Pei00], FP-growth[Han00],
and Apriori[Agrawal96] shown in [Zheng01]. The experiments in [Zheng01] were done on a PC with aDuron 550MHz CPU and 1GB RAM memory. Our
experiments were done on a PC with a Pentium III
500MHz CPU and 256MB RAM memory, which islittle slower than a Duron 550MHz CPU. The results are shown in Figs. 4 – 14. Note that our algorithm uses at most 170MB for any following instance.
We also show the number of frequent sets, frequent
closed/maximal item sets, and minimal frequent sets.
In our experiments, IBE algorithm takes approximately O(|Bd− | × ave(Bd+ )) time, while the computation time of other algorithms deeply depends on
the number of frequent sets, the number of frequent
closed item sets, and the minimum support. We recall that ave(Bd+ ) is the average size of maximal
frequent sets. In some instances, our IBE algorithm
performs rather well compared to other algorithms.
In these cases, the number of maximal frequent item

Second, we reduce the number of iterations. For
mhs ⊆ E, we deﬁne uncov(mhs) by the set of S ∈ H
satisfying S ∩ mhs = ∅. If mhs ∩ Si = ∅, the iteration
inputting mhs and i does nothing but generates arecursive call with increasing i by one. This type of
iterations should be skipped. Only iterations executing lines 3 to 5 are crucial. Hence, in each iteration,
we set i to the minimum index among uncov(mhs).
As a result of this, we need not execute line 2, andthe numberofiterations
isreducedfromi |M HSi |
to | i M HSi |. We describe the improved algorithm
in Fig. 4.
In our implementation, when we generate a recur5

sets is smaller than number of frequent item sets.
IBE algorithm seems to give a good performance fordiﬃcult problems such that the number of maximal
frequent sets is very small rather than those of frequent item sets and frequent closed item sets.

[KDDcup00] Kohavi, R., Brodley, C. E., Frasca, B.,
Mason, L., and Zheng, Z., “KDD-Cup 2000 Organizers’ Report: Peeling the Onion,” SIGKDD
Explorations, 2(2), pp. 86-98, 2000.
[Mannila96] Mannila, H. and Toivonen, T., “Onan Algorithm for Finding All Interesting Sentences”, Cybernetics and Systems, Vol II, The
Thirteen European Meeting on Cybernetics andSystems Research, pp. 973 – 978 (1996).

6. Conclusion
In this paper, we describe the detailed implementation method of our algorithm proposedin [SatohUno03] and we give some experimental results on test data.

[Pei00] Pei, J., Han, J., Mao, R., “CLOSET: An Efﬁcient Algorithm for Mining Frequent Closed
Itemsets,” ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge
Discovery 2000, pp. 21-30, 2000.

Acknowledgments
We are grateful to Heikki Mannila for participating
useful discussions about this research.

[SatohUno03] Satoh, K., Uno, T., “Enumerating
Maximal Frequent Sets using Irredundant Dualization”, Lecture Notes in Artificial Intelligence(Proc. of Discovery Science 2003), SpringerVarlag, pp. 192-201, 2003.

References[Agrawal96] Agrawal, R., Mannila, H., Srikant, R.,
Toivonen, H., and Verkamo, A. I., “Fast Discovery of Association Rules”, U. M. Fayyad,
G. Piatetsky-Shapiro, P. Smyth, and R. Uthurusamy, (eds), Advances in Knowledge Discovery and Data Mining, chapter 12, pp. 307–328(1996).

[Uno02] Uno, T., “A Practical Fast Algorithm
for Enumerating Minimal Set Coverings”, SIGAL83, Information Processing Society ofJapan, pp. 9 – 16 (in Japanese) (2002).
[Zaki02] Zaki, M. J., Hsiao, C., “CHARM: An Eﬃcient Algorithm for Closed Itemset Mining,” 2nd
SIAM International Conference on Data Mining(SDM’02), pp. 457-473, 2002.

[Fredman96] Fredman, M. L. and Khachiyan, L.,“On the Complexity of Dualization of Monotone Disjunctive Normal Forms”, Journal of Algorithms 21(3), pp. 618 – 628 (1996)[Zheng01] Zheng, Z., Kohavi, R., and Mason, L.,“Real World Performance of Association Rule
Algorithms,” KDD 2001, pp. 401-406, 2001.

[Gunopulos97a] Gunopulos, D., Khardon, R., Mannila, H. and Toivonen, H., “Data mining, Hypergraph Transversals, and Machine Learning”,
Proc. of PODS’97, pp. 209 – 216 (1997).
[Gunopulos97b] Gunopulos, D., Mannila, H., andSaluja, S., “Discovering All Most Speciﬁc Sentences using Randomized Algorithms”, Proc. of
ICDT’97, pp. 215 – 229 (1997).
[Han00] Han, J., Pei, J., Yin, Y., “Mining Frequent
Patterns without Candidate Generation,” SIGMOD Conference 2000, pp. 1-12, 2000
[Kavvadias99] Kavvadias, D. J., and Stavropoulos,
E. C., “Evaluation of an Algorithm for theTransversal Hypergraph Problem”, Algorithm
Engineering, pp 72 – 84 (1999).
6

time(sec)10000

time(sec)

BMS-WebView1

T10I4D100K

10000

1000

1000

Apriori
FP-growthcloset
CHARM
IBE

100

10

Apriori
FP-growthcloset
CHARM
IBE

100

10

1
0.01

0.02

10000)

0.04

time(sec

BMS-WebView2

0.06

support

0.08

6

12

24

36

48

60
time(sec)
1000000.1

1

support

T40I10D100K

10000

Apriori
FP-growthcloset
CHARM
IBE

1000

100

IBE
1000

10

100

1
7

15

31

46

62

77

time(sec)

support1600

time(sec)

BMS-POS

100000

1300

1000

700

support

pumsb

10000

10000
1000

ApioriFP-growth
CHARM
IBE

1000

100

100

IBE
10
51

103

206

310

413

517

10

support45000 44000 43000 42000 41000 40000

7

supporttime(sec)time(sec

pumsb_star

10000

connect

10000)

1000

IBE
1000
100

IBE
10

time(sectime(sec)

kosaraksupportchess

10000)

10000

45
00
0

10000

48
00
0

15000

51
00
0

20000

54
00
0

25000

57
00
0

support
30000

60
00
0

63
00
0

100
1

1000

IBE

100

1000

10
2200

IBE

100

support3000

2500

time(sec

2000

1500

1000

mushroom

1000 )

IBE
100

10
30

20

10

5

2

support

8

1900

1600

1300

1000

supportBMS-Web-View1: #item 497, #transactions, 59602, ave. size of transaction 2.51
support
60
48
36
24
12
6
Apriori
1.1
3.6
113
FP-growth
1.2
1.8
51
Closet
33
74
Charm
2.2
2.7
7.9
133
422
IBE
5.8
9.6
45
42
333
2982
#freq. sets 3992 10287 461522#closed sets 3974 9391 64762 155651 422692 1240701#max. freq. sets 2067 4028 15179 12956 84833 129754#min. infreq. sets 66629 81393 150278 212073 579508 4320003
maximum use of memory: 45MBBMS-Web-View2: #items 3340, #transactions 77512, ave. size of transaction 4.62
support
77
62
46
31
15
7
Apriori
13.1
15
29.6
58.2
444
Fp-growth
7.03
10
17.2
29.6
131
763
Closet 1500 2250
3890
6840 25800
Charm
5.82
6.66
7.63
13.8
27.2
76
IBE
25
32
46
98
355
1426
#closed sets 22976 37099 60352 116540 343818 754924#freq. sets 24143 42762 84334 180386 1599210 9897303#max. freq. sets 3901 5230
7841 16298 43837 118022#min. infreq. sets 657461 958953 1440057 2222510 3674692 5506524
maximal use of memory: 100MBBMS-POS: #items 1657, #transactions 517255, ave. size of transaction 6.5
support
517
413
310
206
103
51
Apriori
251
341
541
1000
2371
10000
Fp-growth
196
293
398
671
1778
6494
Closet
Charm
100
117
158
215
541
3162
IBE 1714 2564 4409
9951 44328#closed sets 121879 200030 378217 840544 1742055 21885050#freq. sets 121956 200595 382663 984531 5301939 33399782#max. freq. sets 30564 48015 86175 201306 891763 4280416#min. infreq. sets 236274 337309 530946 1047496 3518003
maximum use of memory: 110MB
T10I4D100K: #items 1000, #transactions 100000, ave. size of transaction 10
support
100
80
60
40
20
10
Apriori
33
39
45
62
117
256
Fp-growth
7.3
7.7
8.1
9.0
12
20
Closet
13
16
18
23
41
130
Charm
11
13
16
24
45
85
IBE
96
147
263
567
1705
#freq. sets 15010 28059 46646 84669 187679 335183#closed sets 13774 22944 38437 67537 131342 229029#max. freq. sets 7853 11311 16848 25937 50232 114114#min. infreq. sets 392889 490203 736589 1462121 4776165
maximum use of memory: 60MB
T40I10D100K: #items 1000, #transactions 100000, ave. size of transaction 39.6
support 1600 1300 1000
700
IBE
378
552 1122
2238#freq. sets 4591 10110 65236 550126#closed sets 4591 10110 65236 548349#max. freq. sets 4003 6944 21692 41473#min. infreq. sets 245719 326716 521417 1079237

9

maximum memory use: 74MB
pumsb: #items 7117, #transactions 49046, ave. size of transaction 74
support 45000 44000 43000 42000
IBE 301 582 1069 1840
#freq. sets 1163 2993 7044 15757#closed sets 685 1655 3582 7013
#max. freq. sets 144 288 541 932#min. infreq. sets 7482 7737 8402 9468
maximum use of memory: 70MB
pumsb star: #items 7117, #transactions 49046, ave. size of transaction 50
support 30000 25000 20000 15000 10000 5000
IBE
8
19
59
161
556 2947#freq. sets 165 627 21334 356945 >2G#closed sets
66 221 2314 14274 111849#max. freq. sets4
17
81
315 1666 15683#min. infreq. sets 7143 7355 8020 9635 19087 98938
maximum use of memory: 44MB
kosarak: #items 41217, #transactions 990002, ave. size of transaction 8
support 3000 2500 2000 1500 1000
IBE 226294
528
759 2101#freq. sets 4894 8561 34483 219725 711424#closed sets 4865 8503 31604 157393 496675#max. freq. sets 792 1146 2858 4204 16231#min. infreq. sets 87974 120591 200195 406287 875391
maximum use of memory: 170MB
mushroom: #items 120, #transactions 8124, ave. size of transaction 23
support
30
20
10
5
2
IBE
132
231
365
475
433
#freq. sets 505205917 781458545 1662769667 >2G >2G#closed sets
91122
109304
145482 181243 230585#max. freq. sets
15232
21396
30809 34131 27299#min. infreq. sets
66085
79481
81746 69945 31880
maximum use of memory 47MB
connect: #items 130, #transactions 67577, ave. size of transaction 43
support 63000 60000 57000 54000 51000 48000 45000
IBE 229 391
640
893
1154 1381 1643
#freq. sets 6327 41143 171239 541911 1436863#closed sets 1566 4372 9041 15210 23329#max. freq. sets 152 269
464
671
913 1166 1466
#min. infreq. sets 297 486703
980
1291 1622 1969
maximum use of memory: 60MB
chess: #items 76, #transactions 3196, ave. size of transaction 37
support 2200 1900
1600
1300
1000
IBE
19
61
176
555
2191
#freq. sets 59181 278734 1261227 5764922 29442848#closed sets 28358 106125 366529 1247700 4445373#max. freq. sets 1047 3673 11209 35417 114382#min. infreq. sets 1725 5202 14969 46727 152317
maximum use of memory: 50MB

10