Scalable Algorithms for Association Mining.
AbstractAssociation rule discovery has emerged as an important problem in knowledge discovery and data mining. The association mining task consists of identifying the frequent itemsets and then, forming conditional implication rules among them. In this paper, we present efficient algorithms for the discovery of frequent itemsets which forms the compute intensive phase of the task. The algorithms utilize the structural properties of frequent itemsets to facilitate fast discovery. The items are organized into a subset lattice search space, which is decomposed into small independent chunks or sublattices, which can be solved in memory. Efficient lattice traversal techniques are presented which quickly identify all the long frequent itemsets and their subsets if required. We also present the effect of using different database layout schemes combined with the proposed decomposition and traversal techniques. We experimentally compare the new algorithms against the previous approaches, obtaining improvements of more than an order of magnitude for our test databases.
Introduction
The association mining task is to discover a set of attributes shared among a large number of objects in
a given database. For example, consider the sales database of a bookstore, where the objects represent
customers and the attributes represent books. The discovered patterns are the set of books most frequently
bought together by the customers. An example could be that, \40% of the people who buy Jane Austen's
Pride and Prejudice also buy Sense and Sensibility." The store can use this knowledge for promotions, shelf
placement, etc. There are many potential application areas for association rule technology, which include
catalog design, store layout, customer segmentation, telecommunication alarm diagnosis, and so on.
The task of discovering all frequent associations in very large databases is quite challenging. The search
space is exponential in the number of database attributes, and with millions of database objects the problem
of I/O minimization becomes paramount. However, most current approaches are iterative in nature, requiring
multiple database scans, which is clearly very expensive. Some of the methods, especially those using some
form of sampling, can be sensitive to the data-skew, which can adversely aect performance. Furthermore,
most approaches use very complicated internal data structures which have poor locality and add additional
space and computation overheads. Our goal is to overcome all of these limitations.
In this paper we present new algorithms for discovering the set of frequent attributes (also called itemsets).
The key features of our approach are as follows:
1. We use a vertical tid-list database format, where we associate with each itemset a list of transactions in
which it occurs. We show that all frequent itemsets can be enumerated via simple tid-list intersections.
2. We use a lattice-theoretic approach to decompose the original search space (lattice) into smaller pieces
(sub-lattices), which can be processed independently in main-memory. We propose two techniques for
achieving the decomposition: prex-based and maximal-clique-based partition.
3. We decouple the problem decomposition from the pattern search. We propose three new search strategies
for enumerating the frequent itemsets within each sub-lattice: bottom-up, top-down and hybrid
search.
4. Our approach roughly requires only a a few database scans, minimizing the I/O costs.
We present six new algorithms combining the features listed above, depending on the database format,
the decomposition technique, and the search procedure used. These include Eclat (Equivalence CLAss
Transformation), MaxEclat, Clique, MaxClique, TopDown, and AprClique. Our new algorithms not only
minimize I/O costs by making only a small number of database scan, but also minimize computation costs
by using ecient search schemes. The algorithms are particularly eective when the discovered frequent
itemsets are long. Our tid-list based approach is also insensitive to data-skew. In fact the MaxEclat and
MaxClique algorithms exploit the skew in tid-lists (i.e., the support of the itemsets) to reorder the search, so
that the long frequent itemsets are listed rst. Furthermore, the use of simple intersection operations makes
the new algorithms an attractive option for direct implementation in database systems, using SQL. With the
help of an extensive set of experiments, we show that the best new algorithm improves over current methods
by over an order of magnitude. At the same time, the proposed techniques retain linear scalability in the
number of transactions in the database.
The rest of this paper is organized as follows: In Section 2 we describe the association discovery problem.
We look at related work in Section 3. In section 4 we develop our lattice-based approach for problem
decomposition and pattern search. Section 5 describes our new algorithms. Some previous methods, used
for experimental comparison, are described in more detail in Section 6. An experimental study is presented
in Section 7, and we conclude in Section 8. Some mining complexity results for frequent itemsets and their
link to graph-theory are highlighted in Appendix A.
Problem Statement
The association mining task, rst introduced in [1], can be stated as follows: Let I be a set of items, and D
a database of transactions, where each transaction has a unique identier (tid) and contains a set of items.
A set of items is also called an itemset. An itemset with k items is called a k-itemset. The support of an
itemset X , denoted (X), is the number of transactions in which it occurs as a subset. A k length subset of
an itemset is called a k-subset. An itemset is maximal if it is not a subset of any other itemset. An itemset
is frequent if its support is more than a user-specied minimum support (min sup) value. The set of frequent
k-itemsets is denoted F k .
An association rule is an expression A ) B, where A and B are itemsets. The support of the rule is
given as [B), and the condence as (i.e., the conditional probability that a transaction
contains B, given that it contains A). A rule is condent if its condence is more than a user-specied
minimum condence (min conf).
The data mining task is to generate all association rules in the database, which have a support greater
than min sup, i.e., the rules are frequent. The rules must also have condence greater than min conf, i.e.,
the rules are condent. This task can be broken into two steps [2]:
1. Find all frequent itemsets. This step is computationally and I/O intensive. Given m items, there can
be potentially 2 m frequent itemsets. Ecient methods are needed to traverse this exponential itemset
search space to enumerate all the frequent itemsets. Thus frequent itemset discovery is the main focus
of this paper.
2. Generate condent rules. This step is relatively straightforward; rules of the form XnY
are generated for all frequent itemsets X , provided the rules have at least minimum condence.
Consider an example bookstore sales database shown in Figure 1. There are ve dierent items (names
of authors the bookstore carries), i.e., I = fA; C; D;T ; Wg, and the database consists of six customers who
bought books by these authors. Figure 1 shows all the frequent itemsets that are contained in at least three
customer transactions, i.e., min It also shows the set of all association rules with min conf
100%. The itemsets ACTW and CDW are the maximal frequent itemsets. Since all other frequent
Conan Doyle
Sir Arthur D
Agatha Christie C
Jane Austen A
MarkTwain T
Wodehouse
P. G. W
A C D T W
A C D W
A C T W
C D W
A C T W246
Transaction Items
ITEMS
A
A
A
A (3/3)
AT
AT
AC
W, CW
A, D, T, AC, AW
CD, CT, ACW
100%
50% (3)
Itemsets
Support
CTW,
Maximal Frequent Itemsets:
AT, DW, TW, ACT, ATW
CDW, ACTW
CDW, ACTW
ASSOCIATION RULES
ACT
A (3/3)
AT CW (3/3)

Figure

