基于结构分解的动态图增量匹配算法

• 作者: 吕品 张千桢 李陶深 许嘉 赵翔
• 来源期刊: 计算机科学与探索
• 学科: 工学
• 关键词: 动态图 图模式匹配 增量算法 结构分解 大图数据
• 年，卷（期）: 2018,（8）
• 所属期刊栏目: 数据库技术
• 页码范围: 1214-1224
• 页数: 11页
• 分类号: TP311
• 字数: 8476字
• 语种: 中文
• DOI: 10.3778/j.issn.1673-9418.1709043

摘要

在大数据时代,图数据的规模急剧增长,增量图模式匹配技术能够在数据图发生变化时避免重新对整个数据图进行匹配,进而减少匹配时间,提高整体执行效率,因此成为研究热点.然而,现有的增量匹配算法处理规模较大的模式图时效率会降低.针对该问题,提出了一种基于结构分解的增量图模式匹配算法Inc_CFLS.在匹配过程中,为中间匹配结果构建高效索引,用于后续的模式匹配计算.基于构建的索引信息对数据图增加边事件进行分类,进而为每类增加边事件设计查询剪枝优化策略,从而有效提高匹配效率.在真实数据集上进行实验,结果表明Inc_CFLS算法比目前最好的增量匹配算法在执行效率上平均提升了1～2倍,能更有效支持大规模动态图上的模式匹配.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	赵翔	国防科技大学信息系统与管理学院	7	126	2.0	7.0
2	许嘉	广西大学计算机与电子信息学院	14	9	1.0	2.0
5	吕品	广西大学计算机与电子信息学院	13	8	1.0	2.0
20	张千桢	广西大学计算机与电子信息学院	1	0	0.0	0.0