Abstract:

To solve the problem of huge memory usage of FP-tree construction and traversal in FP-growth, the dynamic-prune algorithm, a concurrent frequent itemsets mining algorithm based on dynamic pruning FP-tree, was proposed. First, by recording the support counts of frequent items during the process of FP-tree construction, the dynamic pruning algorithm of FP-tree was implemented. Sencond, the construction of FP-tree and the discovery of frequent itemsets could be realized simultaneously by using the concurrency strategy. Compared with FP-growth algorithm, it was not necessary to mine frequent itemsets after the construction of FP-tree in dynamic-prune algorithm, and the memory cost reduced. Experimental results showed that the dynamic-prune algorithm outperformed the FP-growth algorithm both in efficiency and scalability.

Key words:  data mining, FP-Tree, frequent itemset, dynamic prune, concurrency