文档名：基于解耦概要图的大规模图数据高效分布式挖掘算法
频繁封闭子图挖掘被证明是NP-难问题.多年来,虽然已有许多算法被提出用于解决该问题,但在挖掘大规模图数据时,却面临着共同的计算效率问题.特别是,当图中节点的平均度数增加时,挖掘效率更是急剧下降.针对以上问题,本文提出一种面向大规模图数据的高效分布式挖掘算法Desu-FSM.与现有基于水平分解的分布式挖掘框架不同,该算法首次采用了基于垂直分解的分布式挖掘框架.其基本思想可概括为“快速抵近,双向搜索”.首先,通过τ-邻域核图合并,获得概要图集,跨越式地快速抵近较大尺寸子图的聚集区域.在此基础上,通过对概要图的缩减和扩展发现所有被概要图包含和包含概要图的闭图模式.相较于原始图数据,概要图的尺寸和平均节点度数更小.而且,基于概要图的双向搜索可在分布式环境下同时独立完成,不存在耦合.因此,计算效率被大幅提升.大量真实和人工数据集上的测试结果表明,在大规模图数据封闭子图挖掘中,基于垂直分解框架的挖掘效率相较于水平分解框架的效率可提升一个数量级.同时,具有更少的内存空间占用.
作者：李玲 印莹 赵宇海 王国仁
作者单位：东北大学,沈阳市110169北京理工大学,北京市100081
母体文献：第六届中国计算机学会大数据学术会议论文集
会议名称：第六届中国计算机学会大数据学术会议
会议时间：2018年10月11日
会议地点：西安
主办单位：中国计算机学会
语种：chi
分类号：TP3O15
关键词：大规模图数据 分布式挖掘算法 垂直分解 解耦概要图
在线出版日期：2020年11月30日
基金项目：
相似文献
相关博文
- 文件大小:
- 1.35 MB
- 下载次数:
- 60
-
高速下载
|
|
