LCM ver.3: Collaboration of Array, Bitmap and Prex Treefor Frequent Itemset Mining
Takeaki Uno

Masashi Kiyomi

Hiroki Arimura

National Institute of

National Institute ofInformation Science andTechnology, Hokkaido

Informatics

Informatics2­1­2, Hitotsubashi,

2­1­2, Hitotsubashi,

University

Chiyoda­ku

Chiyoda­ku

Kita 14­jo Nishi 9­chome

Tokyo, JAPAN, 101­8430

Tokyo, JAPAN, 101­8430

060­0814 Sapporo, JAPAN

uno@nii.jp

masashi@grad.nii.ac.jp

arim@ist.hokudai.ac.jp

ABSTRACTFor a transaction database, a frequent itemset is an itemset
included in at least a specified number of transactions. To
find all the frequent itemsets, the heaviest task is the computation of frequency of each candidate itemset. In the previous studies, there are roughly three data structures andalgorithms for the computation: bitmap, prefix tree, andarray lists. Each of these has its own advantage and disadvantage with respect to the density of the input database.
In this paper, we propose an efficient way to combine thesethree data structures so that in any case the combination
gives the best performance.
1.

INTRODUCTION

Frequent item set mining is one of the fundamental problems
in data mining and has many applications such as association rule mining, inductive databases, and query expansion. For these applications, fast implementations of frequent itemset mining problems are needed. In this paper
we propose a new data structure for decreasing the computational cost, and implemented it to obtain the third versions of LCM, LCMfreq, for enumerating all frequent closed
itemsets and all frequent itemsets, respectively. LCM is anabbreviation of Linear time Closed itemset Miner .
According to the computational experiments in FIMI03 andFIMI04[6], the heaviest task in the process of frequent itemset mining is the frequency counting, which is to computethe number of transactions including the candidate itemsets.
Thus, many techniques and data structures were proposed
for frequency counting. Among these, bitmap[4, 5, 10, 11],prefix tree[1, 2, 7, 8, 9, 13], and “occurrence deliver” witharray lists[14, 16] are popular (see Figure 1).
The bitmap stores the transaction database by a 01 matrix,

such that the ij element of the matrix is 1 if and only if item i
is included in jth transaction. Each cell can be represented
by 1 bit, thus we can save memory, especially in the casethat the database is dense. The itemset is also represented
by the bitmap, so that the intersection and the union of two
itemsets or transactions can be done in short time, since a
32bit CPU operates 32 bits at once. Roughly speaking, thebitmap is efficient if the input database is dense, and theminimum support is not small, i.e., larger than 5% of thenumber of transactions.
The prefix tree is a popular data structure to store stringsor sequences. It is a rooted tree such that any string (or sequence) is represented as a path from a leaf to the root, andany common prefix of two strings is the common subpath of
the representative paths of them (see Figure 1). Thus, thecommon prefixes save memory. The prefix tree is strong if
the data is structured, and the minimum support is not too
small, hence it is efficient in practice. We can also save computations for frequency counting with respect to the common prefixes. The disadvantage of the prefix tree is the highcost for its reconstruction in the recursive calls.
The occurrence deliver is a technique for efficiently computing the frequencies of many itemsets at once in short time.
In an iteration of mining algorithms, some candidate itemsets are generated, and their frequencies are computed. The
occurrence deliver stores the transaction database by array lists, and compute the frequencies by scanning the lists
once. The occurrence deliver is efficient especially for sparse
databases. With a database reduction, it is also efficient for
dense databases, but still weak for quite dense databases.
These three techniques have their own advantages, but also
have their own disadvantages. To avoid the disadvantages,
we propose a new data structure of a combination of thesethree techniques. The main part of the data structure is thearray list, but for constant number of items, we use a bitmap
and a complete prefix tree (see an example in Figure 5). The
complete prefix tree is a prefix tree including all the possible
itemsets. Mining algorithms are generally recursive, and reduce the database recursively. Thus, the reduced databases
usually include a constant number of items in the bottom
levels of the recursion. For such small databases, we can use
the efficiency of the bitmap and the prefix tree, for frequency

weight

size items

t1

1

6

b c d e g h

t2

1

6

a b c d e g

t3

1

4

b c

t4, t9

2

3

b g h

t5,t6, t8

3

5

a c e

t7

1

2

e g

b

c

d

e

c

e

f

g t ,t ,t
5 6 8

c

d

e

g

c

f

g t
2

g

h t ,t4 9array lists
with weights

g

f

f

g

transaction database
b

c

d

e

t1

b

c

d

e

d

e

a

t2 a

b

c

t3

b

c

t4

b
c

t6 a

c

t7
c
b

h

g

h

g

e

f

e

f

e

h

prefix treewith weights

b

g
g
e

g
f

g t
2

a

g
f

e

t8 a

g

g

t5 a

t9

f

h t1

g t
7

g
g

h

bitmaprepresentation
with weights

weight a

b

c

d

e

f

g

h

t1

1

0

1

1

1

1

0

1

1

t2

1

1

1

1

1

1

0

1

0

t3

1

0

1

1

0

0

1

1

0

t4, t9

2

0

1

0

0

0

0

1

1

t5,t6, t8

3

1

0

1

0

1

1

1

0

t7

1

0

0

0

0

1

0

1

0

