FPO tree and DP3 algorithm for distributed parallel Frequent Itemsets Mining

摘要

Frequent Itemsets Mining is a fundamental mining model in Data Mining. It supports a vast range of application fields and can be employed as a key calculation phase in many other mining models such as Association Rules, Correlations, Classifications, etc. Many distributed parallel algorithms have been introduced to confront with very large-scale datasets of Big Data. However, the problems of running time and memory scalability still have not had adequate solutions for very large and "hard-to-mined" datasets. In this paper, we propose a distributed parallel algorithm named DP3 (Distributed PrePostPlus) which parallelizes the state-of-the-art algorithm PrePost(+) and operates in Master-Slaves model. Slave machines mine and send local frequent itemsets and support counts to the Master for aggregations. In the case of tremendous numbers of itemsets transferred between the Slaves and Master, the computational load at the Master, therefore, is extremely heavy if there is not the support from our complete FPO tree (Frequent Patterns Organization) which can provide optimal compactness for light data transfers and highly efficient aggregations with pruning ability. Processing phases of the Slaves and Master are designed for memory scalability and shared-memory parallel in Work-Pool model so as to utilize the computational power of multi-core CPUs. We conducted experiments on both synthetic and real datasets, and the empirical results have shown that our algorithm far outperforms the well-known PFP and other three recently high-performance ones Dist-Eclat, BigFIM, and MapFIM. (C) 2019 Elsevier Ltd. All rights reserved.