Efficiently Mining Maximal Frequent Itemsets by Item Grouping and 3-Dimensional Indexing

Efficiently Mining Maximal Frequent Itemsets by Item Grouping and 3-Dimensional Indexing

The mining of frequent itemsets has wide applications in data mining, and many methods have been proposed for this problem. However, mining the complete set of frequent itemsets often leads to a huge solution space. Fortunately, this problem can be reduced to the mining of Frequent Closed Itemsets (FCIs), which results in a much smaller solution space. Nevertheless, in some applications the number of FCIs is still too large. In such cases, the alternative is to mine the Maximal Frequent Itemsets (MFIs). In this paper, we propose a compact data structure, the Transaction Pattern List (TPL), for representing the transaction database. Efficient pruning of the search space can be accomplished with TPL. Besides, we develop the technique of item grouping to shorten the search paths and speed up the mining process. For the superset checking before generating new MFIs, we take advantage of the basic properties of itemsets to derive the three-dimensional indexing for quickly locating the set of relevant MFIs to be checked. Experimental results show that our method is more efficient than previously existing methods.