Figure 1: Popular data structures to store transaction databases in memory
counting. Since the computation time in these bottom levels
dominates the total computation time, the increase of the
speed in the bottom levels effects drastically. The disadvantage of the prefix tree is avoided by using the complete prefix
tree by reusing the complete prefix tree in every iteration.
Moreover, many large databases are in the power law inpractice, thus only few items are included in many transactions. Our data structure compresses the part of thedatabases with respect to such items by the bitmap.
We here list up the advantages of our data structure.
· fast construction· fast frequency counting for high frequency items· fast database reduction by using the bitmap· no need of reconstruction of prefix trees· applicable to many existing algorithms
However, when the database is very sparse and the minimum
support is very small, i.e., less than 10, the computation
time is sometime slow. In these cases, the computation timeis 3 or 4 times longer than the fastest implementation in
FIMI repository. This is because of the cost for changing thestrategy. Note that in these cases the fastest implementationis the previous versions of LCM.
Our data structure can be applied to backtrack algorithms(depth-first algorithm) and also apriori type algorithms. It
can also be applied to mining algorithms for any problem;
frequent itemset mining, maximal frequent itemsets mining,
and frequent closed itemset mining. We implemented codes
for both frequent itemset mining and frequent closed itemset mining. The computational experiments shows that inalmost cases our implementation is the fastest in the implementations proposed in FIMI03 and FIMI04. A part of theresults are shown in section 4.

2.

PRELIMINARIESLet E = {1, ..., n} be the set of items. A transaction databaseon E is a set T = {T1 , . . . , Tm } such that each Ti is includedin E. Each Ti is called a transaction. We denote by ||T ||the sum of sizes of all transactions in T , that is, the sizeof database T . A set P ⊆ E is called an itemset. The
maximum element of P is called the tail of P , and denotedby tail(P ). An itemset Q is a tail extension of P if andonly if both Q \ P = {e} and e > tail(P ) hold for an iteme. An itemset P 6= ∅ is a tail extension of Q if and only
if Q = P \ tail(P ), hence Q is unique, i.e., any non-empty
itemset is a tail extension of a unique itemset.
For itemset P , a transaction including P is called an occurrence of P . The denotation of P , denoted by Occ(P ) is
the set of the occurrences of P . |Occ(P )| is called the frequency of P, and denoted by f rq(P ). In particular, for anitem e, f rq({e}) is called the frequency of e. For given constant θ, called a minimum support, itemset P is frequent if
f rq(P ) ≥ θ. If a frequent itemset P is included in no otherfrequent itemset, P is called maximal. We T
define the closureof itemset P in T , denoted by clo(P ), by T ∈Occ(P ) T . An
itemset is called closed itemset if P = clo(P ). For any twoitemsets P and Q, the following properties hold.
(1) Occ(P ∪ Q) = Occ(P ) ∩ Occ(Q)(2) If Q is a tail extension of P ,Occ(Q) = Occ(P ∪ {e}) for an item e(3) If P ⊆ Q, f rq(Q) ≤ f rq(P )(4) If Q is a tail extension of P , f rq(Q) ≤ f rq(P ).
Through this paper, let c be a given constant, which we canchoose by looking the property of the input database. For
transaction T , we call the set of items in T greater than n−cconstant suffix of T , and denote it by T s . Similarly, we call
T \ T p constant prefix of T , and denote it by T p . We recall
that n is the largest item.

a,b,c,d,etransaction database
b

c

d

e

b

c

d

e

t3

b

c

t4 a

b

a
t1
t2 a

t5 a

c

t6 a

c

d

e

d

e

d

e

d

e

a,b,c,d a,b,c,e

a,b

e

t8 a

b

t9

b

c

a,c,d,ea,b,c a,b,d a,b,e a,c,d a,c,e a,d,eet7

a,b,d,ea,ca,d a,eaeb,c,d,eb,c,d b,c,e b,d,eb,c b,d b,ec,d,ec,d c,e

b

c

d,e
d

e

Ø

- Tree structure induced by tail extensions: itemset and its extensions are connected by arrows.
- Gray itemsets are frequent when minimum support is 3: frequent itemsets are connected in the tree
- Backtrack algorithm starts from the empty set, and go up the tree in the depth-first search way
by generating tail extensions. If an extension is not frequent, then does not go up.

Figure 2: A tree induced by tail extensions: backtrack algorithm traverses the tree in a depth-first way
3.

EXISTING ALGORITHMS ANDDATASTRUCTURESIn the following subsections, we explain the popular techniques used in frequent itemset mining.
3.1

Backtrack Algorithm

Any itemset included in a frequent itemset is itself frequent.
Thereby, the property “frequent” is anti-monotone. In particular, any frequent itemset is a tail extension of a frequent
itemset. From this, we can see that any frequent itemset
can be constructed from the empty set by generating tailextensions recursively. A backtrack algorithm is a depthfirst version of this generation[3, 8, 13, 14, 15, 16].
Backtrack algorithm is based on recursive calls. An iterationof a backtrack algorithm inputs a frequent itemset P , andgenerates all tail extensions of P . Then, for each extension
being frequent, the iteration generates a recursive call withrespect to it. We describe the framework of backtrack algorithms below. Figure 2 shows an example of the executionof a backtrack algorithm.

