面向模式图变化的增量图模式匹配

来源：软件学报杂志2015年第11期北京时间：

作者：张丽霞,王伟平,高建良,王建新

单位：张丽霞，中南大学 信息科学与工程学院, 湖南 长沙 410083;湖南师范大学 数学与计算机科学学院, 湖南 长沙 41008111,王伟平，中南大学 信息科学与工程学院, 湖南 长沙 41008302,高建良，中南大学 信息科学与工程学院, 湖南 长沙 41008303,王建新，中南大学 信息科学与工程学院, 湖南 长沙 41008304

摘要：在大数据时代,数据图的规模急剧增长,增量图模式匹配算法能够在数据图或模式图发生变化时避免重新在整个数据图上进行匹配、减少响应时间,因此成为了研究的热点.针对实际应用中数据图不变而模式图发生变化的情况,提出了一种面向模式图变化的增量图模式匹配算法PGC_IncGPM,在模式图匹配的过程中记录适当的中间结果作为索引,用于后续的模式匹配.提出了增强的图模式匹配算法GPMS,用于首次整个数据图上的模式匹配.该算法一方面能够建立后续增量匹配所需的索引,另一方面减少了整个数据图匹配的执行时间.设计实现了面向模式图增边和减边的两个核心子算法,通过子算法的组合,能够支持在模式图发生各种变化时进行增量图模式匹配.在真实数据集和合成数据集上进行实验,结果表明:与重新在整个数据图上进行匹配的ReComputing算法相比,当模式图中变化的边的数目不超过不变的边的数目时,PGC_IncGPM算法能够有效减少图模式匹配的执行时间;随着数据图规模的增大,PGC_IncGPM算法相对于ReComputing算法的执行时间的减少程度更加明显,对于大规模数据图具有更好的适用性.

关键词：图模式匹配;增量算法;动态图;大数据

基金资助：国家自然科学基金(61232001, 61173169); 湖南省教育厅项目(15C0824)