U.S. Department of Energy

Pacific Northwest National Laboratory

Fault Tolerant Frequent Pattern Mining

Publish Date: 
Monday, December 19, 2016
FP-Growth algorithm is a Frequent Pattern Mining (FPM) algorithm that has been extensively used to study correlations and patterns in large scale datasets. While several researchers have designed distributed memory FP-Growth algorithms, it is pivotal to consider fault tolerant FP-Growth, which can address the increasing fault rates in large scale systems. In this work, we propose a novel parallel, algorithm-level fault-tolerant FP-Growth algorithm. We leverage algorithmic properties and MPI advanced features to guarantee an O(1) space complexity, achieved by using the dataset memory space itself for checkpointing. We also propose a recovery algorithm that can use in-memory and disk-based checkpointing, though in many cases the recovery can be completed without any disk access, and incurring no memory overhead for checkpointing. We evaluate our FT algorithm on a large scale InfiniBand cluster with several large datasets using up to 2K cores. Our evaluation demonstrates excellent efficiency for checkpointing and recovery in comparison to the disk-based approach. We have also observed 20x average speed-up in comparison to Spark, establishing that a well designed algorithm can easily outperform a solution based on a general fault-tolerant programming model.
Shohdy S, A Vishnu, and G Agrawal. 2016. "Fault Tolerant Frequent Pattern Mining." In IEEE 23rd International Conference on High Performance Computing (HiPC), December 19-22, 2016, Hyderabad, India, pp. 12-21. IEEE Computer Society, LOS ALAMITOS, CA. doi:10.1109/HiPC.2016.012
| Pacific Northwest National Laboratory