Efficient parallel edge-centric approach for relaxed graph pattern matching

dc.contributor.authorBouhenni, Sarra
dc.contributor.authorYahiaoui, Saïd
dc.contributor.authorNouali-Taboudjemat, Nadia
dc.description.abstractPrior 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.
dc.relation.ispartofseriesThe Journal of Supercomputing; 78
dc.structureCalcul pervasif et mobile (Pervasive and Mobile Computing group)
dc.subjectGraph pattern matching
dc.subjectSubgraph matching
dc.subjectGraph simulation
dc.subjectDual simulation
dc.subjectMassive graph
dc.subjectParallel algorithm
dc.titleEfficient parallel edge-centric approach for relaxed graph pattern matching