An Efficient Algorithm for Enumerating Closed
Patterns in Transaction Databases
Takeaki Uno1 , Tatsuya Asai2 3 , Yuzo Uchida2 , and Hiroki Arimura2
National Institute of Informatics, 2-1-2, Hitotsubashi, Chiyoda-ku, Tokyo, Japan,
e-mail: uno@nii.jp
2
Department of Informatics, Kyushu University, 6-10-1, Hakozaki, Fukuoka, Japan,
e-mail:{t-asai,y-uchida,arim}@i.kyushu-u.ac.jp
1

Abstract: The class of closed patterns is a well known condensed representations offrequent patterns, and have recently attracted considerable interest. In this paper, we
propose an efficient algorithm LCM (Linear time Closed pattern Miner) for mining
frequent closed patterns from large transaction databases. The main theoretical contribution is our proposed prefix-preserving closure extension of closed patterns, whichenables us to search all frequent closed patterns in a depth-first manner, in linear time
for the number of frequent closed patterns. Our algorithm do not need any storage space
for the previously obtained patterns, while the existing algorithms needs it. Performancecomparisons of LCM with straightforward algorithms demonstrate the advantages ofour prefix-preserving closure extension.

1 Introduction
Frequent pattern mining is one of the fundamental problems in data mining and has
many applications such as association rule mining [1, 5, 7] and condensed representation of inductive queries [12]. To handle frequent patterns efficiently, equivalenceclasses induced by the occurrences had been considered. Closed patterns are maximal
patterns of an equivalence class.
This paper addresses the problems of enumerating all frequent closed patterns. For
solving this problem, there have been proposed many algorithms [14, 13, 15, 20, 21].
These algorithms are basically based on the enumeration of frequent patterns, that is,enumerate frequent patterns, and output only those being closed patterns. The enumeration of frequent patterns has been studied well, and can be done in efficiently short time
[1, 5]. Many computational experiments supports that the algorithms in practical takevery short time per pattern on average.
However, as we will show in the later section, the number of frequent patterns canbe exponentially larger than the number of closed patterns, hence the computation time
can be exponential in the size of datasets for each closed pattern on average. Hence, theexisting algorithms use heuristic pruning to cut off non-closed frequent patterns. However, the pruning are not complete, hence they still have possibilities to take exponential
time for each closed pattern.
Moreover, these algorithms have to store previously obtained frequent patterns inmemory for avoiding duplications. Some of them further use the stored patterns for3

Presently working for Fujitsu Laboratory Ltd., e-mail: asai.tatsuya@jp.fujitsu.com

checking the “closedness” of patterns. This consumes much memory, sometimes exponential in both the size of both the database and the number of closed patterns. In
summary, the existing algorithms possibly take exponential time and memory for both
the database size and the number of frequent closed patterns. This is not only a theoretical observation but is supported by results of computational experiments in FIMI’03[7].
In the case that the number of frequent patterns is much larger than the number of frequent closed patterns, such as BMS-WebView1 with small supports, the computation
time of the existing algorithms are very large for the number of frequent closed patterns.
In this paper, we propose a new algorithm LCM (Linear time Closed pattern Miner)
for enumerating frequent closed patterns. Our algorithm uses a new technique called
prefix preserving extension (ppc-extension), which is an extension of a closed pattern
to another closed pattern. Since this extension generates a new frequent closed patternfrom previously obtained closed pattern, it enables us to completely prune the unnecessary non-closed frequent patterns. Our algorithm always finds a new frequent closed
pattern in linear time of the size of database, but never take exponential time. In theother words, our algorithm always terminates in linear time in the number of closed
patterns. Since any closed pattern is generated by the extension from exactly one ofthe other closed patterns, we can enumerate frequent closed patterns in a depth-firstsearch manner, hence we need no memory for previously obtained patterns. Thereby,
the memory usage of our algorithm depends only on the size of input database. This
is not a theoretical result but our computational experiments support the practical efficiency of our algorithm. The techniques used in our algorithm are orthogonal to the existing techniques, such as FP-trees, look-ahead, and heuristic preprocessings. Moreover,
we can add the existing techniques for saving the memory space so that our algorithm
can handle huge databases much larger than the memory size.
For practical computation, we propose occurrence deliver, anytime database reduction, and fast ppc-test, which accelerate the speed of the enumeration significantly. We
examined the performance of our algorithm for real world and synthesis datasets takenfrom FIMI’03 repository, including the datasets used in KDD-cup [11], and comparewith straightforward implementations. The results showed that the performance of the
combination of these techniques and the prefix preserving extension is good for manykinds of datasets.
In summary, our algorithm has the following advantages.
· Linear time enumeration of closed patterns· No storage space for previously obtained closed patterns· Generating any closed pattern from another unique closed pattern· Depth-first generation of closed patterns· Small practical computational cost of generation of a new pattern
The organization of the paper is as follows. Section 2 prepares notions and definitions. In the Section 3, we give an example to show the number of frequent patterns canbe up to exponential to the number of closed patterns. Section 4 explains the existing
schemes for closed pattern mining, then present the prefix-preserving closure extension
and our algorithm. Section 5 describes several improvements for practical use. Section
6 presents experimental results of our algorithm and improvements on synthesis andrealworld datasets. We conclude the paper in Section 7.

