Parallel algorithms for subgraph pattern matching

Abstract

Due to the growing importance of Big Data, graphs are becoming huge in size and are rapidly getting too large for conventional computer approaches. Graph Pattern Matching is often defined in terms of subgraph isomorphism, an NP-Complete problem. Most existing graph pattern matching algorithms are very compute intensive. Unfortunately, for such massive graphs, sequential approaches are almost unfeasible. Therefore, parallel computing resources are required to meet their computational and memory requirements. The paper presents a novel parallel subgraph pattern matching algorithm, known as ParDualIso based on Akka. Since, the sequential implementation of ParDualIso known as DualIso adapts Dual Simulation as the pruning technique, so we also present the parallel implementation of Dual Simulation, referred as ParDualSim. The runtimes of the algorithms are tested against their sequential counter-parts on massive graphs of 10 million vertices and 250 million edges.