基于预处理-枚举的子图匹配算法
Subgraph Matching Algorithm Based on Preprocessing-enumeration
巴伦敦 1梁平 1顾进广1
作者信息
- 1. 武汉科技大学 计算机科学与技术学院,湖北 武汉 430065;智能信息处理与实时工业系统湖北省重点实验室,湖北 武汉 430065
- 折叠
摘要
子图匹配是从与查询图格式相同的数据图中找到所有嵌入.目前常用的算法主要通过基于查询图在数据图上生成树结构索引来工作,对树中的顶点根到叶的路径进行排序,并按照匹配顺序枚举嵌入.但是这种处理方式由于没有考虑路径中邻接点之间的影响,其基于路径的排序和基于树结构的枚举在本质上限制了算法的性能.为了解决这个问题,提出了一种基于预处理-枚举的子图匹配算法.先通过查询顶点的前向邻居生成候选集,再通过后向邻居对候选集进行精化得到更小的候选集.同时,根据查询顶点的候选数量和度生成匹配顺序,进一步消除了基于路径的排序带来的限制.针对真实数据集的模拟实验结果表明,所提出的算法与现有的算法相比具有更好的候选集过滤效果和更快的匹配速度.
Abstract
Subgraph matching is finding all embeddings from a data graph in the same format as the query graph.The currently used algo-rithms work mainly by generating a tree structure index on the data graph based on the query graph,sorting the paths from the root to the leaves of the vertices in the tree,and enumerating the embeddings in the matching order.However,this processing approach inherently limits the algorithm's performance due to its path-based ordering and tree-structure-based enumeration,as it needs to consider the influence between the neighboring points in the paths.We propose a subgraph matching algorithm based on preprocessing-enumeration to solve this problem.The candidate set is first generated by querying the forward neighbors of the vertices,and then the smaller candidate set is obtained by refining the candidate set through the backward neighbors.Meanwhile,the matching order is generated according to the number and degree of candidates of the query vertices,which eliminates the limitation of path-based ranking.The exper-imental simulation results for real data sets show that the proposed algorithm has a better candidate set filtering effect and faster matching speed compared with existing algorithms.
关键词
图数据库/子图匹配/预处理-枚举/匹配顺序/候选集Key words
graph database/subgraph matching/preprocessing-enumeration/matching order/candidate sets引用本文复制引用
基金项目
国家社会科学基金重大项目(11&ZD189)
出版年
2023
国家科技期刊平台
NSTL
维普
万方数据