LCM: An Eﬃcient Algorithm for
Enumerating Frequent Closed Item Sets
Takeaki Uno1 , Tatsuya Asai2 , Yuzo Uchida2, Hiroki Arimura2
1
National Institute of Informatics
2-1-2 Hitotsubashi, Chiyoda-ku, Tokyo, 101-8430, Japane-mail: uno@nii.jp
2
Department of Informatics, Kyushu University, 6-10-1 Hakozaki, Fukuoka 812-0053, JAPANe-mail:{t-asai,y-uchida,arim}@i.kyushu-u.ac.jp
an occurrence of X. For a given constant α ≥ 0,
an item set X is called frequent if |T (X)| ≥ α. If
a frequent item set is included in no other frequentset, it is said to bemaximal. For a transaction set
S ⊆ T , let I(S) = T ∈S T . If an item set X satisﬁes
I(T (X)) = X, then X is called a closed item set. We
denote by F and C the sets of all frequent itemsets
and all frequent closed item sets, respectively.

Abstract:
In this paper, we propose three algorithms LCMfreq, LCM, and LCMmax for mining all frequent sets,
frequent closed item sets, and maximal frequent sets,
respectively, from transaction databases. The main
theoretical contribution is that we construct treeshaped transversal routes composed of only frequent
closed item sets, which is induced by a parent-childrelationship deﬁned on frequent closed item sets. By
traversing the route in a depth-ﬁrst manner, LCM
ﬁnds all frequent closed item sets in polynomial time
per item set, without storing previously obtained
closed item sets in memory. Moreover, we introduce
several algorithmic techniques using the sparse anddense structures of input data. Algorithms for enumerating all frequent item sets and maximal frequent
item sets are obtained from LCM as its variants. By
computational experiments on real world and synthetic databases to compare their performance to theprevious algorithms, we found that our algorithms
are fast on large real world datasets with natural distributions such as KDD-cup2000 datasets, and manyother synthetic databases.

In this paper, we propose an eﬃcient algorithm
LCM for enumerating all frequent closed item sets.
LCM is an abbreviation of Linear time Closed item
set Miner. Existing algorithms for this task basicallyenumerate frequent item sets with cutting oﬀ unnecessary frequent item sets by pruning. However, thepruning is not complete, hence the algorithms operate unnecessary frequent item sets, and do something
more. In LCM, we deﬁne a parent-child relationship between frequent closed item sets. The relationship induces tree-shaped transversal routes composed
only of all the frequent closed item sets. Our algorithm traverses the routes, hence takes linear timeof the number of frequent closed item sets. Thisalgorithm is obtained from the algorithms for enumerating maximal bipartite cliques [14, 15], which isdesigned based on reverse search technique [3, 16].

1. Introduction

In addition to the search tree technique for closed
item sets, we use several techniques to speed-up the
update of the occurrences of item sets. One technique
is occurrence deliver, which simutaneously computes
the occurrence sets of all the successors of the current item set during a single scan on the current occurrence set. The other is diﬀsets proposed in [18].
Since there is a trade-oﬀ between these two methods
that the former is fast for sparse data while the latter
is fast for dense data, we developed the hybrid algorithm combining them. In some iterations, we make

Frequent item set mining is one of the fundamental problems in data mining and has many applications such as association rule mining [1], inductive
databases [9], and query expansion [12].
Let E be the universe of items, consisting of items
1, ..., n. A subset X of E is called an item set. T
is a set of transactions over E, i.e., each T ∈ T
is composed of items of E. For an item set X, let
T (X) = { t ∈ T | X ⊆ t } be the set of transactions
including X. Each transaction of T (X) is called1

a decision based of the estimation of their computation time, hence our algorithm can use appropriate
one for dense parts and sparse parts of the input.
We also consider the problems of enumerating all
frequent sets, and maximal frequent sets, and derive
two algorithms LCMfreq and LCMmax from LCM.
LCMmax is obtained from LCM by adding the explicit check of maximality. LCMfreq is not merely
a LCM without the check of closedness, but alsoachives substantial speed-up using closed itemset discovery techniques because it enumerates only the representatives of groups of frequent item sets, and generate other frequent item sets from the representatives.
From computer experiments on real and artiﬁcial
datasets with the previous algorithms, we observedthat our algorithms LCMfreq, LCM, and LCMmaxsigniﬁcantly outperform the previous algorithms onreal world datasets with natural distributions such
as BMS-Web-View-1 and BMS-POS datasets in the
KDD-CUP 2000 datasets as well as large synthesis datasets such as IBM T10K4D100K. The performance of our algorithms is similar to other algorithms for hard datasets such as Connect and Chess
datasets from UCI-Machine Learning Repository, butless signiﬁcant than MAFIA, however LCM works
with small memory rather than other algorithms.
The organization of the paper is as follows. In Section 2, we explain our tree enumeration method for
frequent closed item sets and our algorithm LCM. In
Section 3, we describe several algorithmic techniques
for speeding up and saving memory. Then, Section 4
and 5 give LCMmax and LCMfreq for maximal andall frequent item sets, respectively. Techniques for
implementation is described in Section 6, and the results of computational experiments are reported in
Section 7. Finally, we conclude in Section 8.

T
E
i(X)

X
occurrences of X

parent of X
occurrences of the parent