2 Preliminaries
We give basic definitions and results on closed pattern mining according to [1, 13, 6].
Let I = {1, . . . , n} be the set of items. A transaction database on I is a set T ={t1 , . . . , tm } such that each ti is included in I.PEach ti is called a transaction. We
denote the total size of T by ||T ||, i.e., ||T || = t∈T |t|. A subset P of I is called apattern (or itemset). For pattern P , a transaction including P is called an occurrence of
P . The denotation of P , denoted by T (P ) is the set of the occurrences of P . |T (P )|is called the frequency of P, and denoted by f rq(P ). For given constant θ ∈ N, calleda minimum support, pattern P is frequent if f rq(P ) ≥ θ. For any patterns P and Q,
T (P ∪ Q) = T (P ) ∩ T (Q) holds, and if P ⊆ Q then T (Q) ⊇ T (P ).
Let T be a database and P be a pattern on I. For a pair of patterns P and Q, we
say P and Q are equivalent to each other if T (P ) = T (Q). The relationship induces
equivalence classes on patterns. A maximal pattern and a minimal pattern of an equivalence class, w.r.t. set inclusion, are called a closed pattern and key pattern, respectively.
We denote by F and C the sets of all frequent patterns and the set of frequent closed
patterns in T , respectively.
T
Given set S ⊆ T of transactions, let I(S) = T ∈S T be the set of items common
to all transactions
in S. Then, we define the closure of pattern P in T , denoted byT
Clo(P ), by T ∈T (P ) T . For every pair of patterns P and Q, the following properties
hold (Pasquier et al.[13]).
(1) If P ⊆ Q, then Clo(P ) ⊆ Clo(Q).
(2) If T (P ) = T (Q), then Clo(P ) = Clo(Q).
(3) Clo(Clo(P )) = Clo(P ).
(4) Clo(P ) is the unique smallest closed pattern including P .
(5) A pattern P is a closed pattern if and only if Clo(P ) = P .
Note that a key pattern is not the unique minimal element of an equivalence class,while the closed pattern is unique. Here we denote the set of frequent closed patterns
by C, the set of frequent patterns by F, the set of items by I, and the size of databaseby ||T ||.
For pattern P and item i ∈ P , let P (i) = P ∩ {1, . . . , i} be the subset of P
consisting only of elements no greater than i, called the i-prefix of P . Pattern Q is a
closure extension of pattern P if Q = Clo(P ∪ {i}) for some i 6∈ P . If Q is a closure
extension of P , then Q ⊃ P, and f rq(Q) ≤ f rq(P ).

3 Difference between Numbers of Frequent Patterns and Frequent
Closed Patterns
This section shows that the the number of frequent patterns can be quite larger than thenumber of frequent closed patterns. To see it, we prove the following theorem. Here an
irredundant transaction database is a transaction database such that· no two transactions are the same,· no item itself is an infrequent pattern, and· no item is included in all transactions.

Intuitively, if these conditions are satisfied, then we can neither contract nor reduce thedatabase.
Theorem 1. There are infinite series of irredundant transaction databases T such thatthe number |F| of frequent patterns is exponential in m and n while the number |C| offrequent closed patterns is O(m2 ), where m is the number of transactions in T and n
is the size of the itemset on which the transactions are defined. In particular, the size of
T is Θ(nm).
Proof. Let n be any number larger than 4 and m be any even number satisfying thatn − (dlg me + 2) is larger than both n and m for a constant . Let
X = {1, ..., n − 2(dlg me + 2)}
Y1 = {n − 2(dlg me + 2) + 1, ..., n − (dlg me + 2)}
Y2 = {n − (dlg me + 2) + 1, ..., n}
J1 := a subset of 2Y1 \ {∅, Y1 } of size m/2 − 1 without duplications
J2 := a subset of 2Y2 \ {∅, Y2 } of size m/2 − 1 without duplications.
Since |Y1 | = |Y2 | = dlg me + 2, such J1 and J2 always exist. Then, we construct
a database as follows.
T

S {X ∪ Y1 ∪ S|S ∈ J2 }{X ∪ Y2 ∪ S|S ∈ J1 }:= S
{Y
1 ∪ Y2 }S{X}

The database has m transactions defined on an itemset of size n. The size of databaseis Θ(nm).
We set the minimum support to m/2. We can see that no transactions are the same,
no item is included in all transactions, and any item is included in at least m/2 transactions. Let F and C be the set of frequent patterns and the set of frequent closed patterns,
respectively.
Since any transaction in T except for Y1 ∪ Y2 includes X, any subset of X is afrequent pattern. Since |X| = n − (dlg me + 2) is larger than both n and m , we seethat |F| is exponential in both n and m.
On the other hand, any frequent closed pattern includes X. Hence, any frequent
closed pattern is equal to X ∪S for some S ⊆ Y1 ∪Y2 . Since |Y1 ∪Y2 | = 2(dlg me+2),
we have|C| ≤ 22(dlg me+2)= 22 lg m+6= 64m2 .
Therefore, |C| =O(m2 ).

