FSMBUS:一种基于Spark的大规模频繁子图挖掘算法

被引：19

作者：

严玉良 ^{[1
]}

董一鸿 ^{[1
]}

何贤芒 ^{[1
]}

汪卫 ^{[2
]}

机构：

[1] 宁波大学信息科学与工程学院

[2] 复旦大学计算机科学技术学院

来源：

计算机研究与发展 | 2015年 / 52卷 / 08期

关键词：

频繁子图; 大规模单图; 分布式挖掘; Spark; 负载均衡;

D O I：

暂无

中图分类号：

TP311.13 [];

学科分类号：

1201 ;

摘要：

随着社交网络用户数的快速增加,大规模单图上频繁子图挖掘的需求越来越强烈.单机算法对大规模图的运行效率较低,难以支撑支持度较低的频繁子图的挖掘;现有的分布式环境下单图的频繁子图挖掘算法不支持子图增长模式的挖掘,它们所使用的Hadoop框架也不适合运行迭代式算法.提出了一种基于Spark的大规模单图频繁子图挖掘算法FSMBUS,通过次优树构建并行计算的候选子图,在给定最小支持度时挖掘出所有的频繁子图,并利用非频繁检测和搜索顺序选择实现优化,还设计了一种名为Sorted-Greedy的轻量级数据划分方法.实验结果表明,FSMBUS的效率要比现有单图上最新的算法快一个数量级,并支持更低最小支持度阈值以及更大规模图数据的挖掘,同时FSMBUS比其Hadoop的移植版要快2～4倍.

引用

页码：1768 / 1783

页数：16

共 6 条

[1] 一种新的基于嵌入集的图分类方法
王桂娟
印鉴
詹卫许
[J]. 计算机研究与发展, 2012, 49 (11) : 2311 - 2319
[2] 一种高效频繁子图挖掘算法
李先通
李建中
高宏
[J]. 软件学报, 2007, (10) : 2469 - 2480
[3] 基于图论的频繁模式挖掘
汪卫
周皓峰
袁晴晴
楼宇波
施伯乐
不详
[J]. 计算机研究与发展 , 2005, (02) : 230 - 235
[4] Mining globally distributed frequent subgraphs in a single labeled graph
Jiang, Xing
Xiong, Hui
Wang, Chen
Tan, Ah-Hwee
[J]. DATA & KNOWLEDGE ENGINEERING, 2009, 68 (10) : 1034 - 1058
[5] MapReduce[J] . Jeffrey Dean,Sanjay Ghemawat.Communications of the ACM . 2008 (1)
[6] Finding Frequent Patterns in a Large Sparse Graph*
Michihiro Kuramochi
George Karypis
[J]. Data Mining and Knowledge Discovery, 2005, 11 : 243 - 271

← 1 →