An Algorithm of Association Rules Mining for Massive Data Based on Partly Disk Resident FP-TREE Exploiting B+ Tree Index

摘要

As the size of the data set mined is increasing constantly, the size of the available memory has become one bottleneck when FP-GROWTH and similar algorithms are used for association rules mining. So it is necessary to tackle scalability by some new algorithms in order to mine associationrules from massive data with low user-specified support. Nowadays, the disk resident algorithms have become a main research target. Therefore, based on LIFO storage strategy and the thought of storing FP-TREE partly exploiting B+ tree index, a novel algorithm called DRBFP-MINE (disk residentB+ tree FP-TREE mine) is presented in this paper. This algorithm decreases memory occupation through storing FP-TREE partly based on optimized storage strategy and high efficient index technology. When the mining job fails because FP-GROWTH and similar algorithms use too much memory, DRBFP-MINEcan discover association rules from massive data successfully. In addition, DRBFP-MINE overcomes the low efficiency problem of DISK-MINE, which projects data set too early only because some FP-TREE can not be accommodated in the available memory. The verification experiments and performanceanalyses are presented on synthetic data set and real data set. The experimental results show that on the limited memory occasions, DRBFP-MINE is an effective disk resident association rules mining algorithm for massive data.