tuFrom the theorem, we can see that frequent pattern mining based algorithms cantake exponentially longer time for the number of closed patterns. Note that such patterns
may appear in real world data in part, because some transactions may share a common
large pattern.

4 Algorithm for Enumerating Closed Patterns
We will start with the existing schemes for closed pattern enumeration.
4.1 Previous Approaches for Closed Pattern Mining
A simple method of enumerating frequent closed patterns is to enumerate all frequent
patterns, classify them into equivalence classes, and find the maximal pattern for each
equivalent class. This method needs O(|F|2 ) time and O(|F|) memory, since pairwise
comparisons of their denotations are needed to classify frequent patterns. Although thenumber of comparisons can be decreased by using some alphabetical sort of denotations
such as radix sort, it still needs O(|F|) computation. As we saw, |F| is possibly quite
larger than |C|, hence this method consumes a great deal of time and memory.
Some state-of-the-art algorithms for closed pattern mining, such as CHARM [21]and CLOSET [15], use heuristic pruning methods to avoid generating unnecessary nonclosed patterns. Although these pruning methods efficiently cut off non-closed pattens,
the number of generated patterns is not bounded by a polynomial of |C|.
Pasquier et al.[13] proposed the use of closure operation to enumerate closed patterns. Their idea is to generate frequent patterns, and check whether the patterns areclosed patterns or not by closure operation. Although this reduces the storage space fornon-closed patterns, the algorithm still requires |C| space. They actually generate frequent key patterns instead of frequent patterns, to reduce the computational costs. Thus,
the computation time is linear in the number of frequent key patterns, which is less than|F| but can be up to exponential in |C|.
4.2 Closed Patterns Enumeration in Linear Time with Small Space
Our algorithm runs in linear time in |C| with storage space significantly smaller than thatof Pasquier et al.’s algorithm [13], since it operates no non-closed patterns using depthfirst search The following lemmas provide a way of efficiently generating any closed
pattern from another closed pattern. In this way, we construct our basic algorithm. Then,the basic algorithm is improved to save the memory use by using ppc extension.
Lemma 1. Let P and Q, P ⊆ Q be patterns having the same denotation, i.e., T (P ) =T (Q). Then, for any item i 6∈ P, T (P ∪ {i}) = T (Q ∪ {i}).
Proof. T (P ∪ {i}) = T (P ) ∩ T ({i}) = T (Q) ∩ T ({i}) = T (Q ∪ {i}).

tuLemma 2. Any closed pattern P 6= ⊥ is a closure extension of other closed patterns.
Proof. Let Q be a pattern obtained by repeatedly removing items from P until its denotation changes, and i be the item removed last. Then, Clo(Q ∪ {i}) = P. Such a patternmust exist since P 6= ⊥. Since T (Q) 6= T (Q ∪ {i}), i 6∈ Clo(Q). From Property 1,
Clo(Q ∪ {i}) = Clo(Clo(Q) ∪ {i}). Thus, P is a closure extension of Q ∪ {i}.
tuThrough these lemmas, we can see that all closed patterns can be generated byclosure extensions to closed patterns. It follows the basic version of our algorithm,

Algorithm Closure version
1. D := {⊥}2. D0 := { Clo(P ∪ {i}) | P ∈ D, i ∈ I\P }3. if D0 = ∅ then output D ; halt
4. D := D ∪ D 0 ; go to 2
Fig. 1. Basic algorithm for enumerating frequent closed patterns

which uses levelwise (breadth-first) search similar to Apriori type algorithms [1] using
closed expansion instead of tail expansion. We describe the basic algorithm in Figure 1.
Since the algorithm deals with no non-closed pattern, the computational cost depends
on |C| but not on |F|. However, we still need much storage space to keep D in memory.
A possible improvement is to use depth-first search instead of Apriori-style levelwise search. For enumerating frequent patterns, Bayardo [5] proposed an algorithm
based on tail extension, which is an extension of a pattern P by an item larger than the
maximum item of P . Since any frequent pattern is a tail extension of another uniquefrequent pattern, the algorithm enumerates all frequent patterns without duplications in
a depth-first manner, with no storage space for previously obtained frequent patterns.
This technique is efficient, but cannot directly be applied to closed pattern enumeration,
since a closed pattern is not always a tail-extension of another closed pattern.
We here propose prefix-preserving closure extension satisfying that any closed pattern is an extension of another unique closed pattern unifying ordinary closure-expansion
and tail-expansion. This enables depth-first generation with no storage space.
4.3 Prefix-Preserving Closure Extension
We start with definitions. Let P be a closed pattern. The core index of P , denoted bycore i(P ), is the minimum index i such that T (P (i)) = T (P ). We let core i(⊥) = 0.
Here we give the definition of ppc-extension. Pattern Q is called a prefix-preserving
closure extension (ppc-extension) of P if(i) Q = Clo(P ∪ {i}) for some i ∈ P , that is, Q is obtained by first adding i to P
and then taking its closure,(ii) item i satisfies i 6∈ P and i > core i(P ), and(iii) P (i − 1) = Q(i − 1), that is, the (i − 1)-prefix of P is preserved.
Actually, ppc-extension satisfies the following theorem. We give an example in Fig. 2.
Theorem 2. Let Q 6= ⊥ be a closed pattern. Then, there is just one closed pattern Psuch that Q is a ppc-extension of P .
To prove the theorem, we state several lemmas.
Lemma 3. Let P be a closed pattern and Q = Clo(P ∪ {i}) be a ppc-extension of P .
Then, i is the core index of Q.