As we can see, the heaviest part of the computation in a
backtrack algorithm is in step 3, the computation of f rq(P ∪{e}) to check whether P ∪{e} is frequent or not. We call thiscomputation frequency counting. Frequency counting can bedone by taking the intersection of T (P ) and T ({e}), however
it takes long time in a straightforward way. To reduce thecomputation time, there are many approaches; bitmap, prefix tree, occurrence deliver, and conditional database. The
conditional database is orthogonal to the others, hence we
can combine it to one of the others.
The approach of the bitmap is to use a bitmap for representing T (P ) and T ({e}). Then, we can take intersection
by binary operation “and”, thus 32 or 64 operations can bedone in one step. However, if the database is sparse and theminimum support is small, then the bitmap representation
includes so many 0’s in it, which can be omitted in the otherways.
In the following, we explain the conditional database, theprefix tree, and the occurrence deliver.
3.3

ALGORITHM Backtrack (P :itemset)
1. Output P
2. For each e ∈ E, e > tail(P ) do
3.
If P ∪ {e} is frequent then call Backtrack (P ∪ {e})We note that here an iteration of the algorithm is the computation from step 1 to 3 in a recursive call, except for thecomputation done in the recursive calls generated in step 3.
The advantage of the algorithm is that it needs no memory
for storing the frequent itemsets previously obtained, even
if the number of the frequent itemsets is huge. Since backtrack algorithms generate a number of recursive calls in an
iteration, the number of iterations at the kth level of the recursion is small if k is closed to 1, and increases exponentiallyas the increase of k. We call this property bottom-wideness.
From the bottom-wideness, we can see that the total computation time of a backtrack algorithm is dominated by thecomputation in the bottom levels of the recursion.
3.2

Frequency Counting

Conditional Database

A conditional database of an itemset P is a database usedin an iteration inputting P , and is obtained by removing
items and transactions which are not necessary in the iteration and its recursive calls. Using conditional databases
we can reduce the tail extensions to be checked, and thecomputation time for frequency counting.
For an itemset P , its conditional database, denoted by TP
is obtained from T by the following way (see Figure 3):
1. remove transactions not including P(database becomes equal to Occ(P ))2. remove items no larger than tail(P )3. remove items included in less than θ transactions of Occ(P )4. remove items e included in all transactions of Occ(P ),and record that “e is included in all transactions”
5. after removing items as 2, 3, and 4, remove duplicatedtransactions, i.e., if there are k same transactions,remove k − 1 of them, and set the weight of T to k forkeeping that there were k − 1 more transactions equal to it.

b

c

d

e

g

h

t1

b

c

d

e

g

h

d

e

g

h

t2 a

b

c

d

e

g

t1 d

e

g

h

t3

b

c

g

t2 d

e

g

t4

b

a

f

c

t6 a

c

t7

e

f

e

f

e

t8 a

c
b

e

f

f

g

h

t1

f

g

h

t2

g

f

g

t5

f

g

g

t5

e

f

g

t6

f

g

g

t6

e

f

g

t8

f

g

g

t8

e

f

g

g

t5 a

t9

f

h

t3

g
g

h

(1) original transaction database(2) conditional database of itemset {c}:choose transactions including c, andremove items preceding c (a, b and c)(3) conditional database of itemset {c,e}:choose transactions including e fromconditional database of itemset {c}, andremove items preceding e (d and e)

Figure 3: Conditional Database: example of construction
For any tail extension P ∪ {e}, Occ(P ∪ {e}) is obtained bychoosing all transactions in TP including e. The frequencyof P ∪ {e} can be computed in a similar way. Thus we cando all operations in the recursive call with respect to P onlywith the conditional database of P . As the increase of thesize of the itemset P , the size of its conditional databasedecreases exponentially. Thus the computation time for frequency counting is reduced in the bottom level. From thebottom-wideness, the total computation time for mining canalso be drastically shortened. If a transaction has no weight,
we consider the weight of the transaction is 1. Thus, throughthis paper, we assume that any transaction has a weight.
Actually, the term “conditional database” is used for manykinds of restricted databases in other papers, thus its definition is different from those in the other papers.
3.4

Prex Tree

A Prefix tree is a tree shaped data structure for storing
strings. Itemsets and transactions can be considered as
strings composed of items, thus we can use prefix trees tostore them. A vertex of the tree has an alphabet, thus a pathof the tree gives a string. Each string is represented as thepath from a representative vertex to the root. A vertex has
no two children having the same alphabet, thus the positionof the representative vertex of any string is unique. For any
two strings having a common prefix, the paths representing
them share the path corresponding to the prefix. See an
example in Figure 1. The prefix tree is sometime called frequent pattern tree, or FP-tree in short, since it is also usedin some algorithms to store the obtained frequent itemsets.
Note that we sort items in each transaction to be stored
in the order of their frequencies, so that many transactions
share prefixes with others.
To compute the occurrences and the frequency of a tail extension P ∪ {e}, we look up all vertices having e on them,and go down (opposite direction to the root) the tree fromthe vertices to find all the vertices assigned a transaction
including P . The prefix tree can be also used for storing theconditional database. In the case, any occurrence of P ∪ {e}is assigned to a descendant of a vertex having e, and viceversa. Thus, the computation can be efficiently done, andcomputation time becomes short. This technique is popular, and many recent implementations use this technique[1,2, 7, 8, 9, 13].
3.5

Occurrence Deliver