Figure 1: An example of the parent of X: The parentof X is obtained by deleting items larger than i(X)(in the gray area) and take a closure.
preﬁx of Y if X = Y (i) holds for i = tail(X). Then,the parent-child relation P for the set enumeration
tree for F is deﬁne as X = P(Y ) iﬀ Y = X ∪ {i} forsome i > tail(X), or equivalently, X = Y \{tail(Y )}.
Then, the whole search space for F forms a preﬁx
tree (or trie) with this edge relation P.
Now, we deﬁne the parent-child relation P for
closed item sets in C as follows. For X ∈ C, we deﬁne the parent of X by P(X) = I(T (X(i(X) − 1))),
where i(X) be the minimum item i such that T (X) =T (X(i)) but T (X) = T (X(i − 1)). If Y is the parentof X, we say X is a child of Y . Let ⊥ = I(T (∅)) be
the smallest item set in C called the root . For any
X ∈ C \ {⊥}, its parent P(X) is always deﬁned andbelongs to C. An illustration is given in Fig. 1.
For any X ∈ C and its parent Y , the proper inclusion Y ⊂ X holds since T (X(i(X) − 1)) ⊂ T (X).
Thus, the relation P is acyclic, and its graph representation forms a tree. By traversing the tree ina depth-ﬁrst manner, we can enumerate all the frequent closed item sets in linear time in the size of thetree, which is equal to the number of the frequent
closed item sets in C. In addition, we need not store
the tree in memory. Starting from the root ⊥, we
ﬁnd a child X of the root, and go to X. In the sameway, we go to a child of X. When we arrive at a leafof the tree, we backtrack, and ﬁnd another child. Repeating this process, we eventually ﬁnd all frequent
closed item set in C.
To ﬁnd the children of the current frequent closed
item set, we use the following lemma. For an item set
X and an index i, let X[i] = X ∪ H where H is theset of the items j ∈ I(T (X ∪ {i})) satisfying j ≥ i.

2. Enumerating Frequent Closed Item
Sets
In this section, we introduce a parent-child relationship between frequent closed item sets in C, and describe our algorithm LCM for enumeration them.
Recent eﬃcient algorithms for frequent item sets,e.g.,[4, 17, 18], use a tree-shaped search structure for
F , called the set enumeration tree [4] deﬁned as follows. Let X = {x1 , . . . , xn} be an itemset as anordered sequence such that x1 < · · · < xn , where thetail of X is tail(X) = xn ∈ E. Let X, Y be item
sets. For an index i, X(i) = X ∩ {1, . . ., i}. X is a

Lemma 1 X  is a child of X ∈ C (X  ∈ C and theparent of X  is X) if and only if(cond1) X  = X[i] for some i > i(X),(cond2) X  = I(T (X  )) (X  is a closed item set)(cond3) X  is frequent2

Proof : Suppose that X  = X[i] satisﬁes the conditions (cond1), (cond2) and (cond3). Then, X  ∈ C.
Since T (X(i − 1)) = T (X) and T (X(i − 1) ∪ {i}) =T (X  ) holds thus i(X  ) = i holds. Hence, X  is achild of X. Suppose that X  is a child of X. Then,(cond2) and (cond3) hold. From the deﬁnition ofi(X  ), T (X(i(X  ))∪{i(X  )}) = T (X  ) holds. Hence,
X  = X[i(X  )] holds. We also have i(X  ) > i(X)since T (X  (i(X  ) − 1)) = T (X). Hence (cond1)
holds.

occurrences
A
B
C
D
F
G
H
T(X)

A
C
D
F
G
jQ[i]
= T(X[i])

• • •

•••

A
C
D
F
G

A
B
C
F

jQ[|E|-2] jQ[|E|-1]

A
B
C
F
H
jQ[|E|]

Right first sweep

Clearly, T (X[i]) = T (X ∪ {i}) holds if (cond2)
I(T (X[i])) = X[i] holds. Note that no child X  of X
satisﬁes X[i] = X[i ], i = i , since the minimum itemof X[i]\X and X[i ]\X are i and i , respectively. Using this lemma, we construct the following algorithm
scheme for, given a closed itemset X, enumerating alldescendants in the search tree for closed itemsets.

Figure 2: Occurrence deliver and right ﬁrst sweep:
In the ﬁgure, J [i] is written as JQ[i]. For each occurrence T of X, occurrence deliver inserts T to J [i]such that i ∈ T. When the algorithm generates a recursive call respect to X[|E| − 2], the recursive calls
respect to X[|E| − 1] and X[|E|] have been terminated, J [|E| − 1] and J [|E|] are cleared. The recursive call of X[|E|−2] uses only J [|E| − 1] and J [|E|],and hence the algorithm re-uses them in the recursive
call.

Algorithm LCM (X : frequent closed item set)
1. output X
2. For each i > i(X) do
3. If X[i] is frequent and X[i] = I(T (X[i])) thenCall LCM( X[i] )4. End for

3. Reducing Computation Time
The computation time of LCM described in the previous section is linear in |C|, with a factor depending
on T (X) for each closed item set X ∈ C. However,this still takes long time if it is implemented in astraightforward way. In this section, we introduce
some techniques based on sparse and dense structuresof the input data.
Occurrence Deliver. First, We introduce thetechnique called the occurrence deliver for reducing
the construction time for T (X[i]), which is needed
to check (cond3). This technique is particularly eﬃcient in the case that |T (X[i])| is much smaller than
|T (X)|. In a usual way, T (X[i]) is obtained from
T (X) in O(|T (X)|) time by removing all transactions not including i based on the equiality T (X[i]) =T (X ∪ {i}) = T (X) ∩ T ({i}) (this method is known
as down-project). Thus, the total computation for all
children takes |E| scans and O(|T (X)| · |E|) time.
Instead of this, we build for all i = i(X), . . . , |E|
def
the occurrence lists J [i] = T (X[i]) simultaneously
by scanning the transactions in T (X) at once as follows. We initialize J [i] = ∅ for all i = i(X), . . . , |E|.
For each T ∈ T (X) and for each i ∈ T (i > i(X)),
we insert T to J [i]. See Fig. 2 for explanation, where
we write jQ[i] for J [i]. This correctly computes J [i]for all i in the total time O(|T (X)|). Furthermore,
we need not make recursive call of LCM for X[i] if
T (X[i]) = ∅ (this is often called lookahead [4]). In

Theorem 1 Let 0 < σ < 1 be a minimum support.
Algorithm LCM enumerates, given the root closed
item set ⊥ = I(T (∅)), all frequent closed item sets
in linear time in the number of frequent closed item
sets in C.
The existing enumeration algorithm for frequent
closed item sets are based on backtrack algorithm,
which traverse a tree composed of all frequent item
sets in F , and skip some item sets by pruning thetree. Since the pruning is not complete, however,these algorithms generate unnecessary frequent item
sets. On the other hand, the algorithm in [10] directly
generates only closed item sets with the closure operation I(T (·)) as ours, but their method may generate
duplicated closed item sets and needs expensive duplicate check.
On the other hand, our algorithm traverses a treecomposed only of frequent closed item sets, and each
iteration is not as heavy as the previous algorithms.
Hence, our algorithm runs fast in practice. If we consider our algorithm as a modiﬁcation of usual backtracking algorithm, each iteration of our algorithm
re-orders the items larger than i(X) such that theitems not included in X follow the items included in
X. Note that the parent X is not a preﬁx of X[i] ina recursive call. The check of (cond2) can be considered as a pruning of non-closed item sets.
3

