高技术通讯2025，Vol.35Issue(7)：675-686,12.DOI:10.3772/j.issn.1002-0470.2025.07.001
PPFG:基于查询图划分的并行子图匹配算法
PPFG:optimization of parallel subgraph matching based on query graph partitioning
摘要
Abstract
As query complexity increases,existing subgraph matching algorithms face significant challenges,including in-sufficient 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 partitio-ning.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 mer-ging method based on load balancing is presented.This method combines partition results by utilizing identical ver-tex 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 fil-tering(LDF),achieving optimal speedups of over 1.2 ×.Moreover,as the number of searches increases,the aver-age 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.关键词
图划分/星形结构/权值过滤/邻居相交/候选集Key words
graph partitioning/star-shaped/weight filtering/neighbor intersection/candidate sets引用本文复制引用
张萍,范晓宣,曹华伟,梁彦,安学军..PPFG:基于查询图划分的并行子图匹配算法[J].高技术通讯,2025,35(7):675-686,12.基金项目
国家重点研发计划(2023YFB4502305)和北京市自然科学基金(4232036)资助项目. （2023YFB4502305）
