[1]巴伦敦,梁 平,顾进广.基于预处理-枚举的子图匹配算法[J].计算机技术与发展,2023,33(12):85-91.[doi:10. 3969 / j. issn. 1673-629X. 2023. 12. 012]
　BA Lun-dun,LIANG Ping,GU Jin-guang.Subgraph Matching Algorithm Based on Preprocessing-enumeration[J].,2023,33(12):85-91.[doi:10. 3969 / j. issn. 1673-629X. 2023. 12. 012]

点击复制

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

分享到：

《计算机技术与发展》[ISSN:1006-6977/CN:61-1281/TN]

卷:

33

期数:

2023年12期

页码:

85-91

栏目:

媒体计算

出版日期:

2023-12-10

文章信息/Info

Title:

Subgraph Matching Algorithm Based on Preprocessing-enumeration

文章编号:

1673-629X(2023)12-0085-07

作者:

巴伦敦¹; 2 ; 梁 平¹; 2 ; 顾进广¹; 2

1. 武汉科技大学 计算机科学与技术学院,湖北 武汉 430065;

2. 智能信息处理与实时工业系统湖北省重点实验室,湖北 武汉 430065

Author(s):

BA Lun-dun1; 2 ; LIANG Ping1; 2 ; GU Jin-guang1; 2

1. School of Computer Science and Technology,Wuhan University of Science and Technology,Wuhan 430065,China;

2. Hubei Province Key Laboratory of Intelligent Information Processing and Real-time Industrial System,Wuhan 430065,China

关键词:

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

Keywords:

graph database; subgraph matching; preprocessing-enumeration; matching order; candidate sets

分类号:

TP311

DOI:

10. 3969 / j. issn. 1673-629X. 2023. 12. 012

摘要:

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

Abstract:

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 theleaves of the vertices in the tree,and enumerating the embeddings in the matching order. However,this processing approach inherentlylimits the algorithm’s performance due to its path - based ordering and tree - structure - based enumeration, as it needs to consider theinfluence between the neighboring points in the paths. We propose a subgraph matching algorithm based on preprocessing-enumerationto solve this problem. The candidate set is first generated by querying the forward neighbors of the vertices, and then the smallercandidate set is obtained by refining the candidate set through the backward neighbors. Meanwhile, the matching order is generatedaccording 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 matchingspeed compared with existing algorithms.

常用功能