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

作     者：许嘉 张千桢 赵翔 吕品 李陶深 XU Jia1,2,3, ZHANG Qianzhen1, ZHAO Xiang4, LV Pin1,2,3, LI Taoshen1,2

作者机构：广西大学计算机与电子信息学院南宁530004 广西高校并行分布计算技术重点实验室南宁530004 广西多媒体通信与网络技术重点实验室南宁530004 国防科技大学信息系统与管理学院长沙410073 

出 版 物：《计算机科学与探索》 (Journal of Frontiers of Computer Science and Technology)

年 卷 期：2018年第12卷第8期

页      面：1214-1224页

核心收录：

学科分类：08[工学] 0835[工学-软件工程] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：国家自然科学基金Nos.61402494 61402498 61402513 广西自然科学基金青年基金Nos.2015GXNSFBA139243 2016GXNSFBA380182 广西大学科研基金Nos.XGZ141182 XGZ150322 广西高等教育本科教学改革工程项目重点项目No.2017JGZ103~~ 

主　　题：动态图 图模式匹配 增量算法 结构分解 大图数据 

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