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

来源：计算机科学与探索杂志2018年第8期北京时间：

作者：许嘉，张千桢，赵翔，吕品，李陶深

单位：1. 广西大学 计算机与电子信息学院，南宁 5300042. 广西高校并行分布计算技术重点实验室，南宁 5300043. 广西多媒体通信与网络技术重点实验室，南宁 5300044. 国防科技大学 信息系统与管理学院，长沙 410073

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

关键词：动态图,图模式匹配,增量算法,结构分解,大图数据