An Efficient Parallel FP-Growth Algorithm for Big Data Association Rule Mining

Abstract

The FP-Growth algorithm is a proficient method for correlation analysis, notable for its ability to operate without generating candidate sets and requiring only two database scans. In practical applications, it can represent transaction data within a compressed FP-Tree in memory. This approach addresses the limitations of the Apriori algorithm by decreasing the number of database scans and reducing the candidate sets. However, when applied to large datasets, the FP-Growth algorithm can lead to an excessively large tree structure, straining memory capacity.To address this issue, this paper introduces a parallel FP-Growth algorithm tailored for a big data framework, known as the MRFPG algorithm. This algorithm incorporates load balancing and utilizes intermediate agents to distribute transaction data fragments across a computer cluster. Each node then initiates a map-reduce process to filter out non-frequent items and identify all frequent patterns. Compared to the traditional FP-Growth algorithm, the MRFPG algorithm significantly reduces I/O overhead. Experimental results demonstrate that the MRFPG algorithm is both efficient and rapid.