transaction database12345623 5
2
5
12 456
2 4
1
4 6
34 6

1 2 3 4 5 6
1 2 4 5 6
2 3 5

1 4 6

2 4 2 5

3 4 6

2

3

4 6
4

6

Fig. 2. Example of all closed patterns and their ppc extensions. Core indices are circled

Proof. Since i > core i(P ), we have T (P ) = T (P (i)). From Lemma 2, Clo(P (i) ∪{i}) = Clo(P ∪ {i}) = Clo(Q), thus core i(Q) ≤ i. Since the extension preserves thei-prefix of P , we have P (i − 1) = Q(i − 1). Thus, Clo(Q(i − 1)) = Clo(P (i − 1)) =P 6= Q. It follows that core i(Q) > i − 1, and we conclude core i(Q) = i.
tu
Let Q be a closed pattern and P(Q) be the set of closed patterns such that Q istheir closure extension. We show that Q is a ppc-extension of a unique closed patternof P(Q).
Lemma 4. Let Q 6= ⊥ be a closed pattern, and P = Clo(Q(core i(Q) − 1)). Then,
Q is a ppc-extension of P.
Proof. Since T (P ) = T (Q(core i(Q)−1)), we have T (P ∪{i}) = T (Q(core i(Q)−1) ∪ {i}) = T (Q(core i(Q))). This implies Q = Clo(P ∪ {i}), thus Q satisfies
condition (i) of ppc-extension. Since P = Clo(Q(core i(Q) − 1)), core i(P ) ≤ i − 1.
Thus, Q satisfies condition (ii) of ppc-extension. Since P ⊂ Q and Q(i − 1) ⊆ P, wehave P (i − 1) = Q(i − 1). Thus, Q satisfies condition (iii) of ppc-extension.
tu
proof of Theorem 2: From Lemma 4, there is at least one closed pattern P in P(Q)such that Q is a ppc-extension of P. Let P = Clo(Q(core i(Q) − 1)). Suppose that
there is a closed pattern P 0 6= P such that Q is a ppc-extension of P 0 . From lemma 3,
Q = Clo(P 0 ∪{i}). Thus, from condition (iii) of ppc-extension, P 0 (i−1) = Q(i−1) =P (i − 1). This together with T (P ) = T (P (i − 1)) implies that T (P ) ⊃ T (P 0 ). Thus,
we can see T (P 0 (i − 1)) 6= T (P 0 ), and core i(P 0 ) ≥ i. This violates condition (ii) of
ppc-extension, and is a contradiction.
tu
From this theorem, we obtain our algorithm LCM, described in Figure 3, which
generate ppc-extensions for each frequent closed pattern.
Since the algorithm takes O(||T (P )||) time to derive the closure of each P ∪ {i},we obtain the following theorem.

Algorithm LCM(T :transaction database, θ:support )1. call E NUM C LOSED PATTERNS(⊥) ;Procedure E NUM C LOSED PATTERNS( P : frequent closed pattern )2. if P is not frequent then Return;
2. output P ;3. for i = core i(P ) + 1 to |I|
4. Q = Clo(P ∪ {i});5. If P (i − 1) = Q(i − 1) then// Q is a ppc-extension of P
6. Call E NUM C LOSED PATTERNS(Q);
7. End forFig. 3. Description of Algorithm LCM

Theorem 3. Given a database T , the algorithm LCM enumerates all frequent closed
patterns in O(||T (P )|| × |I|) time for each pattern P with O(||T ||) memory space.
The time and space complexities of the existing algorithms [21, 15, 13] are O(||T ||×|F|) and O(||T || + |C| × |I|), respectively. As we saw in the example in Section 3, thedifference between |C| and |F|, and the difference between |C| × |I| and ||T || canbe up to exponential. As Compared with our basic algorithm, the ppc extension basedalgorithm exponentially reduces the memory complexity when O(|C|) is exponentiallylarger than ||T ||. In practice, such exponential differences often occur (see results in
Section 6). Thus, the performance of our algorithm possibly exponentially better thanthe existing algorithms in some instances.

