ISSN 1000-1239 CN 11-1777/TP

Journal of Computer Research and Development ›› 2015, Vol. 52 ›› Issue (8): 1768-1783.doi: 10.7544/issn1000-1239.2015.20150256

Special Issue: 2015面向大数据的人工智能技术

Previous Articles     Next Articles

FSMBUS: A Frequent Subgraph Mining Algorithm in Single Large-Scale Graph Using Spark

Yan Yuliang1,Dong Yihong1,He Xianmang1,Wang Wei2   

  1. 1(Faculty of Electrical Engineering and Computer Science, Ningbo Univeristy, Ningbo, Zhejiang 315211); 2(School of Computer Science, Fudan University, Shanghai 200433)
  • Online:2015-08-01

Abstract: Mining frequent subgraphs in a single large-scale graph is of huge demand with the rapid growth of the social networking. However, it is inefficient for the serial algorithms to mine frequent subgraphs in low support when mining for a single large-scale graph. Meanwhile, few existing distributed algorithms can’t support the growth pattern mining, and the Hadoop framework they worked is not suitable for iterative running. In this paper, a distributed algorithm named FSMBUS for mining frequent subgraph in a single large-scale graph under Spark framework is proposed. It constructs the parallel computing candidate subgraphs by suboptimal CAM Tree, which returns all the frequent subgraphs for given user-defined minimum support. Additionally, infrequent patterns’ test and searching order chosen is introduced to optimize the algorithm. Sorted-Greedy method is designed for data partition to balance the workload. Our experiments show that FSMBUS runs faster and more effective than the existing algorithms with real datasets,and even can run with the lower support threshold and the larger graph datasets as well. At the same time, FSMBUS runs 2~4 times faster on Spark framework than that on Hadoop framework.

Key words: frequent subgraph, single large-scale graph, distribute mining, Spark, workload balance

CLC Number: