Frequent Subgraph Mining Based on Pregel
Frequent Subgraph Mining Based on Pregel
复制标题
基于Pregel的频繁子图挖掘
DOI：
10.1093/comjnl/bxv118
复制
发表时间：
2016
期刊：
影响因子：
1.4
通讯作者：
Jiuyang Tang
中科院分区：
文献类型：
--
作者：
Xiang Zhao;Yifan Chen;Chuan Xiao;Yoshiharu Ishikawa;Jiuyang Tang
图是一种越来越流行的复杂数据建模方式，并且单个图的大小正变得巨大。尽管如此，高效且大规模地执行图算法仍然具有惊人的挑战性。因此，分布式编程框架应运而生，以支持大型图形处理。 Pregel 作为一种流行的处理十亿顶点图的计算模型，已被用来提高许多算法的可扩展性。在本文中，我们研究了使用 Pregel 对单个大型图进行频繁子图挖掘。我们提出了第一个基于 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 subgraphminingonsinglelargegraphsusingPregel.Wepresentthefirstdistributedalgorithmbased on Pregel for single massive graphs. In addition, two optimizations are proposed to enhance the algorithm,reducing communicationcostanddistributionoverhead. Extensiveexperiments conductedon real-life data confirm the effectiveness and efficiency of the proposed algorithm and techniques.