5 Reducing Practical Computation Time
The computation time of LCM described in the previous section is linear in |C|, with afactor depending on ||T || × |I| for each closed pattern P ∈ C. However, this still takes
a long time if it is implemented in a straightforward way. In this section, we propose
some techniques for speeding up frequency counting and closure operation. These techniques will increase practical performance of the algorithms and incorporated into theimplementations used in the experiments in Section 6 of the paper, although independent of our main contribution. In Figure 7, we describe the details of LCM with thesepractical techniques.
5.1 Occurrence Deliver
Occurrence deliver reduces the construction time for T (P ∪ {i}), which is used for
frequency counting and closure operation. This technique is particularly efficient forsparse datasets, such that |T (P ∪ {i})| is much smaller than |T (P )| on average. In ausual way, T (P ∪ {i}) is obtained by T (P ) ∩ T (P ∪ {i}) in O(|T (P )| + |T (P ∪ {i})|)time (this is known as down-project []). Thus, generating all ppc-extensions needs |I|
scans and takes O(||T (P )||) time.
Instead of this, we build for all i = core i(P ), . . . , |I| denotations T (P ∪ {i}),simultaneously, by scanning the transactions in T (P ). We initialize X[i] := ∅ for all i.

2

A
B

1

C

2

3

4

5

3

4

5

6

5

6

A
B

B

3

T({5})

A
B

7
8
7
A
B

C
C
C
X[4] X[5] X[6] X[7] X[8]Occurrences of {5,i} for i=4,…,8Fig. 4. Occurrence deliver: build up denotations by inserting each transaction to each its member
12345
123 5 7 9
123 5
12345
89
12
7
123
9
12
6

1 2 3 5 (× 2)
1 2 3 5 9 (× 2)12(× 2)
1 2 3 9 (× 1)

Fig. 5. Example of anytime database reduction

For each t ∈ T (P ) and for each i ∈ t; i > core i(P ), we insert t to X[i]. Then, each
X[i] is equal to T (P ∪ {i}). See Fig. 4 for the explanation. This correctly computes
T (P ∪{i}) for all i in O(||T (P )||). Table 1 shows results of computational experiments
where the number of item-accesses were counted. The numbers are deeply related to theperformance of frequency counting heavily depending on the number of item-accesses.
Table 1: the accumulated number of item-accesses over all iterations:

Dataset and support connect,65% pumsb,80%, BMS-webview2,0.2% T40I10D100K,5%
Straightforward
914074131 624940309
870850439
830074845
Occurrence deliver 617847782 201860874
17217493
73406900
Reduction factor
1.47
3.09
50.5
11.3

5.2 Anytime Database Reduction
In conventional practical computations of frequent pattern mining, the size of the input
database is reduced by removing infrequent items i such that T ({i}) < θ, and thenmerging the same transactions into one. Suppose that we are given the database on theleft hand side of Fig. 5, and minimum support 3.
In the database, items 4, 6, 7, and 8 are included in at most two transactions, hence
patterns including these items can not be frequent. Items 1 and 2 are included in alltransactions, hence any frequent patterns can contain any subset of {1, 2}. It followsthat items 1 and 2 are redundant. Hence, we remove items 1, 2, 4, 6, 7, and 8 from thedatabase. After the removal, we merge the same transactions into one. We then record
the multiplicity of transactions. Consequently, we have a smaller database, right handside of Fig. 5, with fewer items and fewer transactions, which includes the same setof frequent patterns. We call this operation database reduction (or database filtering).
Many practical algorithms utilize this operation at initialization. Database reduction is
known to be efficient in practice, especially for large support [7].
Here we propose anytime database reduction, which is to apply database reduction
in any iteration. For an iteration (invokation) of Enum ClosedPatterns inputting pattern P, the following items and transactions are unnecessary for any of its descendantiterations:(1) transactions not including P ,(2) transactions including no item greater than core i(P ),(3) items included in P
(4) items less than or equal to core i(P ), and(5) items i satisfies that f rq(P ∪ {i}) < θ (no frequent pattern includes i).
In each iteration, we restrict the database to T (P ), apply database reduction toremove such items and transactions, merge the same transactions, and pass it to child
iterations.
Anytime database reduction is efficient especially when support is large. In the experiments, in almost all iterations, the size of the reduced database is bounded by aconstant even if the patterns have many occurrences. Table 2 lists simple computational
experiments comparing conventional database reduction (applying reduction only at
initialization) and anytime database reduction. Each cell shows the accumulated number of transactions in the reduced databases in all iterations.
Table 2: Accumulated number of transactions in database in all iterations

Dataset and support
connect, 50% pumsb, 60%, BMS-WebView2, 0.1% T40I10D100K, 0.03%
Database reduction
188319235 2125460007
2280260
1704927639
Anytime database reduction
538931777718752157677371534
Reduction factor
349.4
273.2
4.3
22.0

We also use anytime database reduction for closure operation. Suppose that we haveclosed pattern P with core index i. Let transactions t1 , ..., tk ∈ T (P ) have the samei-suffix, i.e., t1 ∩ {i, ..., |I|} = t2 ∩ {i, ..., |I|} =, ..., = tk ∩ {i, ..., |I|}.
Lemma 5. Let j; j < i be an item, and j 0 be items such that j 0 > i and included in all
t1 , ..., tk . Then, if j is not included in at least one transaction of t1 , ..., tk , j 6∈ Clo(Q)holds for any pattern Q including P ∪ {i}.
Proof. Since T (Q) includes all t1 , ..., tk , and j is not included in one of t1 , ..., tk .
Hence, j is not included in Clo(Q).
t
u

