Parallelizing Recursive Backtracking Based Subgraph Matching on a Single Machine

We propose PSM, an algorithmic framework to parallelize a common class of subgraph matching algorithms, which are based on recursive backtracking. Specifically, we abstract the matching process as a tree search in the state space and different matching algorithms as different orders in the search. Subsequently, we parallelize such subgraph matching by dividing up the state space search tree and exploring it in parallel. Different from traditional approaches that parallelize the search by each individual state, we dynamically split the state tree into search regions each of which consist of a subtree. We further optimize PSM for load balance and communication efficiency. As case studies, we have parallelized three representative recursive backtracking based subgraph matching algorithms in PSM and studied their performance in comparison with their sequential counterparts. Our results show that the PSM -style parallel algorithms achieved a speedup of 15X-19X on the in-memory execution time on a twenty-core machine.