基于数据流的大图中频繁模式挖掘算法研究

• 作者: 周佳文 李战怀 樊雪枫 汤小春
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 图挖掘 频繁模式 数据流模型 并行算法 编码树
• 年，卷（期）: 2020,（7）
• 所属期刊栏目: 大数据与智能图象处理
• 页码范围: 1293-1311
• 页数: 19页
• 分类号: TP18
• 字数: 20912字
• 语种: 中文
• DOI: 10.11897/SP.J.1016.2020.01293

摘要

随着单个图数据规模的扩大以及应用领域的扩展,大规模单图的频繁模式挖掘的需求越来越强烈.传统的单机环境已经无法满足大规模图数据挖掘的要求,而现有的并行或者分布式环境下的挖掘方法,普遍受到并行性以及数据倾斜等问题的限制,论文在分析了现有的频繁模式挖掘算法后,提出了一种基于数据流的单个大图频繁模式挖掘方法.首先,建立基于数据流的频繁模式挖掘模型,将MapReduce模型中的“批”数据变成“微批”数据,提高了数据处理的并行度,并且其迭代方式也满足频繁子图挖掘的反单调性;其二,设计了数据流模型中的频繁模式检查、子图实例扩展以及正规编码计算等操作,实现了基于数据流模型的频繁模式挖掘算法;其三,为解决正规编码计算中的复杂性问题,提出了基于不变关系的正规编码计算策略以及基于编码树的优化策略,优化正规编码比未优化编码的计算性能提升了30％,基于编码树的优化策略比原始编码计算策略在性能上提升了10％;最后,对涉及的相关算法进行了实验测试,实验证明,算法提高了频繁模式挖掘的并行性,大幅度减少了大图的搜索空间,降低了正规编码的计算时间,相比于传统算法大规模单图中频繁模式挖掘的效率提升了30％.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李战怀	西北工业大学计算机学院	254	2139	21.0	35.0
2	汤小春	西北工业大学计算机学院	38	222	8.0	13.0
3	樊雪枫	西北工业大学计算机学院	2	0	0.0	0.0
4	周佳文	西北工业大学计算机学院	3	0	0.0	0.0