In this paper, we revisit the frequent itemset mining (FIM) problem and focus on studying the pattern growth approach. Existing pattern growth algorithms differ in several dimensions: (1) item search order; (2) conditional database representation; (3) conditional database construction strategy; and (4) tree traversal strategy. They adopted different strategies on these dimensions. Several adaptive algorithms were proposed to try to nd good strategies for general situations. In this paper, we described the implementation techniques of an adaptive pattern growth algorithm, called AFOPT, which demonstrated good performance on all tested datasets. We also extended the algorithm to mine closed and maximal frequent itemsets. Comprehensive experiments were conducted to demonstrate the ef ciency of the proposed algorithms.
Since the frequent itemset mining problem (FIM) was
rst addressed [
Existing FIM algorithms can be classi ed into two categories: the candidate generate-and-test approach and the pattern growth approach. In each iteration of the candidate generate-and-test approach, pairs of frequent k-itemsets are joined to form candidate (k+1)-itemsets, then the database is scanned to verify their supports. The resultant frequent (k+1)-itemsets will be used as the input for next iteration. The drawbacks of this approach are: (1) it needs scan database multiple times, in worst case, equal to the maximal length of the frequent itemsets; (2) it needs generate lots of candidate itemsets, many of which are proved to be infrequent after scanning the database; and (3) subset checking is a cost operation, especially when itemsets are very long. The pattern growth approach avoids the cost of generating and testing a large number of candidate itemsets by growing a frequent itemset from its pre x. It constructs a conditional database for each frequent itemset t such that all the itemsets that have t as pre x can be mined only using the conditional database of t.
The basic operations in the pattern growth approach are counting frequent items and new conditional databases construction. Therefore, the number of conditional databases constructed during the mining process, and the mining cost of each individual conditional database have a direct effect on the performance of a pattern growth algorithm. The total number of conditional databases mainly depends on in what order the search space is explored. The traversal cost and construct cost of a conditional database depends on the size, the representation format (tree-based or array-based) and construction strategy (physical or pseudo) of the conditional database. If the conditional databases are represented by tree structure, the traversal strategy of the tree structure also matters. In this paper, we investigate various aspects of the pattern growth approach, and try to nd out what are good strategies for a pattern growth algorithm.
The rest of the paper is organized as follows: Section 2 revisits the FIM problem and introduces some related works; In Section 3, we describe an ef cient pattern growth algorithmAFOPT; Section 4 and Section 5 extend the AFOPT algorithm to mine frequent closed itemsets and maximal frequent itemsets respectively; Section 6 shows experiment results; nally, Section 7 concludes this paper. 2
In this section, we rst brie y review FIM problem and the candidate generate-and-test approach, then focus on studying the algorithmic performance space of the pattern growth approach.
Given a transactional database D, let I be the set of items
appearing in it. Any combination of the items in I can be
frequent in D, and they form the search space of FIM
problem. The search space can be represented using set
enumeration tree [
NULL{a,b,c,d,e} a b c d e ab ac ad ae bc bd be cd ce de abc abd abe acd ace ade bcd bce bde cde abcd abce abde acde
bcde abcde
Frequent itemset mining can be viewed as a set
containment join between the transactional database and the search
space of FIM. The candidate generate-and-test approach
essentially uses block nested loop join, i.e. the search space
is the inner relation and it is divided into blocks
according to itemset length. Different from simple block nested
loop join, in candidate generate-and-test approach the
output of the previous pass is used as seeds to generate next
block. For example, in the k-th pass of the Apriori
algorithm, the transaction database and the candidate k-itemsets
are joined to generate frequent k-itemsets. The frequent
kitemsets are then used to generate next blockcandidate
(k+1)-itemsets. Given the large amount of memory
available nowadays, it is a waste of memory to put only a
single length of itemsets into memory. It is desirable to fully
utilize available memory by putting some longer and
possibly frequent itemsets into memory in earlier stage to reduce
the number of database scans. The rst FIM algorithm AIS
[
The pattern growth approach adopts the divide-andconquer methodology. The search space is divided into disjoint sub search spaces. For example, the search space shown in Figure 1 can be divided into 5 disjoint sub search spaces: (1) itemsets containing a; (2) itemsets containing b but no a; (3) itemsets containing c but no a, b; (4) itemsets containing d but no a, b and c; and (5) itemsets containing only e. Accordingly, the database is divided into 5 partitions, and each partition is called a conditional database. The conditional database of item i, denoted as Di, includes all the transactions containing item i. All the items before i are eliminated from each transaction. All the frequent itemsets containing i can be mined from Di without accessing other information. Each conditional database is divided recursively following the same procedure. The pattern growth approach not only reduces the number of database scans, but also avoids the costly set-containment-test operation.
Two basic operations in pattern growth approach are counting frequent items and new conditional databases construction. Therefore, the total number of conditional databases constructed and the mining cost of each individual conditional database are key factors that affect the performance of a pattern growth algorithm. The total number of conditional databases mainly depends on in what order the search space is explored. This order is called item search order in this paper. Some structures for representing conditional databases can also help reduce the total number of conditional databases. For example, if a conditional database is represented by tree-structure and there is only one branch, then all the frequent itemsets in the conditional database can be enumerated directly from the branch. There is no need to construct new conditional databases. The mining cost of a conditional database depends on the size, the representation and construction strategy of the conditional database. The traversal strategy also matters if the conditional database is represented using a tree-structure.
Item Search Order. When we divide the search space,
all items are sorted in some order. This order is called item
search order. The sub search space of an item contains all
the items after it in item search order but no item before it.
Two item search orders were proposed in literature: static
lexicographic order and dynamic ascending frequency
order. Static lexicographic order is to order the items
lexicographically. It is a xed orderall the sub search spaces
use the same order. Tree projection algorithm [
The number of conditional databases constructed by an algorithm can differ greatly using different item search orders. Ascending frequency order is capable of minimizing the number and/or the size of conditional databases constructed in subsequent mining. Intuitively, an itemset with higher frequency will possibly have more frequent extensions than an itemset with lower frequency. We put the most infrequent item in front, though the candidate extension set is large, the frequent extension set cannot be very large. The frequencies of successive items increase, at the same time the size of candidate extension set decreases. Therefore we only need to build smaller and/or less conditional databases in subsequent mining. Table 1 shows the total number of conditional databases constructed (#cdb column), total running time and maximal memory usage when three orders are adopted in the framework of AFOPT algorithm described in this paper. The three item search orders compared are: dynamic ascending frequency order (Asc column), lexicographic order (Lex column) and dynamic descending frequency order (Des column). The minimum support threshold on each dataset is shown in the rst column. On the
rst three datasets, ascending frequency order needs to build more conditional databases than the other two orders, but its total running time and maximal memory usage is less than the other two orders. It implies that the conditional databases constructed using ascending frequency order are smaller. On the remaining datasets, ascending frequency order requires to build less conditional databases and needs less running time and maximal memory usage, especially on dense datasets connect-4 and mushroom.
Agrawal et al proposed an ef cient support counting
technique, called bucket counting, to reduce the total
number of conditional databases[
Conditional Database Representation. The
traversal and construction cost of a conditional database
heavily depends on its representation. Different data
structures have been proposed to store conditional databases, e.g.
tree-based structures such as FP-tree [
Conditional Database Construction Strategy Constructing every conditional database physically can be expensive especially when successive conditional databases do not shrink much. An alternative is to pseudo-construct them, i.e. using pointers pointing to transactions in upper level conditional databases. However, pseudo-construction cannot reduce traversal cost as effectively as physical construction. The item ascending frequency search order can make the subsequent conditional databases shrink rapidly, consequently it is bene cial to use physical construction strategy with item ascending frequency order together.
Tree Traversal Strategy The traversal cost of a tree is
minimal using top-down traversal strategy. FP-growth
algorithm [
Existing pattern growth algorithms mainly differ in the
several dimensions aforementioned. Table 2 lists existing
pattern growth algorithms and their strategies on four
dimensions. AFOPT [
We discussed several trade-offs faced by a pattern growth algorithm in last section. Some implications from above discussions are: (1) Use tree structure on dense database and use array structure on sparse database. (2) Use dynamic ascending frequency order on dense databases and/or when minimum support threshold is low. It can dramatically reduce the number and/or the size of the successive conditional databases. (3) If dynamic ascending frequency order is adopted, then use physical construction strategy because the size of conditional databases will shrink quickly. In this section, we describe our algorithm AFOPT which takes the above three implications into consideration. The distinct features of our AFOPT algorithm include: (1) It uses three different structures to represent conditional databases: arrays for sparse conditional databases, AFOPT-tree for dense conditional databases, and buckets for counting frequent itemsets containing only top-k frequent items, where k is a parameter to control the number of buckets used. Several parameters are introduced to control when to use arrays or AFOPT-tree. (2) It adopts the dynamic ascending frequency order. (3) The conditional databases are constructed physically on all levels no matter whether the conditional databases are represented by AFOPT-tree or arrays. 3.1
Given a transactional database D and a minimum support threshold, AFOPT algorithm scans the original database twice to mine all frequent itemsets. In the rst scan, all frequent items in D are counted and sorted in ascending order of their frequencies, denoted as F = fi1; i2; ; img. We perform another database scan to construct a conditional database for each ij 2 F , denoted as Dij . During the second scan, infrequent items in each transaction t are removed and the remaining items are sorted according to their orders in F . Transaction t is put into Dij if the rst item of t after sorting is ij . The remaining mining will be performed on conditional databases only. There is no need to access the original database.
We rst perform mining on Di1 to mine all the itemsets containing i1. Mining on individual conditional database follows the same process as mining on the original database. After the mining on Di1 is nished, Di1 can be discarded. Because Di1 also contains other items, the transactions in it will be inserted into the remaining conditional databases. Given a transaction t in Di1 , suppose the next item after i1 in t is ij , then t will be inserted into Dij . This step is called push-right. Sorting the items in ascending order of their frequencies ensures that every time, a small conditional database is pushed right. The pseudo-code of AFOPT-all algorithm is shown in Algorithm 1. 3.2
Algorithm 1 is independent of the representation of conditional databases. We choose proper representations ac
Input: p is a frequent itemset Dp is the conditional database of p min sup is the minimum support threshold; Description: 1: Scan Dp count frequent items, F =fi1, i2, , ing; 2: Sort items in F in ascending order of their frequencies; 3: for all item i 2 F do 4: Dp Sfig = ; 5: for all transaction t 2 Dp do 6: remove infrequent items from t, and sort remaining items according to their orders in F ; 7: let i be the rst item of t, insert t into Dp Sfig. 8: for all item i 2 F do 9: Output s = p Sfig; 10: AFOPT-all(s, Ds, min sup); 11: PushRight(Ds);
TID Transactions 1 a, b, c, f, m, p 2 a, d, e, f, g 3 a, b, f, m, n 4 a, c, e, f, m, p 5 d, f, n, p 6 a, c, h, m, p 7 a, d, m, s
TID Transactions 1 c, p, f, m, a 2 d, f, a 3 f, m, a 4 c, p, f, m, a 5 d, p, f 6 c, p, m, a 7 d, m, a header table c:3 d:3 p:4 f:5 m:5 a:6 cording to the density of conditional databases. Three structures are used: (1) array, (2) AFOPT-tree, and (3) buckets. As aforementioned, these three structures are suitable for different situations. Bucket counting technique is proper and extremely ef cient when the number of distinct frequent items is around 10. Tree structure is benecial when conditional databases are dense. Array structure is favorable when conditional databases are sparse. We use four parameters to control when to use these three structures as follows: (1) frequent itemsets containing only top-bucket size frequent items are counted using buckets; (2) if the minimum support threshold is greater than tree min sup or average support of all frequent items is no less than tree avg sup, then all the rest conditional databases are represented using AFOPT-tree; otherwise (3) the conditional databases of the next tree alphabet size most frequent items are represented using AFOPT-tree, and the rest conditional databases are represented using arrays.
Figure 2 shows a transactional database D and the initial conditional databases constructed with min sup=40%. There are 6 frequent items fc:3, d:3, p:4, f :5, m:5,a:6g. Figure 2(b) shows the projected database after removing infrequent items and sorting. The values of the parameters for conditional database construction are set as follows: bucket size=2, tree alphabet size=2, tree min sup=50%, tree avg sup=60%. The frequent itemsets containing only m and a are counted using buckets of size 4 (=2bucket size). The conditional databases of f and p are represented by AFOPT-tree. The conditional databases of item c and d are represented using arrays. From our experience, the bucket size parameter can choose a value around 10. A value between 20 and 200 will be safe for tree alphabet size parameter. We set tree min sup to 5% and tree avg sup to 10% in our experiments.
Table 3 shows the size, construction time (build column) and push-right time if applicable, of the initial structure constructed from original database by AFOPT, H-Mine and FP-growth algorithms. We set bucket size to 8 and tree alphabet size to 20 for AFOPT algorithm. The initial structure of AFOPT includes all three structures. The array structure in AFOPT algorithm simply stores all items in a transaction. Each node in hyper-structure stores three pieces of information: an item, a pointer pointing to the next item in the same transaction and a pointer pointing to the same item in another transaction. Therefore the size of hyper-structure is approximately 3 times larger than the array structure used in AFOPT. A node in AFOPT-tree maintains only a child pointer and a sibling pointer, while a FPtree node maintains two more pointers for bottom-up traversal: a parent pointer and a node link. AFOPT consumes the least amount of space on almost all tested datasets. 4
The complete set of frequent itemsets can be very large.
It has been shown that it contains many redundant
information [
Non-closed itemsets can be removed either in a
postprocessing phase, or during mining process. The second
strategy can help avoid unnecessary mining cost. Non-closed
frequent itemsets are removed based on the following two
lemmas (see [
Lemma 2 In Algorithm 1, if a frequent itemset p is not closed because condition (1) in Lemma 1 does not hold, then none of the itemsets mined from Dp can be closed.
We check whether there exists q such that p q and sup(p)=sup(q) before mining Dp. If such q exists, then there is no need to mine Dp based on Lemma 2 (line 10).
AFOPT build 0.55s 1.85s 2.11s 0.12s 0.04s 0.73s 0.08s 0.82s Thus the identi cation of a non-closed itemsets not only reduces output size, but also avoids unnecessary mining cost. Based on pruning condition (2) in Lemma 1, we can check whether an item i 2 F appears in every transaction of Dp. If such i exists, then there is no need to consider the frequent itemsets that do not contain i when mining Dp. In other words, we can directly perform mining on Dp Sfig instead of Dp (line 3-4). The efforts for mining Dp Sfjg, j 6= i are saved. The pseudo-code for mining frequent closed itemsets is shown in Algorithm 2.
Input: p is a frequent itemset Dp is the conditional database of p min sup is the minimum support threshold; Description: 1: Scan Dp count frequent items, F =fi1, i2, , ing; 2: Sort items in F in ascending order of their frequencies; 3: I = fiji 2 F and support(p Sfig) = support(p)g; 4: F = F I; p = p S I; 5: for all transaction t 2 Dp do 6: remove infrequent items from t, and sort remaining items according to their orders in F ; 7: let i be the rst item of t, insert t into Dp Sfig. 8: for all item i 2 F do 9: s = p Sfig; 10: if s is closed then 11: Output s; 12: AFOPT-close(s, Ds, min sup); 13: PushRight(Ds);
Frequent Closed Itemsets d:3, p:4, f:5, a:6 pf:3, fa:4, ma: 5 fma: 3 cpma:3 c:3 d:3 p:4 f:5 m:5 a:6 f:3
m:3 a:4 a:5 pma:3 a:3 c d p f m a
During the mining process, we store all existing frequent
closed itemsets in a tree structure, called Condensed
Frequent Pattern tree or CFP-tree for short [
CFP-tree to check whether an itemset is closed. An example of CFP-tree is shown in Figure 3(b) which stores all the frequent closed itemsets in Figure 3(a). They are mined from the database shown in Figure 2(a) with support 40%.
Each CFP-tree node is a variable-length array, and all the items in the same node are sorted in ascending order of their frequencies. A path in the tree starting from an entry in the root node represents a frequent itemset. The CFPtree has two properties: the left containment property and the Apriori property. The Apriori Property is that the support of any child of a CFP-tree entry cannot be greater than the support of that entry. The Left Containment Property is that the item of an entry E can only appear in the subtrees pointed by entries before E or in E itself. The superset of an itemset p with support s can be ef ciently searched in the CFP-tree based on these two properties. The apriori property can be exploited to prune subtrees pointed by entries with support less than s. The left containment property can be utilized to prune subtrees that do not contain all items in p. We also maintain a hash-bitmap in each entry to indicate whether an item appears in the subtree pointed by that entry to further reduce searching cost. The superset search algorithm is shown in Algorithm 3. BinarySearch(cnode, s) returns the rst entry in a CFP-tree node with support no less than s. Algorithm 3 do not require the whole CFP-tree to be in main memory because it is also very ef cient on disk. Moreover, the CFP-tree structure is a compact representation of the frequent closed itemsets, so it has a higher chance to be held in memory than at representation.
Although searching in CFP-tree is very ef cient, it is
still costly when CFP-tree is large. Inspired by the
twolayer structure adopted by CLOSET+ algorithm[
p = fi1; i2; ; ilg, p is mapped to ij :hashmap[(sup(p) min sup)%max hashmap len], j = 1; 2; ; l. An entry in a hash map records the maximal length of the itemsets mapped to it. For example, itemset fc; p; m; ag set the rst entry of c:hashmap, p:hashmap, m:hashmap and a:hashmap to 4. Figure 3(c) shows the status of the twolayer hash map before mining Df . An itemset p must be closed if any of the entry it mapped to contains a lower value than its length. In such cases there is no need to search in CFP-tree. The hash map of an item i can be released after all the frequent itemsets containing i are mined because they will not be used in later mining. For example, when mining Df , the hash map of items c, d and p can be deleted. 5
The problem of mining maximal frequent itemsets can
be viewed as given a minimum support threshold min sup,
nding a border through the search space tree such that all
the nodes below the border are infrequent and all the nodes
above the border are frequent. The goal of maximal
frequent itemsets mining is to nd the border by counting
support for as less as possible itemsets. Existing maximal
algorithms [
The most effective techniques are based on the following two lemmas to prune a whole branch from search space tree. Lemma 3 Given a frequent itemset p, if p S cand exts(p) is frequent but not maximal, then none of the frequent itemsets mined from Dp and from p's right sibling's conditional databases can be maximal because all of them are subsets of p S cand exts(p).
Lemma 4 Given a frequent itemset p, if p S f req exts(p) is frequent but not maximal, then none of the frequent itemsets mined from Dp can be maximal because all of them are subsets of p S f req exts(p).
Based on Lemma 3, before mining Dp, we can rst check whether p S cand exts(p) is frequent but not maximal. This can be done by two techniques.
Superset Pruning Technique: It is to check whether there exists some maximal frequent itemset such that it is a superset of p S cand exts(p). Like frequent closed itemset mining, subset checking can be challenging when the number of maximal itemsets is large. We will discuss this issue in next subsection.
Lookahead Technique: It is to check whether p S cand exts(p) is frequent when count frequent items in Dp. If Dp is represented by AFOPT-tree, the lookahead operation can be accomplished by simply looking at the leftmost branch of AFOPT-tree. If p S cand exts(p) is frequent, then the length of the left-most branch is equal to jcand exts(p)j, and the support of the leaf node of the leftmost branch is no less than min sup.
If the superset pruning technique and lookahead technique fail, then based on Lemma 4 we can use superset pruning technique to check whether p S f req exts(p) is frequent but not maximal. Two other techniques are adopted in our algorithm.
Excluding items appearing in every transaction of Dp from subsequent mining: Like frequent closed itemset mining, if an item i appears in every transaction of Dp, then a frequent itemset q mined from Dp and not containing i cannot be maximal because q Sfig is frequent.
Single Path Trimming: If Dp is represented by AFOPTtree and it has only one child i, then we can append i to p and remove it from subsequent mining. 5.2
When do superset prunning, to check against all
frequent maximal itemsets can be costly when the number
of maximal itemsets is large. Zaki et. al proposed a
progressive focusing technique for subset checking [
In this section, we compare the performance of our algorithms with other FIM algorithms. All the experiments were conducted on a 1Ghz Pentium III with 256MB memory running Mandrake Linux.
Table 4 shows some statistical information about the datasets used for performance study. All the datasets were downloaded from FIMI'03 workshop web site. The fth and sixth columns are maximal and average transaction length. These statistics provide some rough description of the density of the datasets.
We compared the ef ciency of AFOPT-all algorithm with Apriori, DCI, FP-growth, H-Mine and Eclat algominimum support=0.1%
AFODPCTI minimum support=0.1%
AFODPCTI 10 200 400 600 800 1000 #Transactions(x1000) (a) #Transactions 10 5 10 15 20 25 30 35 40 45 50 55
Average Transaction Length (b) AvgTransLen rithms. The Apriori and Eclat algorithms we used are implemented by Christian Borgelt. DCI was downloaded from its web site. We obtained the source code of FP-growth from its authors. H-Mine was implemented by ourselves. We ran H-Mine only on several sparse datasets since it was designed for sparse datasets and it changes to use FP-tree on dense datasets. Figure 4 shows the running time of all algorithms over datasets shown in Table 4. When the minimum support threshold is very low, an intolerable number of frequent itemsets can be generated. So when minimum support threshold reached some very low value, we turned off the output. This minimum support value is called output threshold, and they are shown on top of each gure.
With high minimum support threshold, all algorithms showed comparable performance. When minimum support threshold was lowered, the gaps between algorithms increased. The two candidate generate-and-test approaches, Apriori and DCI, showed satisfactory performance on several sparse datasets, but took thousands of seconds to terminate on dense datasets due to high cost for generating and testing a large number of candidate itemsets. HMine demonstrated similar performance with FP-growth on dataset T10I4D100k, but it was slower than FP-growth on the other three sparse datasets. H-Mine uses pseudo con)c 100 see ( iTm 10 1000 )c 100 see ( iTm 10 )c 100 see ( iTm 10 1000 )c 100 see ( iTm 10 1 struction strategy, which cannot reduce traversal cost as effective as physical construction strategy. Eclat uses vertical mining techniques. Support counting is performed ef ciently by transaction id list join. But Eclat is not scale well with respect to the number of transactions in a database. The running time of AFOPT-all was rather stable over all tested datasets, and it outperformed other algorithms.
We studied the scalability of our algorithm by perturbing the IBM synthetic data generator along two dimensions: the number of transactions was varied from 200k to 1000k and the average transaction length was varied from 10 to 50. The default values of these two parameters were set to 1000k and 40 respectively. We compared our algorithm with algorithm DCI. Other algorithms took long time to nish on large datasets, so we exclude them from comparison. Figure 5 shows the results when varying the two parameters.
We compared AFOPT-close with MAFIA [
We compared AFOPT-max with MAFIA and Apriori algorithms. The Apriori algorithm also has an option to produce only maximal frequent itemsets. It is denoted as Apriori-max in gures. Again we only compare with it on sparse datasets. Apriori-max explores the search space in breadth- rst order. It nds short frequent itemsets rst. Maximal frequent itemsets are generated in a post-processing phase. Therefore Apriori-max is infeasible when the number of frequent itemsets is large even if it adopts some pruning techniques during the mining process. AFOPT-max and MAFIA generate frequent itemsets in depth- rst order. Long frequent itemsets are mined rst. All the subsets of a long maximal frequent itemsets can be pruned from further consideration by using the superset pruning and lookahead technique. AFOPT-max uses tree structure to represent dense conditional databases. The AFOPT-tree introduces more pruning capability than tid list or tid bitmap. For example, if a conditional database can be represented by a single branch in AFOPT-tree, then the single branch will be the only one possible maximal itemset in the conditional database. AFOPT-max also bene ts from the progressive focusing technique for superset pruning. MAFIA was very ef cient on small datasets, e.g chess and mushroom when the length of bitmap is short.
In this paper, we revisited the frequent itemset mining problem and focused on investigating the algorithmic performance space of the pattern growth approach. We identi ed four dimensions in which existing pattern growth al1 0 0.02 0.04 0.06 0.08 0.1
Minimum Support(%) (a) T10I4D100k
Dataset: chess
AMFAOFPIAT--mmaaxx 0.1 0 10000 10
AMFAOFPIAT--mmaaxx (c) BMS-WebView-1
Dataset: mushroom
AMFAOFPIAT--mmaaxx 25 30 Minimum Support(%) (e) chess 10 15 20 25 30 35 40
Minimum Support(%) (f) connect-4 gorithms differ: (1) item search order: static lexicographical order or ascending frequency order; (2) conditional database representation: tree-based structure or array-based structure; (3) conditional database construction strategy: physical construction or pseudo construction; and (4) tree traversal strategy: bottom-up or top-down. Existing algorithms adopted different strategies on these four dimensions in order to reduce the total number of conditional databases and the mining cost of each individual conditional database.
we described an ef cient pattern growth algorithm AFOPT in the paper. It adaptively uses three different structures: arrays, AFOPT-tree and buckets, to represent conditional databases according to the density of a conditional database. Several parameters were introduced to control which structure should be used for a speci c conditional database. We showed that the adaptive conditional database representation strategy requires less space than using arraybased structure or tree-based structure solely. We also extended AFOPT algorithm to mine closed and maximal frequent itemsets, and described how to incorporate pruning techniques into AFOPT framework. Ef cient subset checking techniques for both closed and maximal frequent itemsets mining were presented. A set of experiments were conducted to show the ef ciency of the proposed algorithms.