基于预处理-枚举的子图匹配算法

来源：计算机技术与发展杂志2023年第12期北京时间：

作者：巴伦敦;';梁平;';顾进广;'

单位：1. 武汉科技大学 计算机科学与技术学院,湖北 武汉 430065;2. 智能信息处理与实时工业系统湖北省重点实验室,湖北 武汉 430065

摘要：子图匹配是从与查询图格式相同的数据图中找到所有嵌入。 目前常用的算法主要通过基于查询图在数据图上生成树结构索引来工作,对树中的顶点根到叶的路径进行排序,并按照匹配顺序枚举嵌入。 但是这种处理方式由于没有考虑路径中邻接点之间的影响,其基于路径的排序和基于树结构的枚举在本质上限制了算法的性能。 为了解决这个问题,提出了一种基于预处理-枚举的子图匹配算法。 先通过查询顶点的前向邻居生成候选集,再通过后向邻居对候选集进行精化得到更小的候选集。 同时,根据查询顶点的候选数量和度生成匹配顺序,进一步消除了基于路径的排序带来的限制。针对真实数据集的模拟实验结果表明,所提出的算法与现有的算法相比具有更好的候选集过滤效果和更快的匹配速度。

关键词：图数据库;子图匹配;预处理-枚举;匹配顺序;候选集