Accelerating In-Memory Subgraph Matching on a Single Machine

PhD Thesis Proposal Defence


Title: "Accelerating In-Memory Subgraph Matching on a Single Machine"

by

Mr. Shixuan SUN


Abstract:

Graph data are ubiquitous in practice, and subgraph matching is a basic
operation in graph analytics. As modern computers typically have
sufficient processing power and memory resources, we study how to
accelerate in-memory subgraph matching on a single computer. Our approach
is through algorithmic optimization and parallelization.

First, we design PSM, a parallel algorithmic framework for
backtracking-based subgraph matching. Specifically, we abstract the
matching process as a depth-first search (DFS) tree, and parallelize the
search by dividing up the tree into search regions and exploring these
regions in parallel. We design an effective dynamic load balance strategy
for the search. As a result, the PSM-style algorithms achieved a speedup
of 15X-19X over their sequential counterparts on a twenty-core machine.

Second, we develop LIGHT, a parallel subgraph matching algorithm for
unlabeled graphs. The search space in unlabeled subgraph matching, or
called subgraph enumeration, is big due to the absence of vertex labels.
Our approach to reducing the search space and thus redundant computation
is to defer the materialization of intermediate results and to increase
their reuse. Furthermore, we parallelize our algorithm with vector and
simultaneous multithreading instructions in modern computers. Our results
show that LIGHT significantly outperforms the state of the art.

Finally, we introduce our ongoing work on integrating the
backtracking-based method with the worst-case optimal join for subgraph
matching.


Date:			Friday, 22 November 2019

Time:                  	9:00am - 11:00am

Venue:                  Room CYTG001
                         lifts 35/36

Committee Members:	Dr. Qiong Luo (Supervisor)
 			Dr. Wilfred Ng (Chairperson)
 			Dr. Raymond Wong
 			Prof. Ke Yi


**** ALL are Welcome ****