For an itemset P , the occurrence deliver computes the frequency and occurrences of all tail extensions of P at once.
The occurrence deliver stores the transaction database byarray lists. An array list is a list represented by an arraysuch that the elements of the list is stored in the array. In
an array list representation, we store each transaction of the
input database in an array list so that the items in the arrayis sorted. See an example of array lists in Figure 1. For the
initialization, the occurrence deliver assign an empty bucket
for each item. Then, the occurrence deliver scans each transaction Ti in Occ(P ), and insert Ti to the bucket of each item
included in Ti . After scanning all transactions in Occ(P ),the bucket of item e is equal to Occ(P ∪ {e}).
The occurrence deliver works in the conditional database.
The process of the occurrence deliver is equivalent to thetranspose of the matrix of the conditional database, represented by array lists. We write the pseudo code of theconditional database version of the occurrence deliver below. We can also see an example of its execution in Figure
4.
ALGORITHM OccurrenceDeliver (P :itemset,
TP :conditional database)
1. Set Bucket[e] := ∅ for each item e in TP
2. For each transaction Ti ∈ TP do
3.
For each item e ∈ Ti do
4.
Insert Ti to Bucket[e]5.
End for6. End for7. Output Bucket[e] for all items e
Lemma 1. We can get the conditional database TP ∪{e} bymerging the transactions of Bucket[e] including exactly thesame items into one, and put the weights.
Since array list is a compact form for sparse databases, theoccurrence deliver is efficient for sparse databases[14, 15, 16].
With the use of conditional databases, it is also efficient forsome dense databases, however, it takes much cost for quite
dense databases[16].
4.

NEW DATA STRUCTURE

Although the existing algorithms and data structures are
efficient, they have their own disadvantage coming from thedensity and the structure of databases. The motivation of
our new data structure is that we would have a good data

itemsitems

t1

b c d e g h

b c d e g ht2

a b c d e gt2

a b c d e g

t3

b c

t3

b c

t4, t9b g ht4, t9b g ht5,t6,t8

a c e

t5,t6,t8

a c e

t7

f

g

f

g

e g

t1

a

t1

b
c
d
e
f
g
h
(1) occurrence deliver: initial stage

t7

e g

t1

t1

f

g

f

g

t1

t1

items

items
t1

b c d e g ht1

b c d e g ht2

a b c d e gt2

a b c d e g

t3

b c

t3

b c

t4, t9b g ht4, t9b g ht5,t6,t8

a c e

t5,t6,t8

a c e

t7

t1

a
f
b
c
d
e
g
h
(2) trace t1 to insert t1 to the buckets of items in t1

f

g

f

g

t7

e g

t2

t2
t1

t2
t1

t2
t1

t2
t1

a

b

c

d

e

f

t2
t1

t1

g

h

(3) trace t2 to insert t2 to the buckets of items in t2

t5,t6,t8
t2

t4, t9t3
t2
t1

t5,t6,t8
t3
t2
t1

a

b

c

f

g

f

g

e g

t2
t1

t7
t5,t6,t8
t2
t1

d

e

t5,t6,t8
t3

t7
t5,t6,t8
t4, t9t3
t2
t1

t4, t9t1

fgh(4) after operating for all transactions, we
obtain occurrences of each tail extension

Figure 4: Occurrence deliver: example of its process
structure and a fast frequency counting algorithm by carefully combining them.
Our new data structure is very simple. When we input atransaction database, we choose a constant c. We can choosec so that the memory usage is minimal. Then, we use one
integer bit(T ) and an integer array ary(T ) of size |T p |. The
ith bit of bit(T ) is 1 if and only if T s includes item n−i, thus
bit(T ) is a bitmap representation of T s . Each item of theconstant prefix T p of T is stored in ary(T ) in the increasingorder of items, thus ary(T ) is an array list representation of
T p.
For efficient frequency counting, we have a complete prefix
tree for items greater than c. The complete prefix tree iscomposed of vertices i for 0 ≤ i < 2n−c , so that vertex icorresponds to the transactions T such that bit(T ) = i. For
each vertex i, we have two integers w(i) and h(i). w(i) is
the weight of i, and used to keep the number (the sum of
the weights) of transactions T such that bit(T ) = i. h(i)is the highest bit in i set to 1, that is, the smallest item inthe constant suffix represented by i. The parent vertex ofvertex i is the vertex i − 2h(i) , where i − 2h(i) is the number
obtained by setting h(i)th bit of i to zero. Similarly, any
child vertex j of vertex i is obtained by setting hth bit of i
to 1 for h > h(i). In contrast to the usual prefix trees, weneed neither pointers indicating the parent vertex and thechild vertices.
Further, we have a bucket for each item, which is used by theoccurrence deliver. The size of the bucket of item i is 2n−i
if i > c, and |Occ({i})| otherwise. We reuse the complete
prefix trees and the buckets in every iteration, thus we haveto allocate memory for them only once at when we input

the database.
For the memory and time efficiency, we renumber the itemsof the input database so that the items of higher frequencies have larger indices. We can see an example of how toconstruct our data structure from an array list represented
transaction database in Figure 5. Note that the items are
sorted in the order of their frequencies so that items withhigh frequencies are left (it corresponds to renumbering).
We can also see the complete prefix tree for the itemset{a, b, c, d} in Figure 6.
The size of the complete prefix tree increases exponentiallyas the increase of c, and the memory space needed by array
lists and the bitmap can decrease by the increase of c. Thus,
we choose c so that the memory use is optimal, and larger
than a specified minimum threshold such as 12, for speeding
up. The optimal c can be found in O(||T ||) time since thememory use can be computed from the frequencies of items.
If c = 12, the complete prefix tree has 4096 vertices. It is
not so large. However, if c = 32, the number of vertices
grows up to 4,000 million.
We have some motivations and ideas on the new data structure. We briefly explain them below.
1. Many datasets in the real world are in the powerlaw, thus the bitmap is efficient for and only for asmall number of items.
Roughly speaking, the bitmap is efficient if items are included in at least 1% of transactions. Under the powerlaw, databases include few, constant number of, such items.
The part with respect to such items are dense part of thedatabase, and the bitmap can compress it. For the sparsesize items

