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

Subgraph Matching Algorithm Based on Preprocessing-enumeration

作　　者：巴伦敦 梁平[1,2] 顾进广 BA Lun-dun;LIANG Ping;GU Jin-guang(School of Computer Science and Technology,Wuhan University of Science and Technology,Wuhan 430065,China;Hubei Province Key Laboratory of Intelligent Information Processing and Real-time Industrial System,Wuhan 430065,China)

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

出　　处：《计算机技术与发展》2023年第12期85-91,共7页Computer Technology and Development

基　　金：国家社会科学基金重大项目(11&ZD189)。

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

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

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]