Large Scale Frequent Pattern Mining Using MPI One-Sided Model
Abhinav Vishnu, Khushbu Agarwal · 2015
In this paper, we propose a work-stealing runtime -- Library for Work Stealing LibWS -- using MPI one-sided model for designing scalable FP-Growth -- de facto frequent pattern mining algorithm -- on large scale systems. LibWS provides locality efficient and highly scalable work-stealing techniques for load balancing on a variety of data distributions. We also propose a novel communication algorithm for FP-growth data exchange phase, which reduces the communication complexity from state-of-the-art Θ(p) to Θ(f + p/f), for p processes and f frequent attributed-ids. FP-Growth is implemented using LibWS and evaluated on several work distributions and support counts. An experimental evaluation of the FP-Growth on LibWS using 4096 processes on an InfiniBand Cluster demonstrates excellent efficiency for several work distributions (91% efficiency for Power-law and 93% for Poisson). The proposed distributed FP-Tree merging algorithm provides 38x communication speedup on 4096 cores.