Research on Parallelization of Frequent Itemsets Mining Algorithm

摘要

FP-growth is a depth-first mining algorithm based on recursion and pattern growth. However, recursive mode can easily bring huge cost of time and space. Therefore, this paper proposes an improved non-recursive serial algorithm NRFP-growth and a parallel algorithm GPFP-growth. The NRFP-growth algorithm introduces the data structure of FP-array to store data sets, and uses the structure of ItemPoss-map to mine frequent itemsets. The GPFP-growth algorithm is based on NRFP-growth, and uses GPU to accelerate the process of mining frequent itemsets. In order to test the performance of the improved algorithm, this paper selects four data sets with different characteristics, and takes the classical serial algorithm as the benchmark to test the time and space performance of the serial improved algorithm, as well as the speedup ratio performance and scalability of the parallel algorithm.