1: a) Bookstore Database, b) Frequent Itemsets and Condent Rules
itemsets are subsets of one of these two maximal itemsets, we can reduce the frequent itemset search problem
to the task of enumerating only the maximal frequent itemsets. On the other hand, for generating all the
condent rules, we need the support of all frequent itemsets. This can be easily accomplished once the
maximal elements have been identied, by making an additional database pass, and gathering the support
of all uncounted subsets.
3 Related Work
Several algorithms for mining associations have been proposed in the literature [1, 2, 6, 15, 19, 20, 21, 23,
26, 27]. The Apriori algorithm [2] is the best known previous algorithm, and it uses an ecient candidate
generation procedure, such that only the frequent itemsets at a level are used to construct candidates at the
next level. However, it requires multiple database scans, as many as the longest frequent itemset. The DHP
algorithm [23] tries to reduce the number of candidates by collecting approximate counts in the previous
level. Like Apriori it requires as many database passes as the longest itemset. The Partition algorithm [26]
minimizes I/O by scanning the database only twice. It partitions the database into small chunks which can
be handled in memory. In the rst pass it generates the set of all potentially or locally frequent itemsets,
and in the second pass it counts their global support. Partition may enumerate too many false positives in
the rst pass, i.e., itemsets locally frequent in some partition but not globally frequent. If this local frequent
set doesn't t in memory, then additional database scans will be required. The DLG [28] algorithm uses a
bit-vector per item, noting the tids where the item occurred. It generates frequent itemsets via logical AND
operations on the bit-vectors. However, DLG assumes that the bit vectors t in memory, and thus scalability
could be a problem for databases with millions of transactions. The DIC algorithm [6] dynamically counts
candidates of varying length as the database scan progresses, and thus is able to reduce the number of
scans over Apriori. Another way to minimize the I/O overhead is to work with only a small sample of the
database. An analysis of the eectiveness of sampling for association mining was presented in [29], and [27]
presents an exact algorithm that nds all rules using sampling. The AS-CPA algorithm and its sampling
versions [20] build on top of Partition and produce a much smaller set of potentially frequent candidates. It
requires at most two database scans. Approaches using only general-purpose DBMS systems and relational
algebra operations have also been studied [14, 15]. Detailed architectural alternatives in the tight-integration
of association mining with DBMS were presented in [25]. They also pointed out the benets of using the
vertical database layout.
All the above algorithms generate all possible frequent itemsets. Methods for nding the maximal elements
include All-MFS [12], which is a randomized algorithm to discover maximal frequent itemsets. The
Pincer-Search algorithm [19] not only constructs the candidates in a bottom-up manner like Apriori, but
also starts a top-down search at the same time. This can help in reducing the number of database scans.
MaxMiner [5] is another algorithm for nding the maximal elements. It uses ecient pruning techniques
to quickly narrow the search space. Our new algorithms range from those that generate all the frequent
itemsets, to hybrid schemes that generate some maximal along with the remaining itemsets. It is worth
noting that since the enumeration task is computationally challenging a number of parallel algorithms have
also been proposed [3, 7, 13, 31]
4 Itemset Enumeration: Lattice-Based Approach
Before embarking on the algorithm description, we will brie
y review some terminology from lattice theory
(see [8] for a good introduction).
Denition 1 Let P be a set. A partial order on P is a binary relation , such that for all X;Y; Z 2 P ,
the relation is:
exive: X  X.
The set P with the relation  is called an ordered set.
Denition 2 Let P be an ordered set, and let X;Z;Y 2 P . We say X is covered by Y , denoted X < Y ,
there is no element Z of P with X < Z < Y .
Denition 3 Let P be an ordered set, and let S  P . An element X 2 P is an upper bound (lower
bound) of S if s  X (s  X) for all s 2 S. The least upper bound, also called join, of S is denoted as
and the greatest lower bound, also called meet, of S is denoted as
S. The greatest element of P , denoted
>, is called the top element, and the least element of P , denoted ?, is called the bottom element.
Denition 4 Let L be an ordered set. L is called a join (meet) semilattice if X _ Y
all X;Y 2 L. L is called a lattice if it is both a join and meet semilattice, i.e., if X _ Y and exist
for all pairs of elements L. L is a complete lattice if
S and
S exist for all subsets S  L. A
set M  L is a sublattice of L if
A C D T W
CT
CD
AT
AD
ACW ADT ATW
ACDW
ACDT
ACDTW
CDT
ACT
ACD DTW
AC
ACTW
Maximal Frequent Itemsets: ACTW, CDW

Figure

2: The Complete Powerset Lattice P(I)
For set S, the ordered set P(S), the power set of S, is a complete lattice in which join and meet are given
by union and intersection, respectively:
_
i2I
i2I
The top element of P(S) is and the bottom element of P(S) is fg. For any L  P(S), L
is called a lattice of sets if it is closed under nite unions and intersections, i.e., (L; ) is a lattice with the
partial order specied by the subset relation , X _

Figure

2 shows the powerset lattice P(I) of the set of items in our example database I = fA; C; D;T ; Wg.
Also shown are the frequent (grey circles) and maximal frequent itemsets (black circles). It can be observed
that the set of all frequent itemsets forms a meet semilattice since it is closed under the meet operation,
i.e., for any frequent itemsets X , and Y , X \ Y is also frequent. On the other hand, it doesn't form a
join semilattice, since X and Y frequent, doesn't imply X [ Y is frequent. It can be mentioned that the
infrequent itemsets form a join semilattice.
subsets of a frequent itemsets are frequent.
The above lemma is a consequence of the closure under meet operation for the set of frequent itemsets.
As a corollary, we get that all supersets of an infrequent itemset are infrequent. This observation forms the
basis of a very powerful pruning strategy in a bottom-up search procedure for frequent itemsets, which has
been leveraged in many association mining algorithms [2, 23, 26]. Namely, only the itemsets found to be
frequent at the previous level need to be extended as candidates for the current level. However, the lattice
formulation makes it apparent that we need not restrict ourselves to a purely bottom-up search.
Lemma 2 The maximal frequent itemsets uniquely determine all frequent itemsets.
This observation tells us that our goal should be to devise a search procedure that quickly identies the
maximal frequent itemsets. In the following sections we will see how to do this eciently.
4.1 Support Counting
Denition 5 A lattice L is said to be distributive if for all X;Y; Z 2 L,
Denition 6 Let L be a lattice with bottom element ?. Then X 2 L is called an atom if ? < X, i.e., X
covers ?. The set of atoms of L is denoted by A(L).
Denition 7 A lattice L is called a Boolean lattice if
It is distributive.
It has > and ? elements.
Each member X of the lattice has a complement.
We begin by noting that the powerset lattice P(I) on the set of database items I is a Boolean lattice,
with the complement of X 2 L given as InX . The set of atoms of the powerset lattice corresponds to the
set of items, i.e., We associate with each atom (database item) X its tid-list, denoted L(X),
which is a list of all transaction identiers containing the atom. Figure 3 shows the tid-lists for the atoms
in our example database. For example consider atom A. Looking at the database in Figure 1, we see that
A occurs in transactions 1, 3, 4, and 5. This forms the tid-list for atom A.41 13564
A

Figure

3: Tid-List for the Atoms
Lemma 3 ([8]) For a nite boolean lattice L, with X 2 L,
In other words every element of a boolean lattice is given as a join of a subset of the set of atoms. Since the
powerset lattice P(I) is a boolean lattice, with the join operation corresponding to set union, we get
Lemma 4 For any X 2 P(I), let
The above lemma states that any itemset can be obtained is a join of some atoms of the lattice, and the
support of the itemset can be obtained by intersecting the tid-list of the atoms. We can generalize this
lemma to a set of itemsets:
Lemma 5 For any X 2 P(I), let
This lemma says that if an itemset is given as a union of a set of itemsets in J , then its support is given as
the intersection of tid-lists of elements in J . In particular we can determine the support of any k-itemset by
simply intersecting the tid-lists of any two of its (k 1) length subsets. A simple check on the cardinality
of the resulting tid-list tells us whether the new itemset is frequent or not. Figure 4 shows this process
pictorially. It shows the initial database with the tid-list for each item (i.e., the atoms). The intermediate
tid-list for CD is obtained by intersecting the lists of C and D, i.e., Similarly,
Thus, only the lexicographically rst two subsets at the previous
level are required to compute the support of an itemset at any level.41 13564
Intersect
Intersect
A C D T W
CT
CD
AT
AD
ACW ADT ATW
ACDW
ACDT
ACDTW
CDT
ACT
ACD DTW
AC
ACTW
INITIAL DATABASE
OF TID-LISTS

Figure