size items

size items
t1

6

b c d e g h

t1

6

g c e b h dt1

61111 h dt2

6

a b c d e gt2

6

g c e b a dt2

61111 a d

t3

4

b c

t3

4

g c b

t3

4

1101 f

t4

3

b g h

t4

3

g b h

t4

3

1001 h

t5

5

a c e

f

g

t5

5

g c e af

t5

51110 a

f

t6

5

a c e

f

g

t6

5

g c e af

t6

51110 a

f

t7

2

e g

t7

2

g e

t7

2

1010

t8

5

a c e

t8

5

g c e at8

51110 a

t9

3

b g h

t9

3

g b h

t9

3

1001 hfg

fg(1) input transaction
database as array listsff(2) sort items by # appearance

size items

f

t1

6

1111 h dt2

61111 a dt3

41101 ft4,t9

31001 ht5,t6,t8

51110 a

t7

2

1010

f

(4) merge theidentical transactions(3) represent first
C(=4) items by bitmap

Figure 5: Example of the construction of our database

c
b

d

1110

d
c

a

1100

d

c

c

d

0110
0100

d
0000

Complete prefix tree for 4 items (a,b,c,d)

0111
0101

0010

d

1011
1001

1000

d

b

1101
1010

d

1111

0011
0001

Bitmap pattern corresponding to each cell

Figure 6: The complete prefix tree: each vertex of the tree on the right-side has the bitmap pattern corresponding to the string which the vertex representing.
(non-dense) part of databases, array lists are efficient. The
prefix tree does not compress sparse databases as well as
dense databases, but takes much cost. Hence, we do not use
it for storing the transactions.

conditional database includes at most c items. Hence, we
can use the bitmap and the complete prefix tree, so that thecomputation time is reduced especially in the case that the
input database is dense.

2. For the constant number of items, the size of thecomplete prefix tree is also constant.
Under the power law, the database has few items, usuallybounded by a constant, with high frequencies. The use of theprefix tree for such items is efficient for frequency counting.
Although the number of the items in the complete prefix
tree is small, the computation time is drastically reduced
because of bottom-wideness.

5. Constructing conditional databases becomes easy
The heaviest task in the constructing conditional databases
for array lists is to find the duplicated transactions. Actually, it can be done by applying radix sort to the transactions. By using the bitmap, we can omit the computationof the radix sort for items with high frequencies. Thus, thecomputation time is reduced.

3. The complete prefix tree can be re-used.
A disadvantage of the prefix tree is that they need pointeroperations and reconstructions. The complete prefix tree
includes a vertex corresponding to any pattern composedof items larger than c, thus it needs no reconstruction, but
only initialization of accessed vertices in the previous iterations. Thus, by using the complete prefix tree and reused itagain and again in every iterations, we can avoid this disadvantage. It shortens the computation time of the iterationsin the bottom level of the recursion, especially if the input
database is dense.
4. In many iterations databases are small and dense
By sorting and re-numbering the items in the increasing order of their frequency, the computation time for frequency
counting decreases, since the sizes of the conditional databases
become smaller, more dense, and more structured on average. According to bottom-wideness, in many iterations, the4.1

Frequency Counting with Complete Prex
Tree

By using the complete prefix tree, we can get both the frequency and the conditional databases for all extensions of
the current itemset P by a sweep on the complete prefix
tree.
Suppose that we have an itemset P and want to compute thefrequencies and the conditional databases for all extensionsof P . First, we initialize the complete prefix tree and thebuckets, so that the weight of any vertex is zero and any
bucket is empty. It can be done by initializing the vertices
v with h(v) > tail(P ) of non-zero weights, and non-empty
buckets of items e > tail(P ), hence we do not need initialize
all the vertices and buckets.
After the initialization, for each transaction T in the conditional database TP , we add the weight of T to vertex bit(T ).
Then, set the weight of vertex to the sum of weights of its

1

database in
our data structure

1110
1100

bitmap weightpattern
t1

1110

t2

1010

2

t3

0111

1

t4

0101

1

t5

1111

3

1110

1101
1010

1

1111

0110
0100

1010

0010
0000

0111

0110
0100

0111

0010
0000

1101
1010

0110

1

1

bucket(0) Computing frequency and occurrences of tail extensions
by complete prefix tree: initial stage

4
4

1110

3

1010

2

4

2

0110

0100

1

0111
0101

0010
0000

0101

1

2

1

0001

0110

0111

1110

0101

0100

1010

1111

(3) Do the same for the second-rightmost column

0100

0110

0100

1

3

0101
0010

0000

1000

0110

0111

1110

0101

0100

1010

1111

1111

1

2

1011
1001

2

1

3
1111

1000
0110

1

0100

0111
0101

0010
0000

1
1

0011
0001

1000

