Fast algorithms for frequent itemset mining using FP-trees

Citations Over TimeTop 1% of 2005 papers

Abstract

Efficient algorithms for mining frequent itemsets are crucial for mining association rules as well as for many other data mining tasks. Methods for mining frequent itemsets have been implemented using a prefix-tree structure, known as an FP-tree, for storing compressed information about frequent itemsets. Numerous experimental results have demonstrated that these algorithms perform extremely well. In this paper, we present a novel FP-array technique that greatly reduces the need to traverse FP-trees, thus obtaining significantly improved performance for FP-tree-based algorithms. Our technique works especially well for sparse data sets. Furthermore, we present new algorithms for mining all, maximal, and closed frequent itemsets. Our algorithms use the FP-tree data structure in combination with the FP-array technique efficiently and incorporate various optimization techniques. We also present experimental results comparing our methods with existing algorithms. The results show that our methods are the fastest for many cases. Even though the algorithms consume much memory when the data sets are sparse, they are still the fastest ones when the minimum support is low. Moreover, they are always among the fastest algorithms and consume less memory than other methods when the data sets are dense.

Related Papers

• → Efficient Mining of Frequent Itemsets Using Only One Dynamic Prefix Tree(2020)17 cited
• → A Fast Algorithm for Frequent Itemset Mining Using Patricia* Structures(2012)4 cited
• Generation of Referring Expression Using Prefix Tree Structure(2008)
• → A novel approach for prefix minimization using Ternary Trie (PMTT) for packet classification(2014)
• Route Lookup Algorithms Using the Novel Idea of Coded Prefix Trees(2012)