Efficient parallel edge-centric approach for relaxed graph pattern matching

作     者：Bouhenni, Sarra Yahiaoui, Said Nouali-Taboudjemat, Nadia Kheddouci, Hamamache 

作者机构：Ecole Natl Super Informat BP M68 Oued Smar 16309 Algeria CERIST Ctr Rech Informat Sci & Tech Ben Aknoun 16030 Algeria Univ Lyon Univ Lyon 1 UMR5205 LIRISCNRS F-69622 Lyon France 

出 版 物：《JOURNAL OF SUPERCOMPUTING》 (超高速计算杂志)

年 卷 期：2022年第78卷第2期

页      面：1642-1671页

核心收录：

学科分类：0808[工学-电气工程] 08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：Franco-Algerian program PHC Tassili BiGreen [18 MDU 111] DGRSDT grant FNRSDT 

主　　题：Graph pattern matching Subgraph matching Graph simulation Dual simulation Massive graph Parallel algorithm 

摘      要：Prior algorithms on graph simulation for distributed graphs are not scalable enough as they exhibit heavy message passing. Moreover, they are dependent on the graph partitioning quality that can be a bottleneck due to the natural skew present in real-world data. As a result, their degree of parallelism becomes limited. In this paper, we propose an efficient parallel edge-centric approach for distributed graph pattern matching. We design a novel distributed data structure called ST that allows a fine-grain parallelism, and hence guarantees linear scalability. Based on ST, we develop a parallel graph simulation algorithm called PGSim. Furthermore, we propose PDSim, an edge-centric algorithm that efficiently evaluates dual simulation in parallel. PDSim combines ST and PGSim in a Split-and-Combine approach to accelerate the computation stages. We prove the effectiveness and efficiency of these propositions through theoretical guarantees and extensive experiments on massive graphs. The achieved results confirm that our approach outperforms existing algorithms by more than an order of magnitude.