(4) Do the same for the third-rightmost column,
then we have conditional database for each item

0101

1010

1101
1010

0011

1100

1110

1100
6

0001

0111

1110

4
4

1011

0111

0110

(2) Add weights of the cells of the rightmost column
to their parents, and insert to the buckets below

1001

1000

1

0001

1111

2

1

0011

0000

1101
1010

6

0011

1100

1110

1100

1011
1001

1000

1000

4

1111

0111

0010

(1) Write weights on the corresponding cells,
and insert bitmap patterns to buckets below

1101

1100
2

1111

1

0100

0111

1010

1011
1001

1

0001

0101

2

1000

0011

1110

1111

1100

1011

0101

0011
0001

2

3

4
1110

1001

1000

0101

3

1101

1011
1001

1000

1111

1100

6
(=6)

0110

0111

1100

1110

0101

0100

1010

1111

6
7
5
(=4+2) (=4+2+1) (=3+1+1)(5) For each item, add the weights of bitmap patterns in
its bucket, and we have frequency of each tail extension

Figure 7: Example of complete prefix tree: re-use and frequency counting
descendants, and insert each vertex i of non-zero weight tothe (n−h(i))th bucket. The former operation can be done inlinear time of |TP |. In a bottom up way, or sweep the buckets in the increasing order, the latter computation can bedone in time linear to the number of vertices with non-zeroweights.
Lemma 2. After this operation, for any i > c, the ithbucket is the bitmap representation of the conditional databaseTP ∪{i} , i.e., each vertex and its weight in ith bucket are
the bitmap representation of a transaction in TP ∪{i} and its
weight.
From the lemma, we can see that the sum of the weights ofthe vertices in the ith bucket is the frequency of P ∪ {i} for
any i > c, i 6∈ P . See an example in Figure 7.
4.2

Reuse of Complete Prex Tree

To use prefix trees and the conditional database for frequency counting, we have to construct a prefix tree for theconditional database. We avoid this construction by reusing

the complete prefix tree in every iteration, with the use of
the rightmost sweep proposed in the first version of LCM[14].
Suppose that we have an itemset P , and completed thesweep described in the previous subsection. Then, we makerecursive calls with respect to each tail extension P ∪ {e},in the decreasing order of items. In the recursive call withrespect to P ∪ {e}, the buckets of items no greater than enever be accessed. The vertices i with n − h(i) ≤ e neverbe also accessed. This shows that during the recursive call,the buckets and weights of vertices in the buckets are preserved for any item smaller than e. Therefore, we can reuse
the complete prefix trees and buckets without disturbing
the later recursive calls. This saves the memory space andcomputation time to allocate new memory space.
4.3

Prex Maintenance for Closure and Max­
imality Checking

To apply our data structure to closed itemset mining algorithms and maximal frequent itemset mining algorithms,
we have to modify the data structure so that we can compute the closure and checking the maximality in short time.
In LCM ver.2[16], we propose a technique for efficientlymaintaining the prefixes of the transactions in conditional
databases. Here the prefix of a transaction T in a conditional database TP is the set of items in T no larger thantail(P ).

number of frequent closed itemsets is very much smaller than
the number of frequent itemsets for smaller minimum supports. We call these datasets structured dense datasets. Asa representative, we show the result of chess.

Suppose that transactions T1 , · · · , Tk are merged into one
transaction T in TP . For taking closure, we put to T theintersection of the prefixes of T1 , · · · , Tk .

The fourth group is composed only of accidents, since its
density is different from any other dataset. It has huge
number of transactions, but few items. Each transaction
includes many items, so the dataset is very dense, and is
not structured so that the number of frequent itemsets andthe number of frequent closed itemsets are almost equal forany enumeratable minimum support. We call this dataset
dense dataset.

For the check of the maximality, we take union of T1 , ..., Tk ,and put it to T . We further put a weight to each item i ofthe prefix, where the weight is the number of transactions
in T1 , ..., Tk containing i. If the transactions are alreadymerged in the operations previously done, the weight of i isgiven by the sum of the weights of i over T1 , ..., Tk .
These operations can be easily treated by our new data
structure, just by doing them when we compute the frequencies and conditional databases of tail extensions in theway described in the previous subsection. Thus, our new
data structures are efficiently applicable to closed itemset
mining and maximal frequent itemset mining.

BMS-WebView2-all
BMS-WebView2-all
1000
10

COMPUTATIONAL EXPERIMENTS

In this section, we show the results of our computational
experiments. We implemented our new data structure andapply it for the second version of LCM and LCMfreq, which
are for frequent itemset mining and frequent closed itemset
mining. They are coded by ANSI C, and complied by gcc,
and the machine was a PC with Pentium4 3.20E GHz CPU
and 2GB memory. Due to the time limitation, we have no
implementation for LCMmax for maximal frequent itemset
mining. The performance of LCM algorithms are comparedwith the algorithms which marked good score on FIMI 03
or FIMI 04: fpgrowth[7], afopt[9], aim2[1], MAFIA[4, 5],
kDCI and DCI-closed[10, 11], nonodrfp[2], and PATRICIAMINE[13]. We note that aim2, nonodrfp and PATRICIAMINE are only for all frequent itemset mining.

100
cputime (sec)5.

In the following, we show the results for representatives. The
new implementation in this paper is written as “LCM3”. To
reduce the time for experiments, we stop the execution when
an implementation takes more than 10 minutes. We do notplot if the computation time is over 10 minutes, or abnormal
termination.