2

A
B

1

C
T({5})

3

4

5

3

4

5

6

5

6

7

5

6

7

8

7

8

7

8

2

3

D

1

2

3

E

1

2

3

2

3

F

4

7

5
4

5

6

8

Fig. 6. Transaction A has the minimum size. Fast ppc test accesses only circled items whileclosure operation accesses all items

According to this lemma, we can remove j from t1 , ..., tk from the database if j is
not included
in at least one of t1 , ..., tk . By removing all such items, t1 , ..., tk all beT
come h=1,...,k th . Thus, we can merge them into one transaction similar to the above
reduction. This reduces the number of transactions as much as the reduced database forfrequency counting. Thus, the computation time of closure operation is shorten drastically. We describe the details on anytime database reduction for closure operation.
1. Remove transactions not including P
2. Remove items i such that f rq(P ∪ {i}) < θ
3. Remove items of P
4. Replace the transactions
T1 , ..., Tk having the same i-suffix by the intersection,Ti.e., replace them by {T1 , ..., Tk }.
5.3 Fast Prefix-Preserving Test
Fast prefix-preserving test (fast ppc-test) efficiently checks condition (iii) of ppc-extension
for P ∪ {i}. A straightforward way for this task is to compute the closure of P ∪ {i}.
This usually takes much time since it accesses all items in the occurrences of P . Insteadof this, we check for each j whether j; j < i, j 6∈ P (i − 1) is included in Clo(P ∪ {i})or not. Item j is included in Clo(P ∪ {i}) if and only if j is included in every transaction of T (P ∪ {i}). If we find a transaction not including j, then we can immediately
conclude that j is not included in every transaction of T (P ). Thus, we do not need toaccess all items in occurrences. In particular, we have to check items j in occurrencet∗ of the minimum size, since other items can not be included in every transaction of
T (P ). Fig. 6 showsPan example of accessed items by fast ppc test.
This results O( j∈t∗ \P |T (P ∪ {i} ∪ {j})|) time algorithm, which is much fasterP
than the straightforward algorithm with O( j<i |T (P ∪ {i} ∪ {j})|) time. Table 3
shows the results of computational experiments comparing the number of accesses between closure operation and fast ppc test.
Table 3: Accumulated number of accessed items in all iterations:

Dataset and support connect,60% pumsb,75%, BMS-WebVeiw2,0.1% T40I10D100K,0.1%
Closure operation 1807886455 741205890
50313395
2093327534
Fast ppc test
2333551
2703318
1277221701748
Reduction factor
774.7
274.1
393.9
1230

Algorithm LCM (T :transaction database, θ:support)
1. call E NUM C LOSED PATTERNS(T , ⊥, T ) ;Procedure E NUM C LOSED PATTERNS (T : transaction database,
P :frequent closed pattern, Occ: transactions including P )2. Output P ;3. Reduce T by Anytime database reduction;
4. Compute the frequency of each pattern P ∪ {i}, i > core i(P )by Occurrence deliver with P and Occ ;5. for i := core i(P ) + 1 to |I|
6. Q := Clo(P ∪ {i});7. If P (i − 1) = Q(i − 1) and Q is frequent then// Q is a ppc-extension of P
Call E NUM C LOSED PATTERNS(Q);
8. End for
The version of fast-ppc test is obtained by replacing the lines 6 and 7 by
6. if fast-ppc test is true for P ∪ {i} and P ∪ {i} is frequent thenCall E NUM C LOSED PATTERNS(Q);
Fig. 7. Algorithm LCM with practical speeding up

In fact, the test requires an adjacency matrix (sometimes called a bitmap) representing the inclusion relation between items and transactions. The adjacency matrix
requires O(|T | × |I|) memory, which is quite hard to store for large instances. Hence,
we keep columns of the adjacency matrix for only transactions larger than |I|/δ, whereδ is a constant number. In this way, we can check whether j ∈ t or not in constant time
if j is large, and also in short time by checking items of t if t is small. The algorithm
uses O(δ × ||T ||) memory, which is linear in the input size.

