CS SEMINAR

Parallelizing Recursive Backtracking Based Subgraph Matching on a Single Machine

Speaker
Associate Professor Qiong Luo, Department of Computer Science and Engineering, The Hong Kong University of Science and Technology

Chaired by
Dr HE Bingsheng, Professor, School of Computing
hebs@comp.nus.edu.sg

13 Dec 2018 Thursday, 09:15 AM to 10:30 AM

Executive Classroom, COM2-04-02

Abstract:

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 consists 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.

This is joint work with Shixuan Sun.


Biodata:

Qiong Luo is an Associate Professor at the Department of Computer Science and Engineering, Hong Kong University of Science and Technology (HKUST). Her research interests are in big data systems, parallel and distributed systems, and scientific computing. Current focus is on data management on modern hardware, GPU acceleration for data analytics, and database support for e-science. Qiong received her Ph.D. in Computer Sciences from the University of Wisconsin-Madison in 2002, her M.S. and B.S. in Computer Sciences from Beijing (Peking) University, China in 1997 and 1992 respectively.