Efficient maximal frequent itemset mining by pattern-aware dynamic scheduling

While frequent pattern mining is fundamental for many data mining tasks, mining maximal frequent itemsets e±ciently is important in both theory and applications of frequent itemset mining. The fundamental challenge is how to search a large space of item combinations. Most of the existing methods search an enumeration tree of item combinations in a depth- first manner. In this thesis, we develop a new technique for more efficient maximal frequent itemset mining. Different from the classical depth-first search, our method uses a novel probing and reordering search method. It uses the patterns found so far to schedule its future search so that many search subspaces can be pruned. Three optimization techniques, namely reduced counting, pattern expansion and head growth, are developed to improve the performance. As indicated by a systematic empirical study, our new approach outperforms the currently fastest maximal frequent itemset mining algorithm FPMax* clearly.