| 张萍* ** ***,范晓宣* **,曹华伟* **,梁彦* **,安学军* **.PPFG:基于查询图划分的并行子图匹配算法[J].高技术通讯(中文),2025,35(7):675~686 |
| PPFG:基于查询图划分的并行子图匹配算法 |
| PPFG:optimization of parallel subgraph matching based on query graph partitioning |
| |
| DOI：10. 3772 / j. issn. 1002-0470. 2025. 07. 001 |
| 中文关键词: 图划分;星形结构;权值过滤;邻居相交;候选集 |
| 英文关键词: graph partitioning,star-shaped, weight filtering, neighbor intersection, candidate sets |
| 基金项目: |
| 作者 | 单位 | | 张萍* ** *** | (* 处理器芯片全国重点实验室(中国科学院计算技术研究所) 北京 100190)
(** 中国科学院大学计算机科学与技术学院 北京 100049)
(*** 北京科技职业大学集成电路学院(人工智能学院) 北京 100176) | | 范晓宣* ** | | | 曹华伟* ** | | | 梁彦* ** | | | 安学军* ** | |
|
| 摘要点击次数: 356 |
| 全文下载次数: 539 |
| 中文摘要: |
| 随着查询复杂度的提升,现有子图匹配算法面临过滤候选集筛选力度不足等问题,严重制约匹配效率。 据此,本文提出了基于查询图划分的并行子图匹配算法(parallel partition filter gather,PPFG)。 首先,提出基于贪心策略的星形划分方法,把查询图划分为若干精简子图并提前实施剪枝处理;其次,提出基于权值和邻居相交的过滤方法,将查询图和数据图的邻居节点信息作为权重来筛选候选集以缩小验证规模;最后,提出基于负载均衡的并行合并方法,依据不同划分子图在同一个节点取值相同和查询图与数据图的点位双射关系将划分结果合并。 实验结果表明,在 Xeon E5-2683v3 服务器上该算法相比过滤-验证算法(label and degree filtering,LDF)在测试数据集上缩小 10% ~ 50% 候选集,最优加速比达到 1. 2 倍,平均查找时间随着查找数目的增加明显下降,相比核心-森林-叶子分层框架(core-forest-leaf,CFL)算法最优可达 18% 以上的速率提升。 |
| 英文摘要: |
| As query complexity increases,existing subgraph matching algorithms face significant challenges,including insufficient candidate filtering,which severely limits subgraph matching efficiency. This paper proposes the parallel partition filter gather(PPFG),a parallel optimization algorithm for subgraph matching based on query graph partitioning. First,a star-shaped partitioning method based on a greedy strategy is introduced,which divides the query graph into several subgraphs and prunes them in advance. Second,a filtering method based on weight and neighbor intersection is proposed,leveraging neighbor information as weights to refine candidate sets. Finally,a parallel merging method based on load balancing is presented. This method combines partition results by utilizing identical vertex values and bijective relationships between query and data graph vertices. Experimental results demonstrate that on a Xeon E5-2683v3 server,PPFG reduces candidate sets by 10% - 50% compared with the label and degree filtering (LDF),achieving optimal speedups of over 1. 2 × . Moreover,as the number of searches increases,the average search time of PPFG decreases significantly,achieving up to an 18% performance improvement over the core-forest-leaf(CFL)algorithm in the best-case scenario. |
|
查看全文
查看/发表评论 下载PDF阅读器 |
| 关闭 |
|
|
|