4: Computing Support of Itemsets via Tid-List Intersections
Lemma 6 Let X and Y be two itemsets, with X  Y . Then L(X)  L(Y ).
Proof: Follows from the denition of support.
This lemma states that if X is a subset of Y , then the cardinality of the tid-list of Y (i.e., its support)
must be less than or equal to the cardinality of the tid-list of X . A practical and important consequence
of the above lemma is that the cardinalities of intermediate tid-lists shrink as we move up the lattice. This
results in very fast intersection and support counting.
4.2 Lattice Decomposition: Prex-Based Classes
If we had enough main-memory we could enumerate all the frequent itemsets by traversing the powerset
lattice, and performing intersections to obtain itemset supports. In practice, however, we have only a limited
amount of main-memory, and all the intermediate tid-lists will not t in memory. This brings up a natural
question: can we decompose the original lattice into smaller pieces such that each portion can be solved
independently in main-memory! We address this question below.
Denition 8 Let P be a set. An equivalence relation on P is a binary relation  such that for all
the relation is:
exive: X  X.
The equivalence relation partitions the set P into disjoint subsets called equivalence classes. The equivalence
class of an element X 2 P is given as [X g.
Dene a function length prex of X . Dene
an equivalence relation  k on the lattice P(I) as follows: 8X;Y 2 P(I); X  k Y , p(X;
That is, two itemsets are in the same class if they share a common k length prex. We therefore call  k a
prex-based equivalence relation.
A C D T W
CT
CD
AT
AD
ACW ADT ATW
ACDW
ACDT
ACDTW
CDT
ACT
ACD CTW
AC
ACTW
ACDTW
ACDW
ACDT ACTW
A
AT
AD
AC
ACW ADT ATW
ACT
ACD

Figure

5: Equivalence Classes of a) P(I) Induced by  1 , and b) [A] 1 Induced by  Final Lattice of
Independent Classes
Figure 5a shows the lattice induced by the equivalence relation  1 on P(I), where we collapse all itemsets
with a common 1 length prex into an equivalence class. The resulting set or lattice of equivalence classes
is f[A]; [C]; [D]; [T ]; [W ]g.
Lemma 7 Each equivalence class [X induced by the equivalence relation  k is a sub-lattice of P(I).
Proof: Let U and V be any two elements in the class [X ], i.e., U; V share the common prex X . U _
implies that U _ V 2 [X ], and U implies that U
is a sublattice of P(I).
Each [X ] 1 is itself a boolean lattice with its own set of atoms. For example, the atoms of [A] 1 are
and the top and bottom elements are A. By the application of
Lemmas 4, and 5, we can generate all the supports of the itemsets in each class (sub-lattice) by intersecting
the tid-list of atoms or any two subsets at the previous level. If there is enough main-memory to hold
temporary tid-lists for each class, then we can solve each [X ] 1 independently. Another interesting feature
of the equivalence classes is that the links between classes denote dependencies. That is to say, if we want
to prune an itemset if there exists at least one infrequent subset (see Lemma 1), then we have to process the
classes in a specic order. In particular we have to solve the classes from bottom to top, which corresponds
to a reverse lexicographic order, i.e., we process [W ], then [T ], followed by [D], then [C], and nally [A].
This guarantees that all subset information is available for pruning.
In practice we have found that the one level decomposition induced by  1 is sucient. However, in
some cases, a class may still be too large to be solved in main-memory. In this scenario, we apply recursive
class decomposition. Let's assume that [A] is too large to t in main-memory. Since [A] is itself a boolean
lattice, it can be decomposed using  2 . Figure 5b shows the equivalence class lattice induced by applying
2 on [A], where we collapse all itemsets with a common 2 length prex into an equivalence class. The
resulting set of classes are f[AC]; [AD]; [AT ]; [AW ]g. Like before, each class can be solved independently,
and we can solve them in reverse lexicographic order to enable subset pruning. The nal set of independent
classes obtained by applying  1 on P(I) and  2 on [A] is shown in Figure 5c. As before, the links show the
pruning dependencies that exist among the classes. Depending on the amount of main-memory available
we can recursively partition large classes into smaller ones, until each class is small enough to be solved
independently in main-memory.
4.3 Search for Frequent Itemsets
In this section we discuss ecient search strategies for enumerating the frequent itemsets within each class.
The actual pseudo-code and implementation details will be discussed in Section 5.
4.3.1 Bottom-Up Search
The bottom-up search is based on a recursive decomposition of each class into smaller classes induced by
the equivalence relation  k . Figure 6 shows the decomposition of [A] 1 into smaller classes, and the resulting
lattice of equivalence classes. Also shown are the atoms within each class, from which all other elements of a
class can be determined. The equivalence class lattice can be traversed in either depth-rst or breadth-rst
manner. In this paper we will only show results for a breadth-rst traversal, i.e., we rst process the classes
followed by the classes f[ACT ]; [ACW ]; [ATW ]g, and nally [ACTW ]. For computing
the support of any itemset, we simply intersect the tid-lists of two of its subsets at the previous level. Since
the search is breadth-rst, this technique enumerates all frequent itemsets.
AC AD AT AW
ADT
ACT
ACD
ACDT ACDW ADTW
ACDTW
A
ACTW
AC AW
AT
ACTW
ACT
Equivalence Classes
Atoms in each Class

Figure

4.3.2 Top-Down Search
The top-down approach starts with the top element of the lattice. Its support is determined by intersecting
the tid-lists of the atoms. This requires a k-way intersection if the top element is a k-itemset. The advantage
of this approach is that if the maximal element is fairly large then one can quickly identify it, and one can
avoid nding the support of all its subsets. The search starts with the top element. If it is frequent we are
done. Otherwise, we check each subset at the next level. This process is repeated until we have identied
all minimal infrequent itemsets. Figure 7 depicts the top-down search. This scheme enumerates only the
maximal frequent itemsets within each sub-lattice. However, the maximal elements of a sub-lattice may
not be globally maximal. It can thus generate some non-maximal itemsets. The search starts with the top
element ACDTW . Since it is infrequent we have to check each of its four length 4 subsets. Out of these only
ACTW is frequent, so we mark all its subsets as frequent as well. We then examine the unmarked length
3 subsets of the three infrequent subsets. The search stops when AD, the minimal infrequent itemset has
been identied.
ACDT ACDW ADTW
ADT
ACW
ACT
ACD
AD
AC AT AW
A
ACDTW
ACTW
Minimal Infrequent Itemset: AD

Figure

7: Top-Down Search (gray circles represent infrequent itemsets, black circle the maximal frequent,
and white circle the minimal infrequent set)
4.3.3 Hybrid Search
The hybrid scheme is based on the intuition that the greater the support of an frequent itemset the more
likely it is to be a part of a longer frequent itemset. There are two main steps in this approach. We begin
with the set of atoms of the class sorted in descending order based on their support. The rst, hybrid
phase starts by intersecting the atoms one at a time, beginning with the atom with the highest support,
generating longer and longer frequent itemsets. The process stops when an extension becomes infrequent.
We then enter the second, bottom-up phase. The remaining atoms are combined with the atoms in the rst
set in a breadth-rst fashion described above to generate all other frequent itemsets. Figure 8 illustrates
this approach (just for this case, to better show the bottom-up phase, we have assumed that AD and ADW
are also frequent). The search starts by reordering the 2-itemsets according to support, the most frequent
rst. We combine AC and AW to obtain the frequent itemset ACW . We extend it with the next pair
AT , to get ACTW . Extension by AD fails. This concludes the hybrid phase, having found the maximal
set ACTW . In the bottom-up phase, AD is combined with all previous pairs to ensure a complete search,
producing the equivalence class [AD], which can be solved using a bottom-up search. This hybrid search
strategy requires only 2-way intersections. It enumerates the \long" maximal frequent itemsets discovered
in the hybrid phase, and also the non-maximal ones found in the bottom-up phase. Another modication
of this scheme is to recursively substitute the second bottom-up search with a hybrid search, so that mainly
the maximal frequent elements are enumerated.
ACD
AC
ACW
AW AT AD
ACDTW
ACTW
Hybrid Phase
AT AD
AC
AC AD AT AW
Pairs
Sort on Support
Phase

Figure

8: Hybrid Search
4.4 Generating Smaller Classes: Maximal Clique Approach
In this section we show how to produce smaller sub-lattices or equivalence classes compared to the pure
prex-based approach, by using additional information. Smaller sub-lattices have fewer atoms and can save
unnecessary intersections. For example, if there are k atoms, then we have to perform k
intersections for
the next level in the bottom-up approach. Fewer atoms thus lead to fewer intersections in the bottom-up
search. Fewer atoms also reduce the number of intersections in the hybrid scheme, and lead to smaller
maximum element size in the top-down search.
Denition 9 Let P be a set. A pseudo-equivalence relation on P is a binary relation  such that for
all the relation is:
exive: X  X.
The pseudo-equivalence relation partitions the set P into possibly overlapping subsets called pseudo-equivalence
classes.
Denition 10 A graph consists of a set of elements called vertices, and a set of lines connecting pairs
of vertices, called the edges. A graph is complete if there is an edge between all pairs of vertices. A
complete subgraph of a graph is called a clique.
{12, 13, 14, 15, 16, 17, 18, 23, 25, 27, 28, 34, 35, 36, 45, 46, 56, 58, 68, 78}
Frequent 2-Itemsets
Maximal Cliques
Association Graph
Maximal-Clique-Based Classes

Figure

9: Maximal Cliques of the Association Graph; Prex-Based and Maximal-Clique-Based Classes
denote the set of frequent k-itemsets. Dene an k-association graph, given as G E), with the
vertex set
Zg. Let M k denote the set of maximal cliques in G k . Figure 9 shows the association graph G 1 for the
example shown. Its maximal clique set
Dene a pseudo-equivalence relation  k on the lattice P(I) as follows: 8X;Y 2 P(I); X  k Y , 9 C 2
k such that X;Y  C and p(X; That is, two itemsets are related, i.e, they are in the same
pseudo-class, if they are subsets of the same maximal clique and they share a common prex of length k.
We therefore call  k a maximal-clique-based pseudo-equivalence relation.
Lemma 8 Each pseudo-class [X induced by the pseudo-equivalence relation  k is a sub-lattice of P(I).
Proof: Let U and V be any two elements in the class [X ], i.e., U; V share the common prex X and there
exists a maximal clique C 2 M k such that U; V  C. Clearly, U [
implies that U _ V 2 [X ], and U implies that U
Thus, each pseudo-class [X ] 1 is a boolean lattice, and the supports of all elements of the lattice can be
generated by applying Lemmas 4, and 5 on the atoms, and using any of the three search strategies described
above.
Lemma 9 Let @ k denote the set of pseudo-classes of the maximal-clique-based relation  k . Each pseudo-class
induced by the prex-based relation  k is a subset of some class [X induced by  k . Conversely,
each [X ] k , is the union of a set of pseudo-classes , given as [X
g.
Proof: Let (X) denote the neighbors of X in the graph G k . Then [X (X)gg. In
other words, [X ] consists of elements with the prex X and extended by all possible subsets of the neighbors
of X in the graph G k . Since any clique Y is a subset of fY; (Y )g, we have that [Y
a prex of X . On the other hand it is easy to show that [X
Y is a prex of Xg.
This lemma states that each pseudo-class of  k is a renement of (i.e., is smaller than) some class of  k .
By using the relation  k instead of  k , we can therefore, generate smaller sub-lattices. These sub-lattices
require less memory, and can be processed independently using any of the three search strategies described
above.

Figure

9 contrasts the classes (sub-lattices) generated by  1 and  1 . It is apparent that  1 generates
smaller classes. For example, the prex class class containing all the elements,
while the maximal-clique classes for 1568g. Each of these classes is much
smaller than the prex-based class. The smaller classes of  k come at a cost, since the enumeration of
maximal cliques can be computationally expensive. For general graphs the maximal clique decision problem
is NP-Complete [10]. However, the k-association graph is usually sparse and the maximal cliques can be
enumerated eciently. As the edge density of the association graph increases the clique based approaches
may suer.  k should thus be used only when G k is not too dense. Some of the factors aecting the edge
density include decreasing support and increasing transaction size. The eect of these parameters is studied
in the experimental section.
4.4.1 Maximal Clique Generation
We modied Bierstone's algorithm [22] for generating maximal cliques in the k-association graph. For a
class [x], and y 2 [x], y is said to cover the subset of [x], given by For each class C, we
rst identify its covering set, given as fy 2 Cjcov(y) 6= ;; and cov(y) 6 cov(z); for any z 2 C; z < yg. For
example, consider the class [1], shown in gure 9. Similarly, for our example,
since each [y]  [1]. The covering set of [1] is given by the set f2; 3; 5g. The
item 4 is not in the covering set since, is a subset of shows
the complete clique generation algorithm. Only the elements in the covering set need to be considered while
generating maximal cliques for the current class (step 3). We recursively generate the maximal cliques for
elements in the covering set for each class. Each maximal clique from the covering set is prexed with the
class identier to obtain the maximal cliques for the current class (step 7). Before inserting the new clique,
all duplicates or subsets are eliminated. If the new clique is a subset of any clique already in the maximal
list, then it is not inserted. The conditions for the above test are shown in line 8.
1:for
4: for all cliq 2 [x].CliqList do
5:
7: insert (fig [ M) in [i].CliqList such that
8:

Figure

10: The Maximal Clique Generation Algorithm
Weak Maximal Cliques For some database parameters, the edge density of the k-association graph may
be too high, resulting in large cliques with signicant overlap among them. In these cases, not only does
the clique generation take more time, but redundant frequent itemsets may also be discovered within each
sublattice. To solve this problem we introduce the notion of weak maximality of cliques. Given any two
cliques X , and Y , we say that they are -related, if jX\Y j
, i.e., the ratio of the common elements to
the distinct elements of the cliques is greater than or equal to the threshold . A weak maximal clique,
g, is generated by collapsing the two cliques into one, provided they are -related. During clique
generation only weak maximal cliques are generated for some user specied value of . Note that for
we obtain regular maximal cliques, while for we obtain a single clique. Preliminary experiments
indicate that using an appropriate value of , most of the overhead of redundant cliques can be avoided. We
found 0:5 to work well in practice.
5 Algorithm Design and Implementation
In this section we describe several new algorithms for ecient enumeration of frequent itemsets. The rst
step involves the computation of the frequent items and 2-itemsets. The next step generates the sub-lattices
(classes) by applying either the prex-based equivalence relation  1 , or the maximal-clique-based pseudo-
equivalence relation  1 on the set of frequent 2-itemsets F 2 . The sub-lattices are then processed one at a
time in reverse lexicographic order in main-memory using either bottom-up, top-down or hybrid search. We
will now describe these steps in some more detail.
5.1 Computing Frequent 1-Itemsets and 2-Itemsets
Most of the current association algorithms [2, 6, 20, 23, 26, 27] assume a horizontal database layout, such
as the one shown in Figure 1, consisting of a list of transactions, where each transaction has an identier
followed by a list of items in that transaction. In contrast our algorithms use the vertical database format,
such as the one shown in Figure 3, where we maintain a disk-based tid-list for each item. This enables us to
check support via simple tid-list intersections.
Computing F 1 Given the vertical tid-list database, all frequent items can be found in a single database
scan. For each item, we simply read its tid-list from disk into memory. We then scan the tid-list, incrementing
the item's support for each entry.
Computing F 2 Let jIj be the number of frequent items, and A the average id-list size in bytes. A
naive implementation for computing the frequent 2-itemsets requires N
id-list intersections for all pairs of
items. The amount of data read is A  N  (N 1)=2, which corresponds to around N=2 data scans. This is
clearly inecient. Instead of the naive method one could use two alternate solutions:
1. Use a preprocessing step to gather the counts of all 2-sequences above a user specied lower bound.
Since this information is invariant, it has to be computed once, and the cost can be amortized over the
number of times the data is mined.
2. Perform a vertical to horizontal transformation on-the-
y. This can be done quite easily. For each
item i, we scan its tid-list into memory. We insert item i in an array indexed by tid for each t 2 L(i).
For example, consider the id-list for item A, shown in Figure 3. We read the rst tid 1, and then
insert A in the array indexed by transaction 1. We repeat this process for all other items and their
tidlists. Figure 11 shows how the inversion process works after the addition of each item and the
complete horizontal database recovered from the vertical item tid-lists. This process entails only a
trivial amount of overhead. In fact, Partition performs the opposite inversion from horizontal to
vertical tid-list format on-the-
y, with very little cost. We also implemented appropriate memory
management by recovering only a block of database at a time, so that the recovered transactions t
in memory. Finally, we optimize the computation of F 2 by directly updating the counts of candidate
pairs in an upper triangular 2D array.
The experiments reported in Section 7 use the horizontal recovery method for computing F 2 . As we shall
demonstrate, this inversion can be done quite eciently.
Add C Add D Add W
Add T
Add A246246246
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A

Figure

11: Vertical-to-Horizontal Database Recovery
5.2 Search Implementation
Bottom-Up Search Figure 12 shows the pseudo-code for the bottom-up search. The input to the procedure
is a set of atoms of a sub-lattice S. Frequent itemsets are generated by intersecting the tid-lists of
all distinct pairs of atoms and checking the cardinality of the resulting tid-list. A recursive procedure call is
made with those itemsets found to be frequent at the current level. This process is repeated until all frequent
itemsets have been enumerated. In terms of memory management it is easy to see that we need memory to
store intermediate tid-lists for at most two consecutive levels. Once all the frequent itemsets for the next
level have been generated, the itemsets at the current level can be deleted.
for all atoms A i 2 S do
for all atoms A j 2 S, with j > i do
if (R)  min sup then

Figure

12: Pseudo-code for Bottom-Up Search
Since each sub-lattice is processed in reverse lexicographic order all subset information is available for
itemset pruning. For fast subset checking the frequent itemsets can be stored in a hash table. However, in
our experiments on synthetic data we found pruning to be of little or no benet. This is mainly because of
Lemma 6, which says that the tid-list intersection is especially ecient for large itemsets. Nevertheless, there
may be databases where pruning is crucial for performance, and we can support pruning for those datasets.
Top-Down Search The code for top-down search is given in Figure 13. The search begins with the
maximum element R of the sub-lattice S. A check is made to see if the element is already known to be
frequent. If not we perform a k-way intersection to determine its support. If it is frequent then we are done.
Otherwise, we recursively check the support of each of its (k 1)-subsets. We also maintain a hash table
HT of itemsets known to be infrequent from previous recursive calls to avoid processing sub-lattices that
have already been examined. In terms of memory management the top-down approach requires that only
the tid-lists of the atoms of a class be in memory.
if R 62 F jRj then
if (R)  min sup then
else
for all Y  R, with jY

Figure

13: Pseudo-code for Top-Down Search
Hybrid Search Figure 14 shows the pseudo-code for the hybrid search. The input consists of the atom
set S sorted in descending order of support. The maximal phase begins by intersecting atoms one at a time
until no frequent extension is possible. All the atoms involved in this phase are stored in the set S 1 . The
remaining atoms S enter the bottom-up phase. For each atom in S 2 , we intersect it with each atom
in S 1 . The frequent itemsets form the atoms of a new sub-lattice and are solved using the bottom-up search.
This process is then repeated for the other atoms of S 2 . The maximal phase requires main-memory only for
the atoms, while the bottom-up phase requires memory for at most two consecutive levels.
Hybrid(S sorted on support):
for all A i 2 S, i > 1 do /* Maximal Phase */
if (R)  min sup then
else break;
do /* Bottom-Up Phase */

Figure

14: Pseudo-code for Hybrid Search
5.3 Number of Database Scans
Before processing each sub-lattice from the initial decomposition all the relevant item tid-lists are scanned
into memory. The tid-lists for the atoms (frequent 2-itemsets) of each initial sub-lattice are constructed by
intersecting the item tid-lists. All the other frequent itemsets are enumerated by intersecting the tid-lists
of the atoms using the dierent search procedures. If all the initial classes have disjoint set of items, then
each item's tid-list is scanned from disk only once during the entire frequent itemset enumeration process
over all sub-lattices. In the general case there will be some degree of overlap of items among the dierent
sub-lattices. However only the database portion corresponding to the frequent items will need to be scanned,
which can be a lot smaller than the entire database. Furthermore, sub-lattices sharing many common items
can be processed in a batch mode to minimize disk access. Thus we claim that our algorithms will usually
require a small number of database scans after computing F 2 .
5.4 New Algorithms
The dierent algorithms that we propose are listed below. These algorithms dier in the the search strategy
used for enumeration and in the relation used for generating independent sub-lattices.
1. Eclat: It uses prex-based equivalence relation  1 along with bottom-up search. It enumerates all
frequent itemsets.
2. MaxEclat: It uses prex-based equivalence relation  1 along with hybrid search. It enumerates the
\long" maximal frequent itemsets, and some non-maximal ones.
3. Clique: It uses maximal-clique-based pseudo-equivalence relation  1 along with bottom-up search. It
enumerates all frequent itemsets.
4. MaxClique: It uses maximal-clique-based pseudo-equivalence relation  1 along with hybrid search.
It enumerates the \long" maximal frequent itemsets, and some non-maximal ones.
5. TopDown: It uses maximal-clique-based pseudo-equivalence relation  1 along with top-down search.
It enumerates only the maximal frequent itemsets. Note that for top-down search, using the larger
sub-lattices generated by  1 is not likely to be ecient.
6. AprClique: It uses maximal-clique-based pseudo-equivalence relation  1 . However, unlike the algorithms
described above, it uses horizontal data layout. It has two main steps:
possible subsets of the maximum element in each sub-lattice are generated and inserted in hash
trees [2], avoiding duplicates. There is one hash tree for each length, i.e., a k-subset is inserted in the
tree C k . An internal node of the hash tree at depth d contains a hash table whose cells point to nodes
for all sub-lattices S i induced by  1 do
for all k > 2 and k  jRj do
Insert each k-subset of R in C k ;
for all transactions t 2 D do
for all k-subsets s of t, with k > 2 and k  jtj do
Set of all frequent itemsets =

Figure

15: Pseudo-code for AprClique Algorithm
at depth d + 1. All the itemsets are stored in the leaves. The insertion procedure starts at the root,
and hashing on successive items, inserts a candidate in a leaf.
ii) The support counting step is similar to the Apriori approach. For each transaction in the database
D, we form all possible k-subsets. We then search that subset in C k and update the count if it is
found.
The database is thus scanned only once, and all frequent itemset are generated. The pseudo-code is
shown in Figure 15.
6 The Apriori and Partition Algorithms
We now discuss Apriori and Partition in some more detail, since we will experimentally compare our new
algorithms against them.
Apriori Algorithm Apriori [2] is an iterative algorithm that counts itemsets of a specic length in a given
database pass. The process starts by scanning all transactions in the database and computing the frequent
items. Next, a set of potentially frequent candidate 2-itemsets is formed from the frequent items. Another
database scan is made to obtain their supports. The frequent 2-itemsets are retained for the next pass, and
the process is repeated until all frequent itemsets have been enumerated. The complete algorithm is shown
in gure 16. We refer the reader to [2] for additional details.
There are three main steps in the algorithm:
1. Generate candidates of length k from the frequent (k 1) length itemsets, by a self join on F k 1 . For ex-
ample, if F
BCD;BCE;BDEg.
2. Prune any candidate with at least one infrequent subset. As an example, ACD will be pruned since
CD is not frequent. After pruning we get a new set C
3. Scan all transactions to obtain candidate supports. The candidates are stored in a hash tree to facilitate
fast support counting (note: the second iteration is optimized by using an array to count candidate
pairs of items, instead of storing them in a hash tree).
ffrequent 1-itemsets
for all transactions t 2 D
for all k-subsets s of t
Set of all frequent itemsets =

Figure

16: The Apriori Algorithm
Partition Algorithm Partition [26] logically divides the horizontal database into a number of non-overlapping
partitions. Each partition is read, and vertical tid-lists are formed for each item, i.e., list of all
tids where the item appears. Then all locally frequent itemsets are generated via tid-list intersections. All
locally frequent itemsets are merged and a second pass is made through all the partitions. The database is
again converted to the vertical layout and the global counts of all the chosen itemsets are obtained. The size
of a partition is chosen so that it can be accommodated in main-memory. Partition thus makes only two
database scans. The key observation used is that a globally frequent itemset must be locally frequent in at
least one partition. Thus all frequent itemsets are guaranteed to be found.
7 Experimental Results
Our experiments used a 200MHz Sun Ultra-2 workstation with 384MB main memory. We used dierent
synthetic databases that have been used as benchmark databases for many association rules algorithms
[1, 2, 6, 15, 19, 20, 23, 26, 30]. We wrote our own dataset generator, using the procedure described in [2].
Our generator produces longer frequent itemsets for the same parameters (code is available by sending email
to the author).
These datasets mimic the transactions in a retailing environment, where people tend to buy sets of items
together, the so called potential maximal frequent set. The size of the maximal elements is clustered around
a mean, with a few long itemsets. A transaction may contain one or more of such frequent sets. The
transaction size is also clustered around a mean, but a few of them may contain many items.
Let D denote the number of transactions, T the average transaction size, I the size of a maximal
potentially frequent itemset, L the number of maximal potentially frequent itemsets, and N the number of
items. The data is generated using the following procedure. We rst generate L maximal itemsets of average
size I , by choosing from the N items. We next generate D transactions of average size T by choosing from
the L maximal itemsets. We refer the reader to [4] for more detail on the database generation. In our
experiments we set are conducted on databases with dierent values
of D, T , and I . The database parameters are shown in Table 1.
Database T I D Size

Table

1: Database Parameter Settings

Figure

17 shows the number of frequent itemsets of dierent sizes for the databases used in our ex-
periments. The length of the longest frequent itemset and the total number of frequent itemsets for each
database are shown in Table 2. For example, T30:I16:D400K has a total of 13480771 frequent itemsets of
various lengths. The longest frequent itemset is of size 22 at 0.25% support!
Database Longest Freq. Itemset Number Freq. Itemsets
T30.I16.D400K (0.5% minsup) 22 13480771

Table

2: Maximum Size and Number of Frequent Sequences (0.25% Support)
Number
of
Frequent
Itemsets
Frequent Itemset Size
Min Support: 0.25%

Figure

17: Number of Frequent Itemsets of Dierent Sizes
Comparative Performance In Figure 18 and Figure 19 we compare our new algorithms against Apriori
and Partition (with 3 and 10 database partitions) for decreasing values of minimum support on the dierent
databases. As the support decreases, the size and the number of frequent itemsets increases. Apriori thus
has to make multiple passes over the database (22 passes for T30:I16:D400K), and performs poorly.
Partition performs worse than Apriori for high support, since the database is scanned only a few times
at these points. The overheads associated with inverting the database on-the-
y dominate in Partition.
However, as the support is lowered, Partition wins out over Apriori, since it only scans the database twice.
These results are in agreement with previous experiments comparing these two algorithms [26]. One problem
with Partition is that as the number of partitions increases, the number of locally frequent itemsets, which
are not globally frequent, increases (this can be reduced somewhat by randomizing the partition selection).
Partition can thus spend a lot of time in performing these redundant intersections. For example, compare
the time for Partition3 and Partition10 on all the datasets. Partition10 typically takes a factor of 1.5 to 2
times more time than Partition3. For T30:I16 (at 1% support) it takes 13 times more! Figure 20, which
shows the number of tid-list intersections for dierent algorithms on dierent datasets, makes it clear that
Partition10 is performing four to ve times more intersections than Partition3.
AprClique scans the database only once, and out-performs Apriori and Partition for higher support values
on the T10 and T20 datasets. AprClique is very sensitive to the quality of maximal cliques (sub-lattices)
that are generated. For small support, or with increasing transaction size T for xed I , the edge density of
the k-association graph increases, consequently increasing the size of the maximal cliques. AprClique doesn't
Time
(sec)
Minimum Support
Partition3
AprClique
Topdown
Eclat
Clique
MaxEclat
MaxClique40801200.25%
0.5%
0.75%
1.0%
Time
(sec)
Minimum Support
Partition3
AprClique
Topdown
Eclat
Clique
MaxEclat
MaxClique10010000
0.5%
0.75%
1.0%
Time
(sec)
Minimum Support
Partition3
AprClique
Topdown
Eclat
Clique
MaxEclat
MaxClique1000.25%
0.5%
0.75%
1.0%
Time
(sec)
Minimum Support
Partition3
AprClique
Topdown
Eclat
Clique
MaxEclat
MaxClique10010000
0.5%
0.75%
1.0%
Time
(sec)
Minimum Support
Partition3
AprClique
Topdown
Eclat
Clique
MaxEclat
MaxClique100100000.25%
0.5%
0.75%
1.0%
Time
(sec)
Minimum Support
Partition3
AprClique
Topdown
Eclat
Clique
MaxEclat
MaxClique

Figure

Total Execution Time
Time
(sec)
Minimum Support
Partition3
Eclat
Clique
MaxEclat
MaxClique

Figure

19: Total Execution Time
perform well under these conditions. TopDown usually performs better than AprClique, but shares the same
characteristics as AprClique, i.e., it is better than both Apriori and Partition for higher support values,
except for the T30 and T40 datasets. At lower support the maximum clique size, in the worst case, can
become as large as the number of frequent items, forcing TopDown to perform too many k-way intersections
to determine the minimal infrequent sets.
Eclat performs signicantly better than all these algorithms in all cases. It usually out-performs Apriori
by more than an order of magnitude, Partition3 by a factor of two, and Partition10 by a factor of four.
Eclat makes only a few database scans, requires no hash trees, and uses only simple intersection operations
to generate frequent itemsets. Further, Eclat is able to handle lower support values in dense datasets (e.g.
T20:I12 and T40:I8), where both Apriori and Partition run out of virtual memory at 0.25% support.
We now look at the comparison between the remaining four methods, which are the main contributions
of this work, i.e., between Eclat, MaxEclat, Clique and MaxClique. Clique uses the maximal-clique-based
decomposition, which generates smaller classes with fewer number of candidates. However, it performs only
slightly better than Eclat. Clique is usually 5-10% better than Eclat, since it cuts down on the number of
tidlist intersections, as shown in Figure 20. Clique performs anywhere from 2% to 46% fewer intersections
than Eclat. The dierence between these methods is not substantial, since the savings in the number of
intersections doesn't translate into a similar reduction in execution time.
The graphs for MaxEclat and MaxClique indicate that the reduction in search space by performing the
hybrid search provides signicant gains. Both the maximal clique-based strategies outperform their prex-1e+07
Number
of
Intersections
Min Support: 0.25%
Partition3
TopDown
Eclat
Clique
MaxEclat
MaxClique

Figure

20: Number of Tid-list Intersections (0.25% Support)
based counterparts. MaxClique is always better than MaxEclat due to the smaller classes. The biggest
dierence between these methods is observed for T20:I12, where MaxClique is twice as fast as MaxEclat.
An interesting result is that for T40:I8 we could not run the clique-based methods on 0.25% support, while
the prex-based methods, Eclat and MaxEclat, were able to handle this very low support value. The reason
why clique-based approaches fail is that whenever the edge density of the association graph increases, the
number and size of the cliques becomes large and there is a signicant overlap among dierent cliques. In
such cases the clique based schemes start to suer.
The best scheme for all the databases we considered is MaxClique since it benets from the smaller sublattices
and the hybrid search scheme. Figure 20 gives the number of intersections performed by MaxClique
compared against other methods. As one can see, MaxClique cuts down the candidate search space drastically,
by anywhere from a factor of 3 (for T20:I4) to 35 (for T40:I8) over Eclat. It performs the fewest intersections
of any method. In terms of raw performance MaxClique outperforms Apriori by a factor of 20-30, Partition10
by a factor of 5, and Eclat by as much as a factor of 10 on T20:I12. Furthermore, it is the only method
that was able to handle support values of 0.5% on T30:I16 (see Figure 19) where the longest frequent
itemset was of size 22. All bottom-up search methods would have to enumerate at least 2 22 subsets, while
MaxClique only performed 197601 intersections, even though there were 13480771 total frequent itemsets
(see

Table

2). MaxEclat quickly identies the 22 sized long itemset and also other long itemsets, and thus
avoids enumerating all subsets. At 0.75% support MaxClique takes 69 seconds while Apriori takes 22963
seconds, a factor of 332, while Partition10 ran out of virtual memory.
To summarize, there are several reasons why the last four algorithms outperform previous approaches:
1. They use only simple join operation on tid-lists. As the length of a frequent sequence increases, the
size of its tid-list decreases, resulting in very fast joins.
2. No complicated hash-tree structure is used, and no overhead of generating and searching of customer
subsequences is incurred. These structures typically have very poor locality [24]. On the other hand
the new algorithms have excellent locality, since a join requires only a linear scan of two lists.
3. As the minimum support is lowered, more and larger frequent sequences are found. Apriori makes
a complete dataset scan for each iteration. Eclat and the other three methods, on the other hand,
restrict themselves to usually only few scan, cutting down the I/O costs.
4. The hybrid search approaches are successful by quickly identifying long itemsets early, and are able to
avoid enumerating all subsets. For long itemsets of size 19 or 22, only the hybrid search methods are
able to run, while other methods run out of virtual memory.101000
Relative
Time
Number of Transactions
T10.I4, Min Support 0.25%
Partition
AprClique
TopDown
Eclat
Clique
MaxEclat
Relative
Time
Transaction Size
Min Support: 250
Eclat
Clique
MaxEclat
MaxClique

Figure

21: Scale-up Experiments: a) Number of Transactions, b) Transaction Size
Scalability The goal of the experiments below is to measure how the new algorithms perform as we increase
the number of transactions and average transaction size.

Figure

shows how the dierent algorithms scale up as the number of transactions increases from 100,000
to 5 million. The times are normalized against the execution time for MaxClique on 100,000 transactions. A
minimum support value of 0.25% was used. The number of partitions for Partition was varied from 1 to 50.
While all the algorithms scale linearly, our new algorithms continue to out-perform Apriori and Partition.

Figure

shows how the dierent algorithms scale with increasing transaction size. The times are
normalized against the execution time for MaxClique on transactions. Instead of a
percentage, we used an absolute support of 250. The physical size of the database was kept roughly the
same by keeping a constant T  D value. We used
The goal of this setup is to measure the eect of increasing transaction size while keeping other parameters
constant. We can see that there is a gradual increase in execution time for all algorithms with increasing
transaction size. However the new algorithms again outperform Apriori and Partition. As the transaction
size increases, the number of cliques increases, and the clique based algorithms start performing worse than
the prex-based algorithms.0.20.611.4Memory
Usage
2Mean
Time ->
Eclat

Figure

22: Eclat Memory Usage
Memory Usage Figure 22 shows the total main-memory used for the tid-lists in Eclat as the computation
of frequent itemsets progresses on T20.I6.D100K. The mean memory usage is less than 0.018MB, roughly
2% of the total database size. The gure only shows the cases where the memory usage was more than twice
the mean. The peaks in the graph are usually due to the initial construction of all the (2-itemset) atom
tid-lists within each sub-lattice. This gure conrms that the sub-lattices produced by  1 and  1 are small
enough, so that all intermediate tid-lists for a class can be kept in main-memory.
Conclusions
In this paper we presented new algorithms for ecient enumeration of frequent itemsets. We presented a
lattice-theoretic approach to partition the frequent itemset search space into small, independent sub-spaces
using either prex-based or maximal-clique-based methods. Each sub-problem can be solved in main-memory
using bottom-up, top-down, or a hybrid search procedure, and the entire process usually takes only a few
database scans.
Experimental evaluation showed that the maximal-clique-based decomposition is more precise and leads
to smaller classes. When this is combined with the hybrid search, we obtain the best algorithm MaxClique,
which outperforms current approaches by more than an order of magnitude. We further showed that the
new algorithms scale linearly in the number of transactions.



--R

Mining association rules between sets of items in large databases.
Fast discovery of association rules.
Parallel mining of association rules.
Fast algorithms for mining association rules.

Dynamic itemset counting and implication rules for market basket data.
A fast distributed algorithm for mining association rules.
Introduction to Lattices and Order.
Arboricity and bipartite subgraph listing algorithms.
Computers and Intractability: A Guide to the Theory of NP- Completeness
Data mining
Discovering all the most speci
Scalable parallel data mining for association rules.
A perspective on databases and data mining.

Generation of maximum independent sets of a bipartite graph and maximum cliques of a circular-arc graph
Interpretation on graphs and complexity characteristics of a search for speci
Some zarankiewicz numbers.
A new algorithm for discovering the maximum frequent set.
Mining association rules: Anti-skew algorithms
Fast sequential and parallel algorithms for association rule mining: A comparison.
Corrections to bierstone's algorithm for generating cliques.

Memory placement techniques for parallel association mining.
Integrating association rule mining with databases: alternatives and implications.

Sampling large databases for association rules.

Evaluation of sampling for data mining of association rules.
New algorithms for fast discovery of association rules.
Parallel algorithms for fast discovery of association rules.
--TR

--CTR
Xiu-Li Ma , Yun-Hai Tong , Shi-Wei Tang , Dong-Qing Yang, Efficient incremental maintenance of frequent patterns with FP-tree, Journal of Computer Science and Technology, v.19 n.6, p.876-884, November 2004
Zengyou He , Xiaofei Xu , Shengchun Deng, Mining top-k strongly correlated item pairs without minimum correlation threshold, International Journal of Knowledge-based and Intelligent Engineering  Systems, v.10 n.2, p.105-112, April 2006
Valerie Guralnik , George Karypis, Parallel tree-projection-based sequence mining algorithms, Parallel Computing, v.30 n.4, p.443-472, April 2004
Peiyi Tang , Li Ning , Ningning Wu, Domain and data partitioning for parallel mining of frequent closed itemsets, Proceedings of the 43rd annual southeast regional conference, March 18-20, 2005, Kennesaw, Georgia
Toon Calders , Bart Goethals , Michael Mampaey, Mining itemsets in the presence of missing values, Proceedings of the 2007 ACM symposium on Applied computing, March 11-15, 2007, Seoul, Korea
Bart Goethals, Memory issues in frequent itemset mining, Proceedings of the 2004 ACM symposium on Applied computing, March 14-17, 2004, Nicosia, Cyprus
Alexandros Nanopoulos , Apostolos N. Papadopoulos , Yannis Manolopoulos, Mining association rules in very large clustered domains, Information Systems, v.32 n.5, p.649-669, July, 2007
A Support-Ordered Trie for Fast Frequent Itemset Discovery, IEEE Transactions on Knowledge and Data Engineering, v.16 n.7, p.875-879, July 2004
Yudho Giri Sucahyo , Raj P. Gopalan, CT-ITL: efficient frequent item set mining using a compressed prefix tree with pattern growth, Proceedings of the fourteenth Australasian database conference, p.95-104, February 01, 2003, Adelaide, Australia
Raj P. Gopalan , Yudho Giri Sucahyo, Efficient mining of long frequent patterns from very large dense datasets, Design and application of hybrid intelligent systems, IOS Press, Amsterdam, The Netherlands,
Nele Dexters , Paul W. Purdom , Dirk Van Gucht, A probability analysis for candidate-based frequent itemset algorithms, Proceedings of the 2006 ACM symposium on Applied computing, April 23-27, 2006, Dijon, France
Jau-Ji Shen , Po-Wei Hsu, A robust associative watermarking technique based on similarity diagrams, Pattern Recognition, v.40 n.4, p.1355-1367, April, 2007
Jie Dong , Min Han, BitTableFI: An efficient mining frequent itemsets algorithm, Knowledge-Based Systems, v.20 n.4, p.329-335, May, 2007
Mohammad El-Hajj , Osmar R. Zaane, COFI approach for mining frequent itemsets revisited, Proceedings of the 9th ACM SIGMOD workshop on Research issues in data mining and knowledge discovery, June 13, 2004, Paris, France
Bassem Sayrafi , Dirk Van Gucht , Paul W. Purdom, On the effectiveness and efficiency of computing bounds on the support of item-sets in the frequent item-sets mining problem, Proceedings of the 1st international workshop on open source data mining: frequent pattern mining implementations, p.46-55, August 21-21, 2005, Chicago, Illinois
Son N. Nguyen , Maria E. Orlowska, A further study in the data partitioning approach for frequent itemsets mining, Proceedings of the 17th Australasian Database Conference, p.31-37, January 16-19, 2006, Hobart, Australia
Yaochun Huang , Hui Xiong , Weili Wu , Ping Deng , Zhongnan Zhang, Mining maximal hyperclique pattern: A hybrid search strategy, Information Sciences: an International Journal, v.177 n.3, p.703-721, February, 2007
Congnan Luo , Anil L. Pereira , Soon M. Chung, Distributed Mining of Maximal Frequent Itemsets on a Data Grid System, The Journal of Supercomputing, v.37 n.1, p.71-90, July      2006
Mohammed J. Zaki , Ching-Jui Hsiao, Efficient Algorithms for Mining Closed Itemsets and Their Lattice Structure, IEEE Transactions on Knowledge and Data Engineering, v.17 n.4, p.462-478, April 2005
Mohammed J. Zaki , Karam Gouda, Fast vertical mining using diffsets, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C.
Geller , Xuan Zhou , Kalpana Prathipati , Sripriya Kanigiluppai , Xiaoming Chen, Raising data for improved support in rule mining: How to raise and how far to raise, Intelligent Data Analysis, v.9 n.4, p.397-415, July 2005
Mukund Deshpande , George Karypis, Using conjunction of attribute values for classification, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA
Charu C. Aggarwal, Towards long pattern generation in dense databases, ACM SIGKDD Explorations Newsletter, v.3 n.1, July 2001
P. Valtchev , R. Missaoui , P. Lebrun, A partition-based approach towards constructing Galois (concept) lattices, Discrete Mathematics, v.256 n.3, p.801-829, 28 October 2002
Massimo Coppola , Marco Vanneschi, Parallel and distributed data mining through parallel skeletons and distributed objects, Data mining: opportunities and challenges, Idea Group Publishing, Hershey, PA,
Claudio Silvestri , Salvatore Orlando, Distributed approximate mining of frequent patterns, Proceedings of the 2005 ACM symposium on Applied computing, March 13-17, 2005, Santa Fe, New Mexico
Doug Burdick , Manuel Calimlim , Jason Flannick , Johannes Gehrke , Tomi Yiu, MAFIA: A Maximal Frequent Itemset Algorithm, IEEE Transactions on Knowledge and Data Engineering, v.17 n.11, p.1490-1504, November 2005
Bart Goethals , Mohammed J. Zaki, Advances in frequent itemset mining implementations: report on FIMI'03, ACM SIGKDD Explorations Newsletter, v.6 n.1, June 2004
R. J. Kuo , S. Y. Lin , C. W. Shih, Mining association rules through integration of clustering analysis and ant colony system for health insurance database in Taiwan, Expert Systems with Applications: An International Journal, v.33 n.3, p.794-808, October, 2007
Gosta Grahne , Jianfei Zhu, Fast Algorithms for Frequent Itemset Mining Using FP-Trees, IEEE Transactions on Knowledge and Data Engineering, v.17 n.10, p.1347-1362, October 2005
John D. Holt , Soon M. Chung, Parallel mining of association rules from text databases, The Journal of Supercomputing, v.39 n.3, p.273-299, March     2007
Toon Calders , Bart Goethals, Non-derivable itemset mining, Data Mining and Knowledge Discovery, v.14 n.1, p.171-206, February  2007
Chih-Ming Chen, Incremental personalized web page mining utilizing self-organizing HCMAC neural network, Web Intelligence and Agent System, v.2 n.1, p.21-38, August 2004
Chih-Ming Chen, Incremental personalized web page mining utilizing self-organizing HCMAC neural network, Web Intelligence and Agent System, v.2 n.1, p.21-38, January 2004
Michihiro Kuramochi , George Karypis, An Efficient Algorithm for Discovering Frequent Subgraphs, IEEE Transactions on Knowledge and Data Engineering, v.16 n.9, p.1038-1051, September 2004
Taneli Mielikinen, Frequency-based views to pattern collections, Discrete Applied Mathematics, v.154 n.7, p.1113-1139, 1 May 2006
Aaron Ceglar , John F. Roddick, Association mining, ACM Computing Surveys (CSUR), v.38 n.2, p.5-es, 2006
Mukund Deshpande , Michihiro Kuramochi , Nikil Wale , George Karypis, Frequent Substructure-Based Approaches for Classifying Chemical Compounds, IEEE Transactions on Knowledge and Data Engineering, v.17 n.8, p.1036-1050, August 2005
data mining;equivalence classes;frequent itemsets;association rules;lattices;maximal cliques