基于Spark的大规模单图频繁子图算法

Single Large-Scale Graph Frequent Subgraph Algorithm Based on Spark

随着互联网的快速发展,校园一卡通得到了广泛的普及,进而服务器上的数据也在迅速增加。单机算法已无法支撑支持度较低的频繁子图挖掘和子图增长模式的挖掘。海量的单图频繁子图的数据挖掘已无法在单机上实现,现有的Hadoop分布式框架也并不适合迭代式算法运行。因此论文提出一种基于Spark的大规模单图频繁子图挖掘FSMBUS算法。通过次优树构建并行计算的候选子图,在给定最小支持度时挖掘出所有的频繁子图,实验结果表明,单图上最新的算法比FSMBUS的效率慢一个数量级,FSMBUS算法可支持更低的支持度阈值以及更大的图数据挖掘,比Hadoop移植版的效率快2~4倍,分析我校一卡通数据可帮助院校管理、领导决策提出可参照的依据。

With the rapid development of the Internet,the campus card has been widely popularized,and the data on the serv er is also increasing rapidly.The single computer algorithm can not support frequent subgraph mining and growth pattern mining.The data mining of a large number of single graph frequent subgraphs can not be realized on a single machine.The Hadoop distribut ed framework is not suitable for iterative algorithm.Therefore,In this paper,a distributed algorithm named FSMBUS for mining fre quent subgraph in a single large-scale graph under Spark frame work is proposed.It constructs the parallel computing candidate sub graphs by suboptimal CAM Tree,w hich returns all the frequent subgraphs for given user-defined minimum support.This experi ments show that the single chart of new algorithms than the efficiency of FSMBUS is an order of magnitude slower,F SMBUS algo rithm can support lower support threshold and larger map data mining,2~4 times faster than the efficiency of the Hadoop version of the transplant,analysis of our campus card can help college management and leadership of colleges and universities to put forward a reference basis.