图模式匹配在图挖掘中是一类具有挑战性的问题。首先,模式图中顶点或边的搜索顺序与性能密切相关,不同的搜索顺序可能会导致最后的执行时间相差几个数量级,其次,由于模式图普遍存在对称结构,对称结构在模式匹配的过程中会不可避免地映射到同一组嵌入,从而引发了冗余计算,这还会导致最终匹配结果中存在自同构,最后,在枚举子图的过程中,中间子图规模,计算量呈指数级别增长,系统的内存消耗往往很大。为解决以上问题,单机图挖掘系统Tuwajuer提供了一套处理有向图模式匹配的高效方案。系统将有向图的模式匹配分成非等价模式图,等价环模式图和轴对称模式图三类。针对非等价模式图,基于边选择度的有向图模式匹配算法实现了结合模式图与数据图实时地生成探索顺序,通过每次扩展选择度最大的边来保证当前的探索空间最小,以达到减小计算量的目的。针对等价环模式图,基于DFS(Depth First Search)的图匹配算法通过最小起始点的规则限制使每个任务在探索过程中能够迅速剪枝掉大量不符合规则的探索路径,这在消除自同构的同时,避免了冗余计算。针对轴对称模式图,模式图分割与重组策略通过等价点组分割出模式图中唯一的重复子结构,对分割后的模式图进行模式匹配,在模式匹配的过程中,可以对得到的分支嵌入进行重新组合得到整个嵌入,实现了不需要挖掘完整的模式图而只用挖掘模式图的重复子结构就能得到模式图的所有嵌入,这削减了模式匹配原本所必须的计算量,并改善了中间数据爆炸的问题。通过与当前主流的图挖掘系统对比,Tuwajuer可以处理十亿边级别的数据,并且具有良好的可扩展性。总体性能优于Peregrine和Graph Pi。特别是对于轴对称模式图,在不同的数据集下,Tuwajuer比这两个系统的性能要高出30%到600%。
暂无评论