Frequent Subgraph Mining Based on Pregel

摘要

Graph is an increasingly popular way to model complex data, and the size of single graphs is growing toward massive. Nonetheless, executing graph algorithms efficiently and at scale is surprisingly challenging. As a consequence, distributed programming frameworks have emerged to empower large graph processing. Pregel, as a popular computational model for processing billion-vertex graphs, has been employed to improve the scalability of many algorithms. In this paper, we investigate frequent subgraph mining on single large graphs using Pregel. We present the first distributed algorithm based on Pregel for single massive graphs. In addition, two optimizations are proposed to enhance the algorithm, reducing communication cost and distribution overhead. Extensive experiments conducted on real-life data confirm the effectiveness and efficiency of the proposed algorithm and techniques.