1

0.1
0.1
0.11
0.11 0.1
0.1 0.09
0.090.08
0.080.07
0.07 0.06
0.06 0.05
0.05 0.04
0.04 0.03
0.03 0.02 0.01
minsupminsup(%)(%)
BMS-WebView2-closed
BMS-WebView2-closed

From the performances of implementations, the instanceswere classified into four groups, in each of which the results
are similar. Due to the space limitation, we show one instance as a representative for each group.

The second group is of mushrooms, BMS-POS, kosarak,
Webdoc, and T40I10D100K. They are also sparse, but the
number of frequent itemsets is quite huge when the minimum support is very small. We call them sparse datasets.
We chose kosarak as the representative.
The third group is composed of connect, chess, pumsb, andpumsb-star. These datasets are generated in mathematicalways but are not natural data, thus they are structured.
They have many transactions but few items. Transactions
have many items, so the dataset is dense. Moreover, the

100
1000

cputime (sec)

The first group is composed of BMS-WebView1, BMS-WebView2,
T10I4D100K, and retail. These datasets have many items
and transactions but are sparse, and even if the minimum
support is very small, such as 10, the number of frequent
itemsets is not so huge, i.e., frequent itemsets are enumeratable. We call these datasets very sparse datasets. We chose
BMS-WebView2 as the representative.

1
10

afopt_allafopt_all afopt_all
fpg_all
fpg_all fpg_all
lcm_alllcm_all lcm_all
mafia_all mafia_all
dci_all dci_all
lcm3_all lcm3_all
patriciamine_all
aim2_allnonodrfp_all

10010afopt_closed
afopt_closed
fpg_closed
fpg_closed
lcm_closed
lcm_closed
mafia_closed
dci_closed
lcm3_closed

10
1
1

0.1
0.1
0.11
0.11 0.1
0.1 0.09
0.090.08
0.080.07
0.07 0.06
0.06 0.05
0.05 0.04
0.04 0.03
0.03 0.02 0.01
minsupminsup(%)(%)

kosarak-all
kosarak-all
kosarak-all

100
100
10
10

chess-closed
chess-closed
1000
1000

afopt_allafopt_allafopt_all afopt_all
fpg_all
fpg_all fpg_all
lcm_alllcm_all lcm_all
mafia_allmafia_all mafia_all
dci_all dci_all
lcm3_all lcm3_all
patriciamine_all
aim2_allnonodrfp_all

100100
cputime (sec)cputime (sec)

10
100
1000

10
1

10
10
1

afopt_closed
afopt_closed
fpg_closed
fpg_closed
lcm_closed
lcm_closed
mafia_closed
mafia_closed
dci_closed
dci_closed
lcm3_closed

1
0.1
0.1
0.01

10.1
11
111

0.9
0.9
0.9 0.8
0.8 0.8
0.7
0.7 0.6
0.6
0.7 0.5
0.5 0.6
0.4
0.4
minsupminsupminsup(%)
(%)
(%)

0.3
0.30.50.2

0.01
0.001
90
90

0.4
0.1

80
80

70
7070

kosarak-closed
kosarak-closed
kosarak-closed

100

40
30

30
20

30
30

20

10

6060 50 50 40 4030
minsupminsup(%)
(%)

30
20

20
10

accidents-all
accidents-all
100
1000

afopt_closed
afopt_closed
afopt_closed
fpg_closed
fpg_closed
lcm_closed
lcm_closed
mafia_closed
dci_closed
lcm3_closed

cputime (sec)cputime (sec)

10
100
1000

60
60 60 50
50 5040
40
minsupminsup(%)
(%)

10
10

100
10
10
10

afopt_allafopt_all afopt_all
fpg_all
fpg_all fpg_all
lcm_alllcm_all lcm_all
mafia_all mafia_all
dci_all dci_all
lcm3_all lcm3_all
patriciamine_all
aim2_allnonodrfp_all

1
1

111
111

0.9
0.9
0.9 0.8
0.8 0.8
0.7
0.7 0.6
0.6
0.7 0.5
0.5 0.6
0.4
0.4
minsupminsupminsup(%)
(%)
(%)

0.3
0.30.50.2

0.1
0.1
1
90
90

0.4
0.1

80
80

70
70

chess-allchess-all

100
100
10
10
10
11
1
0.1
0.1
0.1
0.01
0.01
0.001
90
90

accidents
accidents
100
1000

afopt_allafopt_all afopt_all
fpg_all
fpg_all fpg_all
lcm_alllcm_all lcm_all
mafia_allmafia_all mafia_all
dci_all
dci_all dci_all
lcm3_all lcm3_all
patriciamine_all
aim2_allnonodrfp_all

80
80

70
70

60
60
50
50
minsupminsup(%)(%)

cputime (sec)cputime (sec)

1000
100
1000

60
60 50
50
40
40
minsupminsup(%)
(%)

40
40

30

20

100
100

afopt_closed
afopt_closed
fpg_closed
lcm_closed
mafia_closed
lcm3_closed

10
10
10
1

0.1
11
90
90

80

70
70