6 Computational Experiments
This section shows the results of computational experiments for evaluating the practical performance of our algorithms on real world and synthetic datasets. Fig. 8 lists thedatasets, which are from the FIMI’03 site (http://fimi.cs.helsinki.fi/):retail, accidents; IBM Almaden Quest research group website (T10I4D100K); UCI ML
repository (connect, pumsb); (athttp://www.ics.uci.edu/ mlearn/MLRepository.html) Click-stream
Data by Ferenc Bodon (kosarak); KDD-CUP 2000 [11] (BMS-WebView-1, BMS-POS)( at http://www.ecn.purdue.edu/KDDCUP/).
To evaluate the efficiency of ppc extension and practical improvements, we implemented several algorithms as follows.
· freqset: algorithm using frequent pattern enumeration· straight: straightforward implementation of LCM (frequency counting by tuples)· occ: LCM with occurrence deliver· occ+dbr: LCM with occurrence deliver and anytime database reduction forboth frequency counting and closure

Fig. 8. Datasets: AvTrSz means average transaction size
Dataset #items #Trans AvTrSz|F||C|
support (%)
BMS-POS 1,657 517,255
6.5 122K–33,400K 122K–21,885K 0.64–0.01
BMS-Web-View1
497 59,602
2.51
3.9K–NA
3.9K–1,241K
0.1–0.01
T10I4D100K 1,000 100,000
10.0 15K–335K
14K–229K
0.15–0.025
kosarak 41,270 990,000
8.10 0.38K–56,006K 0.38K–17,576K 1–0.08
retail 16,470 88,162
10.3 10K–4,106K
10K–732K
0.32–0.005
accidents
469 340,183
33.8 530–10,692K
530–9,959K
70–10
pumsb 7,117 49,046
74.0
2.6K–NA
1.4K–44,453K
95–60
connect
130 67,577
43.0
27K–NA
3.4K–8,037K
95–40
Fig. 9. Computation time for datasets

freqsetstraight
occ
occ+dbrocc+ftest#freq closed#freqset

10

1
0.16%

0.08%

0.04%

0.02%

0.01%

10

1
0.08%

0.06%

0.04%

0.02%

100

10
0.64% 0.32% 0.16% 0.08% 0.04% 0.02% 0.01%
support0.01%

freqsetstraight
occ
occ+dbrocc+ftest#freq closed#freqset

10000

10

1

0.1

0.1

10

1

accidents

100

freqsetstraight
occ
occ+dbrocc+ftest#freq closed#freqset

10

1

0.1

10000

supportconnecttime(sec), #solutions(1000)

1000

freqsetstraight
occ
occ+dbrocc+ftest#freq closed#freqset

100

10

1

50%

40%

30%

20%

10%

0.1

10000

pumsb

1000

freqsetstraight
occ
occ+dbrocc+ftest#freq closed#freqset

100

10

1

90% 80% 70% 60% 50% 40% 30% 20% 10%
support0.1

60%

supporttime(sec), #solutions(1000)

0.0
05
%

0.0
1%

0.0
2%

0.0
4%

0.0
8%

0.1
6%

70%

0.3
2%

time(sec), #solutions(1000)

freqsetstraight
occ
occ+dbrocc+ftest#freq closed#freqset

support1000

time(sec), #solutions(1000)

retail100

freqsetstraight
occ
occ+dbrocc+ftest#freq closed#freqset100

support1000

kosarak1000

1%time(sec), #solutions(1000)

100

freqsetstraight
occ
occ+dbrocc+ftest#freq closed#freqset

1

BMSWebView1

0.16%

1000

0.005%
support1000

BMS-pos

0.8
0%
0.6
0%
0.4
0%
0.2
0%
0.1
0%
0.0
9%
0.0
8%

100

10000

time(sec), #solutions(1000)

T10I4D100K

time(sec), #solutions(1000)time(sec), #solutions(1000)

1000

90%
0.1

80%

70%

60%

50%

40%
support· occ+fchk: LCM with occurrence deliver, anytime database reduction forfrequency counting, and fast ppc test
The figure also displays the number of frequent patterns and frequent closed patterns, which are written as #freqset and #freq closed. The algorithms were implemented
in C and compiled with gcc 3.3.1. The experiments were run on a notebook PC with mobile Pentium III 750MHz, 256MB memory. Fig. 9 plots the running time with varying
minimum supports for the algorithms on the eight datasets.
From Fig. 9, we can observe that LCM with practical optimization (occ, occ+dbr,
occ+fchk) outperforms the frequent pattern enumeration-based algorithm (freqset). The
speed up ratio of the ppc extension algorithm (straight) against algorithm freqset totallydepends on the ratio of #freqset and #freq. closed. The ratio is quite large for several
real world and synthetic datasets with small supports, such as BMS-WebView, retails,
pumsb, and connect. On such problems, sometimes the frequent pattern based algorithm
takes quite long time while LCM terminates in short time.
Occurrence deliver performs very well on any dataset, especially on sparse datasets,such as BMS-WebView, retail, and IBM datasets. In such sparse datasets, since T ({i})
is usually larger than T (P ∪ {i}), occurrence deliver is efficient.
Anytime database reduction decreases the computation time well, especially in
dense datasets or those with large supports. Only when support is very small, closed
to zero, the computation time were not shorten, since a few items are eliminated andfew transactions become the same. In such cases, fast ppc test performs well. However,fast ppc test does not accelerate speed so much in dense datasets or large supports.
For a detailed study about the performance of our algorithm compared with other algorithms, consult the companion paper [18] and the competition report of FIMI’03 [7].
Note that the algorithms we submitted to [18, 7] were old versions, which does not include anytime database reduction, thus they are slower than the algorithm in this paper.

7 Conclusion
We addressed the problem of enumerating all frequent closed patterns in a given transaction database, and proposed an efficient algorithm LCM to solve this, which uses
memory linear in the input size, i.e., the algorithm does not store the previously obtained patterns in memory. The main contribution of this paper is that we proposed
prefix-preserving closure extension, which combines tail-extension of [5] and closure
operation of [13] to realize direct enumeration of closed patterns.
We recently studied frequent substructure mining from ordered and unordered trees
based on a deterministic tree expansion technique called the rightmostexpansion [2–4]. There have been also pioneering works on closed pattern mining in sequences andgraphs [17, 19]. It would be an interesting future problem to extend the framework ofprefix-preserving closure extension to such tree and graph mining.

Acknowledgment
We would like to thank Professor Ken Satoh of National Institute of Informatics andProfessor Kazuhisa Makino of Osaka University for fruitful discussions and comments

on this issue. This research was supported by group research fund of National Instituteof Informatics, Japan. We are also grateful to Professor Bart Goethals, and people supporting FIMI’03 Workshop/Repository, and the authors of the datasets for the datasets
available by the courtesy of them.

References
1. R. Agrawal,H. Mannila,R. Srikant,H. Toivonen,A. I. Verkamo, Fast Discovery of Association
Rules, In Advances in Knowledge Discovery and Data Mining, MIT Press, 307–328, 1996.
2. T. Asai, K. Abe, S. Kawasoe, H. Arimura, H. Sakamoto, S. Arikawa, Efficient Substructure
Discovery from Large Semi-structured Data, In Proc. SDM’02, SIAM, 2002.
3. T. Asai, H. Arimura, K. Abe, S. Kawasoe, S. Arikawa, Online Algorithms for Mining Semistructured Data Stream, In Proc. IEEE ICDM’02, 27–34, 2002.
4. T. Asai, H. Arimura, T. Uno, S. Nakano, Discovering Frequent Substructures in Large Unordered Trees, In Proc. DS’03, 47–61, LNAI 2843, 2003.
5. R. J. Bayardo Jr., Efficiently Mining Long Patterns from Databases, In Proc. SIGMOD’98,
85–93, 1998.
6. Y. Bastide, R. Taouil, N. Pasquier, G. Stumme, L. Lakhal, Mining Frequent Patterns withCounting Inference, SIGKDD Explr., 2(2), 66–75, Dec. 2000.
7. B. Goethals, the FIMI’03 Homepage, http://fimi.cs.helsinki.fi/, 2003.
8. E. Boros, V. Gurvich, L. Khachiyan, K. Makino, On the Complexity of Generating Maximal
Frequent and Minimal Infrequent Sets, In Proc. STACS 2002, 133-141, 2002.
9. D. Burdick, M. Calimlim, J. Gehrke, MAFIA: A Maximal Frequent Itemset Algorithm forTransactional Databases, In Proc. ICDE 2001, 443-452, 2001.
10. J. Han, J. Pei, Y. Yin, Mining Frequent Patterns without Candidate Generation, In Proc. SIGMOD’00, 1-12, 2000
11. R. Kohavi, C. E. Brodley, B. Frasca, L. Mason, Z. Zheng, KDD-Cup 2000 Organizers’ Report: Peeling the Onion, SIGKDD Explr., 2(2), 86-98, 2000.
12. H. Mannila, H. Toivonen, Multiple Uses of Frequent Sets and Condensed Representations,
In Proc. KDD’96, 189–194, 1996.
13. N. Pasquier, Y. Bastide, R. Taouil, L. Lakhal, Efficient Mining of Association Rules Using
Closed Itemset Lattices, Inform. Syst., 24(1), 25–46, 1999.
14. N. Pasquier, Y. Bastide, R. Taouil, L. Lakhal, Discovering Frequent Closed Itemsets for
Association Rules, In Proc. ICDT’99, 398-416, 1999.
15. J. Pei, J. Han, R. Mao, CLOSET: An Efficient Algorithm for Mining Frequent Closed Itemsets,
In Proc. DMKD’00, 21-30, 2000.
16. R. Rymon, Search Through Systematic Set Enumeration, In Proc. KR-92, 268–275, 1992.
17. P. Tzvetkov, X. Yan, and J. Han, TSP: Mining Top-K Closed Sequential Patterns, In
Proc. ICDM’03, 2003.
18. T. Uno, T. Asai, Y. Uchida, H. Arimura, LCM: An Efficient Algorithm for Enumerating Frequent Closed Item Sets, In Proc. IEEE ICDM’03 Workshop FIMI’03, 2003. (Available as
CEUR Workshop Proc. series, Vol. 90, http://ceur-ws.org/vol-90)
19. X. Yan and J. Han, CloseGraph: Mining Closed Frequent Graph Patterns, In Proc. KDD’03,
ACM, 2003.
20. M. J. Zaki, Scalable Algorithms for Association Mining, Knowledge and Data Engineering,12(2), 372–390, 2000.
21. M. J. Zaki, C. Hsiao, CHARM: An Efficient Algorithm for Closed Itemset Mining, In
Proc. SDM’02, SIAM, 457-473, 2002.