our experiments on BMS instances, the occurrencedeliver reduces the computation time up to 1/10 insome cases.
Right-ﬁrst sweep.
The occurrence deliver
method needs eager computation of the occurrence
sets J [i] = T (X[i]) for all children before expanding one of them. A simple implementation of it may
require much memory than the ordinary lazy computation of T (X[i]) as in [17]. However, we can reducethe memory usage using a method called the rightﬁrst sweep as follows.
Given a parent X, we make the recursive call for
X[i] in the decreasing order for each i = |E|, . . ., i(X)(See Fig. 2). At each call of X[i], we collect the
memory allocated before for J [i + 1], . . ., J [|E|] andthen re-use it for J [i]. After terminating the call for
X[i], the memory for J [i] is released for the future
use in J [j] for j < i. Since |J [i]| = |T (X[i])|≤|T ({i})| for any i and X, the total memory
|J
[i]|
i

is bounded by the input size ||T || = T ∈T |T |, andthus, it is suﬃcient to allocate the memory for J atonce as a global variable.
Diﬀsets. In the case that |T (X[i])| is nearly equal
to |T (X)| we use the diﬀset technique proposed in[18]. The diﬀset for index i is DJ [i] = T (X)\T (X[i]),where T (X[i]) = T (X ∪ {i}). Then, the frequencyof X[i] is obtained by |T (X[i])| = |T (X)| − |DJ [i]|.
When we generate a recursive call respect to X[i], we
update DJ [j], j > i by setting DJ [j] to be DJ [j] \DJ [i] in time O( i>i(X),X[i]∈F ((|T (X)|−|T (X[i])|).
Diﬀsets are needed for only i such that X[i] is frequent. By diﬀsets, the computation time for instances such as connect, chess, pumsb are reduced
to 1/100, where |T (X[i])| is as large as |T (X)|.
Hybrid Computation. As we saw in the preceding subsections, our occurrence deliver is fast when
|T (X[i])| is much smaller than |T (X)| while the diﬀset of [18] is fast when |T (X[i])| is nearly close to|T (X)|. Therefore, our LCM dinamically decides
which of occurrence deliver and diﬀsets we will use.
To do this,
we compare two quantities on X:
A(X) = i |T (X ∪ {i})| andB(X) = i:X∪{i}∈F (|T (X)| − |T (X ∪ {i})|).
For some ﬁxed constant α > 1, we decide to use
the occurrence deliver if A(X) < αB(X) and thediﬀset otherwise. We make this decision only at thechild iterations of the root set ⊥ since this decision
takes much time. Empirically, restricting the rangei ∈ {1, . . ., |E|} of the the index i in A(X) and B(X)to i ∈ {i(X) + 1, . . . , |E|} results signiﬁcant speedup. By experiments on BMS instances, we observethat the hybrid technique reduces the computation

time up to 1/3. The hybrid technique is also usefulin reducing the memory space in diﬀset as follows.
Although the memory B(X) used by diﬀsets is notbounded by the input size ||T || in the worst case,
it is ensured in hybrid that B(X) does not exceedA(X) ≤ ||T || because the diﬀset is chosen only whenA(X) ≥ αB(X).
Checking the closedness in occrrence deliver. Another key is to eﬃciently check the closedness X[i] = I(T (X[i])) (cond 2). The straightforward computation of the closure I(T (X[i])) takes
much time since it requires the access to the wholesets T (X[j]), j < i and i is usually as large as |E|.
By deﬁnition, (cond 2) is violated iﬀ there exists
some j ∈ {1, . . . , i − 1} such that j ∈ T for every T ∈ T (X ∪ {i}). We ﬁrst choose a transaction T ∗ (∪{i}) ∈ T (X ∪ {i}) of minimum size, andtests if j ∈ T for increasing j ∈ T ∗ (∪{i}). This
results O( j∈T ∗ (X∪{i}) m(X[i], j)) time algorithm,
where m(X  , j) is the maximum index m such that
all of the ﬁrst m transactions of T (X  ) include j,which is much
faster than the straightforward algorithm with O( j<i |T (X ∪ {i} ∪ {j}])|) time.
In fact, the eﬃcient check requires the adjacency
matrix (sometime called bitmap) representing the inclusion relationship between items and transactions.
However, the adjacency matrix requires O(|T | × |E|)
memory, which is quite hard to store for large instances. Hence, we make columns of adjacency
matrixfor only transactions of size larger than
( T ∈T |T |)/δ.
 Here δ is a constant. This uses atmost O(δ × T ∈T |T |), linear in the input size.
Checking the closedness in diﬀsets. In thecase that |T (X[i])| is nearly equal to |T (X)|, theabove check is not done in short time. In this case,we keep diﬀset DJ [j] for all j < i, i ∈ X suchthat X[i] is frequent. To maintain DJ for all i isa heavy task, thus we discard unnecessary DJ ’s asfollows. If T (X ∪ {j}) includes an item included
in no T (X[i ]), i > i(X), then for any descendantX  of X, j ∈ I(T (X  [j  ])) for any j  > i(X  ).
Hence, we no longer have to keep DJ [j] for such
j. Let N C(X) be the set of items j such that X[j]is frequent and any item of T (X) \ T (X ∪ {j}) is
included in some T (X[j  ]), j  > i(X). Then, thecomputation
time for checking (cond2) is written
as O( j∈N C(X),j<i |T (X) \ T (X ∪ {j})|). By checking (cond2) in these ways, the computation time forchecking (cond2) is reduced from 1/10 to 1/100.
Detailed Algorithm. We present below the description of the algorithm LCM, which recursively
computes (X, T (X), i(X)), simultaneously.
4global: J , DJ

111 ••• 1/* Global sets of lists */Algorithm LCM()
1. X := I(T (∅)) /* The root ⊥ */2. For i := 1 to |E|
3. If X[i] satisﬁes (cond2) and (cond3) thenCall LCM Iter( X[i], T (X[i]), i ) or
Call LCMd Iter2( X[i], T (X[i]), i, DJ )based on the decision criteria
4. End for
LCM Iter( X, T (X), i(X) ) /* occurrence deliver */1. output X
2. For each T ∈ T (X)For each j ∈ T, j > i(X), insert t to J [j]4. For each j, J [j] = ∅ in the decreasing order
5. If |J [j]| ≥ α and (cond2) holds thenLCM Iter( T (J [j]), J [j], j )6. Delete J [j]7. End for000 ••• 0

Figure 3: Hypercube decomposition: LCMfreq decomposes a closed item set class into several sublattices (gray rectangles).
complexity but increase the computation time. In thecase of occurrence deliver, we generate T (X ∪{j}) for
all j in the same way as the occurrence deliver, andcheck the maximality. This takes O( j<i(X) |T (X ∪{j}|) time. In the case of diﬀerence update, we do
not discard diﬀsets unnecessary for closed item set
enumeration. We keep diﬀsets DJ for all j such thatX ∪ {j} is frequent.
To update and maintain this,
we spend O( j,X∪{j}∈F |T (X) \ T (X ∪ {j})|) time.
Note that we are not in need of check the maximality
if X has a child.

LCM Iter2( X, T (X), i(X), DJ ) /* diﬀset */1. output X
2. For each i, X[i] is frequent
3. If X[i] satisﬁes (cond2) then4.
For each j, X[i] ∪ {j} is frequent,DJ  [j] := DJ [j] \ DJ [i]5.
LCM Iter2( T (J [j]), J [j], j, DJ  )6. End if
7. End for

Theorem 3 Algorithm LCMmax enumerates all
maximal frequent
item sets in O( i |T (X ∪ {i})|)
time, or O( i,X∪{i}∈F ((|T (X)|−|T (X ∪{i})|)) timefor each frequent closed item set X, with memory linear in the input size.

Theorem 2 Algorithm LCM 
enumerates all frequent closed item sets in O( j>i(X) |T (X[j])| +



time,
j>i(X),X[j]∈Fj  ∈T ∗ (X) m(X[j], j ))orO( i>i(X),X[i]∈F ((|T (X)| − |T (X[i])|) +j∈N C(X),j<i |T (X) \ T (X ∪ {j})|)) time foreach frequent closed item set X, with memory linear
to the input size.

4.

closed item
set class

01 lattice

5. Enumerating Frequent Sets
In this section, we describe an enumeration algorithm for frequent item sets. The key idea of ouralgorithm is that we classify the frequent item sets
into groups and enumerate the representative of eachgroup. Each group is composed of frequent item sets
included in the class of a closed item set. This idea
is based on the following lemma.

Enumerating Maximal FrequentSets

In this section, we explain an enumeration algorithmof maximal frequent sets with the use of frequent
closed item set enumeration. The main idea is very
simple. Since any maximal frequent item set is a frequent closed item set, we enumerate frequent closed
item sets and output only those being maximal frequent sets. For a frequent closed item set X, X is a
maximal frequent set if and only if X ∪ {i} is infrequent for any i ∈ X. By adding this check to LCM,
we obtain LCMmax.
This modiﬁcation does not increase the memory

Lemma 2 Suppose that frequent item sets X andS ⊃ X satisfy T (X) = T (S). Then, for any item
set X  including X, T (X  ) = T (X  ∪ S).
Particularly, T (X  ) = T (R) holds for any X  ⊆R ⊆ X  ∪S, hence all R are included in the same classof a closed item set. Hence, any frequent item set X 5is generated from X  \ (S \ X). We call X  \ (S \ X)representative.
Let us consider a backtracking algorithm ﬁnding
frequent item sets which adds items one by one in lexicographical order. Suppose that we currently have afrequent item set X, and ﬁnd another frequent item
set X ∪ {i}. Let S = X[i]. Then, according to theabove lemma, we can observe that for any frequent
item set X  including X and not intersecting S \ X,any item set including X  and included in X  ∪ S is
also frequent. Conversely, any frequent item set including X is generated from X  not intersecting S\X.
Hence, we enumerate only representatives including
X and not intersecting S \ X, and generate otherfrequent item sets by adding each subset of S \ X.
This method can be considered that we “decompose”
classes of closed item sets into several sublattices (hypercubes) each of whose maximal and minimal elements are S and X  , respectively (see Fig. 3). We
call this technique hypercube decomposition.
Suppose that we are currently operating a representative X  including X, and going to generate a recursive call respect to X  ∪ {j}. Then, if(X  [i] \ X  ) \ S = ∅, X  and S ∪ (X  [i] \ X  ) satisﬁes
the condition of Lemma 2. Hence, we add X  [i] \ X 
to S.
We describe LCMfreq as follows.

call. Hence, the algorithm ﬁrst starts with occurrence deliver, and compares them in each iteration.
If j>i(X),X[j]∈F |T (X) \ T (X[j])| becomes smaller,
then we change to diﬀsets. Note that these estimators can computed in short time by using the resultof occurrence deliver.
Theorem 4 LCMfreq enumerates all frequent
sets of F in O( j>i(X) |T (X[j])|) time orO( j>i(X),X[j]∈F |T (X) \ T (X[j])|) time foreach frequent set X, within O( T ∈T |T |) space.
Particularly, LCMfreq requires one integer for each
item of any transaction, which is required to store theinput data. Other memory LCMfreq uses is boundedby O(|T | + |E|).
Experimentally, an iteration of LCMfreq inputting frequent set X takes O(|T (X)| + |X|)
or O((size of diﬀset) + |X|) steps in average. In
some sense, this is optimal since we have to takeO(|X|) time to output, and O(|T (X)|) time orO((size of diﬀset)) time to check the frequency of X.

6. Implementation

Algorithm LCMfreq ( X : representative,
S : item set, i : item )1. Output all item sets R, X ⊆ R ⊆ X ∪ S
2. For each j > i, j ∈ X ∪ S
3. If X ∪ {j} is frequent thenCall LCMfreq ( X ∪ {j}, S ∪ (X[j] \ (X ∪ {j})), j)
4. End for
For some synthetic instances such that frequent
closed item sets are fewer than frequent item sets,
the average size of S is up to 5. In these cases, thealgorithm ﬁnds 2|S| = 32 frequent item sets at once,
hence the computation time is reduced much by the
improvement.
To check the frequency of all X ∪ {j}, we canuse occurrence deliver and diﬀsets used for LCM.
LCMfreq does not require the check of (cond2),hence
 The computation time of each iteration isO( j>i(X) |T (X[j])|) time for occurrence deliver,and O( j>i(X),X[j]∈F |T (X) \ T (X[j])|) for diﬀsets.
Since the computation time change, we
use another estimatorsfor hybrid. In almost allcases, if once
|T (X) \ T (X[j])| bej>i(X),X[j]∈Fcomes smaller thanj>i(X) |T (X[j])|, the condition holds in any iteration generated by a recursive

In this section, we explain our implementation. First,
we explain the data structure of our algorithm. A
transaction T of input data is stored by an array withlength |T |. Each cell of the array stores the index of
an item of T. For example, t = {4, 2, 7} is stored in
an array with 3 cells, [2, 4, 7]. We sort the elements of
the array so that we can take {i, ..., |E|} ∩ T in linear
time of {i, ..., |E|}∩T. J is also stored in arrays in thesame way. We are not in need of doubly linked lists
or binary trees, which take much time to be operated.
To reduce the practical computation time, we sortthe transactions by their sizes, and items by the number of transactions
including them. Experimentally,
this reduces j>i(X) |T (X ∪{j})|. In some cases, thecomputation time has been reduced by a factor of
1/3.

7. Computational Experiments
To examine the practical eﬃciency of our algorithms,
we run the experiments on the real and synthetic
datasets, which are made available on FIMI’03 site.
In the following, we will report the results of the experiments.
6

Table 1: The datasets. AvTrSz means the average transaction size
Dataset #items #Trans AvTrSz
#FI
#FCI
#MFI
Minsup (%)
BMS-Web-View1
497 59,602
2.51 3.9K–NA
3.9K–1241K 2.1K–129.4K 0.1–0.01
BMS-Web-View2 3,340 77,512
4.62 24K–9897K
23K–755K
3.9K–118K
0.1–0.01
BMS-POS 1,657 517,255
6.5 122K–33400K 122K–21885K 30K–4280K
0.1–0.01
T10I4D100K 1,000 100,000
10.0 15K–335K
14K–229K
7.9K–114K 0.15–0.025
T40I10D100K 1,000 100,000
39.6
2–0.5
pumsb 7,117 49,046
74.0
95–60
pumsb star 7,117 49,046
50.0
50–10
mushroom
120
8,124
23.0
20–0.1connect
130 67,577
43.0
95–40
chess
76
3196
37.0
90–30

7.1

Datasets and Methods

7.2

We implemented our algorithms our three algorithms
LCMfreq (LCMfreq), LCM (LCM), LCMmax (LCMmax) in C and compiled with gcc3.2.
The algorithms were tested on the datasets shownin Table 1. available from the FIMI’03 homepage1 ,which include: T10I4D100K, T40I10D100K fromIBM Almaden Quest research group; chess, connect, mushroom, pumsb, pumsb star from UCI ML
repository2 and PUMSB; BMS-WebView-1, BMSWebView-2, BMS-POS from KDD-CUP 20003.
We compare our algorithms LCMfreq, LCM, LCMmax with the following frequent item set mining algorithms: Implementations of Fp-growth [7], Eclat [17],Apriori [1, 2] by Bart Goethals 4 ; We also compare the LCM algorithms with the implementation ofMaﬁa [6], a fast maximal frequent pattern miner, by
University of Cornell’s Database group 5 . This versions of maﬁa with frequent item sets, frequent closed
item sets, and maximal frequent item sets options
are denoted by maﬁa-ﬁ, maﬁa-fci, maﬁa-mﬁ, respectively. Although we have also planned to make theperformance comparison with Charm, the state-ofthe-art frequent closed item set miner, we gave up thecomparison in this time due to the time constraint.
All experiments were run on a PC with the conﬁguration of Pen4 2.8GHz, 1GB memory, and RPM 7200
hard disk of 180GB. In the experiments, LCMfreq,
LCM and LCMmax use at most 123MB, 300MB, and300MB of memory, resp. Note that LCM and LCMmax can save the memory use by decreasing δ.

Figures 6 through Figure 12 show the running timewith varying minimum supports for the seven algorithms, namely LCMfreq, LCM, LCMmax, FPgrowth, eclat, apriori, maﬁa-mﬁ on the nine datasets
described in the previous subsection. In the following, we call all, maximal, closed frequent item set
mining simply by all, maximal, closed.
Results on Synthetic Data
Figure 4 shows the running time with minimum support ranging from 0.15% to 0.025% on IBM-Artiﬁcial
T10I4D100K datasets. From this plot, we see thatmost algorithms run within around a few 10 minutes and the behaviors are quite similar when minimum support increases. In Figure 4, All of LCMmax,
LCM, and LCMfreq are twice faster than FP-growth
on IBM T10I4D100K dataset. On the other hand,Maﬁa-mﬁ, Maﬁa-fci, and Maﬁa-ﬁ are slower than every other algorithms. In Figure 5, Maﬁa-mﬁ is fastest
for maximal, and LCMfreq is fastest for all, for minimum support less than 1% on IBM T10I4D100K
dataset.
Results on KDD-CUP datasets
Figures 6 through Figure 8 show the running timewith range of minimum supports from ranging from
0.1% to 0.01% on three real world datasets BMSWebView-1, BMS-WebView-2, BMS-POS datasets.
In the ﬁgure, we can observe that LCM algorithms
outperform others in almost cases, especially forlower minimum support. In particular, LCM wasbest among seven algorithms in a wide range of minimum support from 0.1% to 0.01% on all datasets.

1 http://fimi.cs.helsinki.fi/testdata.html
2 http://www.ics.uci.edu/

Results

mlearn/MLRepository.html

3 http://www.ecn.purdue.edu/KDDCUP/

4 http://www.cs.helsinki.fi/u/goethals/software/
5 Universityof Cornell Database group, Himalaya Data
Mining Tools, http://himalaya-tools.sourceforge.net/

7㪠㪙㪤㩷㪫㪈㪇㪠㪋㪛㪈㪇㪇㪢㪠㪙㪤㩷㪫㪋㪇㪠㪈㪇㪛㪈㪇㪇㪢

㪈㪇㪇㪇

㪈㪇㪇㪇
㪣㪚㪤㪽㫉㪼㫈
㪣㪚㪤㪣㪚㪤㫄㪸㫏
㪽㫇㪾㫉㫆㫎㫋㪿
㪽㫇㪶㪼㪺㫃㪸㫋
㪽㫇㪶㪸㫇㫉㫀㫆㫉㫀㫄㪸㪽㫀㪸㪶㪽㫀
㫄㪸㪽㫀㪸㪶㪽㪺㫀㫄㪸㪽㫀㪸㪶㫄㪽㫀

㪀 㪈㪇㪇
㪺
㪼
㫊
㩿㩷
㪼
㫄
㫀
㫋

㪈㪇

㪈

㪇㪅㪈㪌

㪇㪅㪈㪊

㪇㪅㪈

㪇㪅㪇㪏

㪇㪅㪇㪌

㪇㪅㪇㪊

㪈

㪈㪇
㪈

㪇㪅㪇㪏

㪇㪅㪇㪍

㪇㪅㪇㪋

㪇㪅㪇㪉

㪀
㪺
㪼
㩿㫊
㩷
㪼
㫀㫄
㫋

㪇㪅㪌

㫄㫀㫅㫊㫌㫇㩷㩿㩼㪀㪙㪤㪪㪄㪮㪼㪹㪭㫀㪼㫎㪄㪉㪣㪚㪤㪽㫉㪼㫈
㪣㪚㪤㪣㪚㪤㫄㪸㫏
㪽㫇㪾㫉㫆㫎㫋㪿
㪽㫇㪶㪼㪺㫃㪸㫋
㪽㫇㪶㪸㫇㫉㫀㫆㫉㫀㫄㪸㪽㫀㪸㪶㪽㫀
㫄㪸㪽㫀㪸㪶㫄㪽㫀

㪈㪇
㪈
㪇㪅㪈

㫄㫀㫅㫊㫌㫇㩷㩿㩼㪀

㪇㪅㪇㪈

㪈

㪈㪇㪇

㪣㪚㪤㪽㫉㪼㫈
㪣㪚㪤㪣㪚㪤㫄㪸㫏
㪽㫇㪾㫉㫆㫎㫋㪿
㪽㫇㪶㪼㪺㫃㪸㫋
㪽㫇㪶㪸㫇㫉㫀㫆㫉㫀㫄㪸㪽㫀㪸㪶㪽㫀
㫄㪸㪽㫀㪸㪶㫄㪽㫀

㪇㪅㪈

㪈㪅㪌

㪈㪇㪇㪇

㪈㪇㪇

㪇㪅㪈

㪉

Figure 5: Running time of the algorithms on IBMArtiﬁcial T40I10D100K

㪙㪤㪪㪄㪮㪼㪹㪭㫀㪼㫎㪄㪈

㪈㪇㪇㪇

㪀
㪺
㪼
㩿㫊
㩷
㪼
㫀㫄
㫋

㪈㪇

㫄㫀㫅㫊㫌㫇㩷㩿㩼㪀

Figure 4: Running time of the algorithms on IBMArtiﬁcial T10I40D100K

㪣㪚㪤㪽㫉㪼㫈
㪣㪚㪤㪣㪚㪤㫄㪸㫏
㪽㫇㪾㫉㫆㫎㫋㪿
㪽㫇㪶㪼㪺㫃㪸㫋
㪽㫇㪶㪸㫇㫉㫀㫆㫉㫀㫄㪸㪽㫀㪸㪶㪽㫀
㫄㪸㪽㫀㪸㪶㪽㪺㫀㫄㪸㪽㫀㪸㪶㫄㪽㫀

㪀 㪈㪇㪇
㪺
㪼
㫊
㩿㩷
㪼
㫄
㫀
㫋

㪇㪅㪈

㪇㪅㪇㪏

㪇㪅㪇㪍

㪇㪅㪇㪋

㪇㪅㪇㪉

㪇㪅㪇㪈

㫄㫀㫅㫊㫌㫇㩷㩿㩼㪀

Figure 6: Running time of the algorithms on BMS- Figure 7: Running time of the algorithms on BMSWebView-1
WebView-2

㪙㪤㪪㪄㪧㪦㪪

㪈㪇㪇㪇㪇
㪈㪇㪇㪇
㪀
㪺
㪼
㫊
㩿㩷
㪼
㫀㫄
㫋

㪣㪚㪤㪽㫉㪼㫈
㪣㪚㪤㪣㪚㪤㫄㪸㫏
㪽㫇㪾㫉㫆㫎㫋㪿
㪽㫇㪶㪼㪺㫃㪸㫋
㪽㫇㪶㪸㫇㫉㫀㫆㫉㫀㫄㪸㪽㫀㪸㪶㪽㫀
㫄㪸㪽㫀㪸㪶㫄㪽㫀

㪈㪇㪇
㪈㪇
㪈

2, BMS-POS datasets. LCMfreq works quite wellfor higher minimum support, but takes more than 30
minutes for minimum support above 0.04% on BMSWeb-View-1. In these cases, the number of frequent
item sets is quite large, over 100,000,000,000. Interestingly, Maﬁa-mﬁ’s performance is stable in a wide
range of minimum support from 0.1% to 0.01%.
In summary, LCM family algorithms signiﬁcantly
perform well on real world datasets BMS-WebView1, BMS-WebView-2, BMS-POS datasets.

㪇㪅㪈

㪇㪅㪇㪏

㪇㪅㪇㪍

㪇㪅㪇㪋

㪇㪅㪇㪉

㪇㪅㪇㪈

㫄㫀㫅㫊㫌㫇㩷㩿㩼㪀

Figure 8: Running time of the algorithms on
BMS-POS

Results on UCI-ML repository and PUMSB
datasets

For higher minimum support ranging from 0.1% to
0.06%, the performances of all algorithms are similar,and LCM families have slightly better performance.
For lower minimum support ranging from 0.04% to0.01%, Eclat and Apriori are much slower than every
other algorithms. LCM outperforms others. Somefrequent item set miners such as Maﬁa-ﬁ, and Maﬁafci runs out of 1GB of main memory for these minimum supports on BMS-WebView-1, BMS-WebView-

Figures 9 through Figure 12 show the running
time on middle sized data sets pumsb and pumsb*,
kosarak and small sized datasets connect, chess,and mushroom. These datasets taken from machinelearning domains are small but hard datasets for frequent pattern mining task since they have many frequent patterns even with high minimum supports,e.g., from 50% to 90%. These datasets are originallybuild for classiﬁcation task and have slightly diﬀerent characteristics than large business datasets such8㫇㫌㫄㫊㪹

㪈㪇㪇㪇
㪈㪇㪇
㪀
㪺
㪼
㫊
㩿㩷
㪼
㫄
㫀
㫋

㪈㪇㪇㪇

㪣㪚㪤㪽㫉㪼㫈
㪣㪚㪤㪣㪚㪤㫄㪸㫏
㪽㫇㪾㫉㫆㫎㫋㪿
㪽㫇㪶㪼㪺㫃㪸㫋
㪽㫇㪶㪸㫇㫉㫀㫆㫉㫀㫄㪸㪽㫀㪸㪶㪽㫀
㫄㪸㪽㫀㪸㪶㫄㪽㫀

㪈㪇
㪈
㪇㪅㪈

㪐㪌

㪐㪇

㪏㪌

㪏㪇

㪎㪌

㪎㪇

㪍㪌

㪍㪇

㪀
㪺
㪼
㫊
㩿㩷
㪼
㫄
㫀
㫋

㪣㪚㪤㪽㫉㪼㫈
㪣㪚㪤㪣㪚㪤㫄㪸㫏
㪽㫇㪾㫉㫆㫎㫋㪿
㪽㫇㪶㪼㪺㫃㪸㫋
㪽㫇㪶㪸㫇㫉㫀㫆㫉㫀㫄㪸㪽㫀㪸㪶㪽㫀
㫄㪸㪽㫀㪸㪶㫄㪽㫀

㪈㪇㪇
㪈㪇
㪈
㪇㪅㪈

㫄㫀㫅㫊㫌㫇㩷㩿㩼㪀

Figure 9: Running time of the algorithms on pumsb

㪌㪇

㪊㪌

㪊㪇

㪉㪌

㪉㪇

㪈㪌

㫄㫌㫊㪿㫉㫆㫆㫄

㪈㪇㪇㪇

㪈㪇㪇㪇

㪈㪇㪇

㪀 㪈㪇㪇
㪺
㪼
㩿㫊
㩷
㪼
㫀㫄
㫋

㪀
㪺
㪼
㫊
㩿㩷
㪼
㫄
㫀
㫋

㪣㪚㪤㪽㫉㪼㫈
㪣㪚㪤㪣㪚㪤㫄㪸㫏
㪽㫇㪾㫉㫆㫎㫋㪿
㪽㫇㪶㪼㪺㫃㪸㫋
㪽㫇㪶㪸㫇㫉㫀㫆㫉㫀

㪈㪇

㪇㪅㪉㪌

㪇㪅㪉

㪇㪅㪈㪌

㪇㪅㪈

㪣㪚㪤㪽㫉㪼㫈
㪣㪚㪤㪣㪚㪤㫄㪸㫏
㪽㫇㪾㫉㫆㫎㫋㪿
㪽㫇㪶㪼㪺㫃㪸㫋
㪽㫇㪶㪸㫇㫉㫀㫆㫉㫀㫄㪸㪽㫀㪸㪶㪽㫀
㫄㪸㪽㫀㪸㪶㪽㪺㫀㫄㪸㪽㫀㪸㪶㫄㪽㫀

㪈㪇
㪈
㪇㪅㪈

㪇㪅㪇㪈
㪇㪅㪊

㫄㫀㫅㫊㫌㫇㩷㩿㩼㪀

Figure 10: Running time of the algorithms on pumsb*

㫂㫆㫊㪸㫉㪸㫂

㪈㫇㫌㫄㫊㪹㪶㫊㫋㪸㫉㪈㪇㪇㪇㪇㫄㫀㫅㫊㫌㫇㩷㩿㩼㪀

㪉㪇

㪈㪇

㪌

㪈

㪇㪅㪈

㫄㫀㫅㫊㫌㫇㩷㩿㩼㪀

Figure 12: Running time of the algorithms on mushFigure 11: Running time of the algorithms on kosarak room
closed item set in the total input size. In practice, weshow by experiments that our algorithms run fast on
several real world datasets such as BMS-WebView-1.
We also showed variants LCMfreq and LCMmax of
LCM for computing maximal and all frequent item
sets. LCMfreq uses new schemes hybrid and hypercube decomposition, and the schemes work well formany problems.

as BMS-Web-View-1 or BMS-POS.
In these ﬁgures, we see that Maﬁa-mﬁ constantly
outperforms every other maximal frequent item setsmining algorithms for wide range of minimum supports except on pumsb*. On the other hand, Apriori
is much slower than other algorithm. On the miningof all frequent item sets, LCMfreq is faster than theothers algorithms. On the mining of frequent closed
item sets, there seems to be no consistent tendency
on the performance results. However, LCM does notstore the obtained solutions in the memory, while theother algorithms do. Thus, in the sense of memorysaving, LCM has an advantage.

8

Acknowledgement
We gratefully thank to Prof. Ken Satoh of National
Institute of Informatics. This research had been supported by group research fund of National Instituteof Informatics, JAPAN.

Conclusion

In this paper, we present an eﬃcient algorithm LCM
for mining frequent closed item sets based on parentchild relationship deﬁned on frequent closed item
sets. This technique is taken from the algorithms
for enumerating maximal bipartite cliques [14, 15]
based on reverse search [3]. In theory, we demonstrate that LCM exactly enumerates the set of frequent closed item sets within polynomial time per

References[1] R. Agrawal and R. Srikant, “Fast Algorithms for
Mining Association Rules in Large Databases,”
In Proc. VLDB ’94, pp. 487–499, 1994.
[2] R. Agrawal, H. Mannila, R. Srikant, H. Toivonenand A. I. Verkamo, “Fast Discovery of Associa9㪺㫆㫅㫅㪼㪺㫋

㪈㪇㪇㪇

㪈㪇
㪈
㪇㪅㪈

㪈㪇㪇

㪣㪚㪤㪽㫉㪼㫈
㪣㪚㪤㪣㪚㪤㫄㪸㫏
㪽㫇㪾㫉㫆㫎㫋㪿
㪽㫇㪶㪼㪺㫃㪸㫋
㪽㫇㪶㪸㫇㫉㫀㫆㫉㫀㫄㪸㪽㫀㪸㪶㪽㫀
㫄㪸㪽㫀㪸㪶㪽㪺㫀㫄㪸㪽㫀㪸㪶㫄㪽㫀

㪈㪇㪇
㪀
㪺
㪼
㫊
㩿㩷
㪼
㫄
㫀
㫋

㪐㪌

㪐㪇

㪏㪇

㪎㪇

㪍㪇

㪺㪿㪼㫊㫊

㪈㪇㪇㪇

㪌㪇

㪋㪇

㪊㪇

㪀
㪺
㪼
㫊
㩿㩷
㪼
㫄
㫀
㫋

㪈
㪇㪅㪈
㪇㪅㪇㪈

㫄㫀㫅㫊㫌㫇㩷㩿㩼㪀

Figure 13: Running time of the algorithms on connect

㪈㪇

㪇㪅㪇㪇㪈

㪐㪇

㪏㪇

㪎㪇

㪍㪇

㪌㪇

㪋㪇

㪊㪇

㪣㪚㪤㪽㫉㪼㫈
㪣㪚㪤㪣㪚㪤㫄㪸㫏
㪽㫇㪾㫉㫆㫎㫋㪿
㪽㫇㪶㪼㪺㫃㪸㫋
㪽㫇㪶㪸㫇㫉㫀㫆㫉㫀㫄㪸㪽㫀㪸㪶㪽㫀
㫄㪸㪽㫀㪸㪶㪽㪺㫀㫄㪸㪽㫀㪸㪶㫄㪽㫀㫄㫀㫅㫊㫌㫇㩷㩿㩼㪀

Figure 14: Running time of the algorithms on chess[12] B. Possas, N. Ziviani, W. Meira Jr.,B. A. Ribeiro-Neto, “Set-based model: a
new approach for information retrieval,” In
Proc. SIGIR’02, pp. 230-237, 2002.

tion Rules,” In Advances in Knowledge Discovery and Data Mining, MIT Press, pp. 307–328,
1996.
[3] D. Avis and K. Fukuda, “Reverse Search for
Enumeration,” Discrete Applied Mathematics,
Vol. 65, pp. 21–46, 1996.

[13] S. Tsukiyama, M. Ide, H. Ariyoshi and I. Shirakawa, “A New Algorithm for Generating All
the Maximum Independent Sets,” SIAM Journal on Computing, Vol. 6, pp. 505–517, 1977.

[4] R. J. Bayardo Jr., Eﬃciently Mining Long Patterns from Databases, In Proc. SIGMOD’98,
pp. 85–93, 1998.

[14] Takeaki Uno, “A Practical Fast Algorithm for
Enumerating Cliques in Huge Bipartite Graphs
and Its Implementation,” 89th Special Interest
Group of Algorithms, Information Processing
Society Japan, 2003,[5] E. Boros, V. Gurvich, L. Khachiyan, andK. Makino, “On the Complexity of Generating Maximal Frequent and Minimal Infrequent
Sets,” In Proc. STACS 2002, pp. 133-141, 2002.

[15] Takeaki Uno, “Fast Algorithms for Enumerating Cliques in Huge Graphs,” Research Group ofComputation, IEICE, Kyoto University, pp.5562, 2003

[6] D. Burdick, M. Calimlim, J. Gehrke, “MAFIA:
A Maximal Frequent Itemset Algorithm forTransactional Databases,” In Proc. ICDE 2001,
pp. 443-452, 2001.

[16] Takeaki Uno, “A New Approach for Speeding Up Enumeration Algorithms,”
In
Proc. ISAAC’98, pp. 287–296, 1998.

[7] J. Han, J. Pei, Y. Yin, “Mining Frequent
Patterns without Candidate Generation,” In
Proc. SIGMOD’00, pp. 1-12, 2000

[17] M. J. Zaki, “Scalable algorithms for association mining,” Knowledge and Data Engineering,12(2), pp. 372–390, 2000.

[8] R. Kohavi, C. E. Brodley, B. Frasca, L. Mason and Z. Zheng, “KDD-Cup 2000 Organizers’
Report: Peeling the Onion,” SIGKDD Explorations, 2(2), pp. 86-98, 2000.

[18] M. J. Zaki, C. Hsiao, “CHARM: An Eﬃcient Algorithm for Closed Itemset Mining,” In
Proc. SDM’02, SIAM, pp. 457-473, 2002.

[9] H. Mannila, H. Toivonen, “Multiple Uses of Frequent Sets and Condensed Representations,” In
Proc. KDD’96, pp. 189–194, 1996.

[19] Z. Zheng, R. Kohavi and L. Mason, “Real World
Performance of Association Rule Algorithms,”
In Proc. SIGKDD-01, pp. 401-406, 2001.

[10] N. Pasquier, Y. Bastide, R. Taouil, L. Lakhal,
Discovering frequent closed itemsets for association rules, In Proc. ICDT’99, pp. 398-416, 1999.
[11] J. Pei, J. Han, R. Mao, “CLOSET: An Eﬃcient
Algorithm for Mining Frequent Closed Itemsets,” ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery
2000, pp. 21-30, 2000.
10