In almost instances and minimum supports, LCM3 performs
the best. For unstructured dense datasets, and dense datasetswith large minimum supports, nonodrfp sometime outperforms LCM3. For quite small minimum supports, LCM3
algorithms are fast but not the fastest. This is because of
the cost for changing the strategy, which is from array lists
to the prefix tree. If the cost per a frequent itemset is large,i.e., iterations generates few recursive calls on average, then
LCM3 is slow. Moreover, in some sparse datasets, only few
transactions of conditional databases share prefixes on average. In such cases, frequency counting with a prefix treetakes longer time than that with array lists, hence the firstversion and the second version of LCM are fast.

[7] G. Grahne and J. Zhu, “Efficiently Using Prefix-treesin Mining Frequent Itemsets,” In Proc. IEEE
ICDM’03 Workshop FIMI’03, 2003.
For very sparse datasets, the memory usage is almost the[8] J. Han, J. Pei, Y. Yin, “Mining Frequent Patterns
same as array list, which is used in LCM ver.2. However,
without Candidate Generation,” SIGMOD Conference
for the other datasets, the memory usage decreases to half
2000, pp. 1-12, 2000
in average.
[9] Guimei Liu, Hongjun Lu, Jeffrey Xu Yu, Wang Wei,
and Xiangye Xiao, “AFOPT: An Efficient
Implementation of Pattern Growth Approach,” In
6.
CONCLUSION
Proc. IEEE ICDM’03 Workshop FIMI’03, 2003.
In this paper, we proposed a new data structure for frequent
itemset mining algorithms. We applied our data structure to[10] S. Orlando, C. Lucchese, P. Palmerini, R. Perego andthe second version of LCM algorithms, and gave implemenF. Silvestri, “kDCI: a Multi-Strategy Algorithm fortations of them. We show by computational experiments
Mining Frequent Sets,” In Proc. IEEE ICDM’03
that our implementations perform above the other impleWorkshop FIMI’03, 2003.
mentations for almost almost datasets in any minimum sup[11] C. Lucchese, S. Orlando and R. Perego, “DCI Closed:
port, except for very small minimum support. For these very
A Fast and Memory Efficient Algorithm to Mine
small minimum support, the second version of LCM is theFrequent Closed Itemsets,” In Proc. IEEE ICDM’04
fastest, thus we conclude that we can get a fast implemenWorkshop FIMI’04, 2004.
tation by a combination of the second version and the new[12] N. Pasquier, Y. Bastide, R. Taouil, L. Lakhal,
version of LCM algorithms.
Efficient Mining of Association Rules Using Closed
Itemset Lattices, Inform. Syst., 24(1), 25–46, 1999.
For very huge datasets such that 10 or 100 times larger than[13] A. Pietracaprina and D. Zandolin, “Mining Frequent
the fimi datasets, optimizing the memory usage is quite imItemsets using Patricia Tries,” In Proc. IEEE
portant. In this sense, our data structure is not the best:
ICDM’03 Workshop FIMI’03, 2003.
perhaps the combination of array list and prefix trees (pa[14] T. Uno, T. Asai, Y. Uchida, H. Arimura, “LCM: An
tricia trees[13]) might be the best. In particular, if the
Efficient Algorithm for Enumerating Frequent Closed
database is quite structured so that many transactions share
Item Sets,” In Proc. IEEE ICDM’03 Workshop
prefixes, but includes no item of a high frequency. For maxFIMI’03, 2003.
imal frequent itemsets mining and frequent closed itemset[15] T. Uno, T. Asai, Y. Uchida, H. Arimura, “An Efficientmining, if the number of output itemsets is small, then the
Algorithm for Enumerating Closed Patterns inchecking the maximality and taking closure take long time
Transaction Databases,” Lecture Notes in Artificial
rather than the way with storing all the itemsets obtained.
Intelligence 3245, pp. 16–31, 2004.
Our data structure is not weak in these cases, but the next
[16] T. Uno, M. Kiyomi, H. Arimura, “LCM ver. 2: Efficient
goal is how to perform better than others for such cases.
Mining Algorithms for Frequent/Closed/Maximal Itemsets”,
In Proc. IEEE ICDM’04 Workshop FIMI’04, 2004.
Acknowledgment

We sincerely thank to the organizers of FIMI03 and FIMI04,
and all the authors gave implementations to FIMI, especiallyfor Prof. Bart Goethals for his working for constructing andmaintaining FIMI repository. This research is supported
by Grant-in-Aid for Scientific Research of Japan and jointresearch funds of National Institute of Informatics.
7.

REFERENCES[1] A. Fiat and S. Shporer, “AIM2: Improved
implementation of AIM” In Proc. IEEE ICDM’04
Workshop FIMI’04, 2004.
[2] B. Racz, “nonordfp: An FP-growth variation without
rebuilding the FP-tree,” In Proc. IEEE ICDM’04
Workshop FIMI’04, 2004.
[3] R. J. Bayardo Jr., “Efficiently Mining Long Patterns
from Databases”, In Proc. SIGMOD’98, pp. 85–93,
1998.
[4] D. Burdick, M. Calimlim, J. Gehrke, “MAFIA: A
Maximal Frequent Itemset Algorithm forTransactional Databases,” In Proc. ICDE 2001,
pp. 443-452, 2001.
[5] D. Burdick, M. Calimlim, J. Flannick, J. Gehrke, andT. Yiu, “MAFIA: A Performance Study of Mining
Maximal Frequent Itemsets,” In Proc. IEEE ICDM’03
Workshop FIMI’03, 2003.
[6] B. Goethals, the FIMI repository,
http://fimi.cs.helsinki.fi/, 2003.