Accelerating Continuous Subgraph Matching on Heterogeneous Processors

PhD Thesis Proposal Defence


Title: "Accelerating Continuous Subgraph Matching on Heterogeneous Processors"

by

Mr. Xibo SUN


Abstract:

Continuous subgraph matching (CSM) is an operation that keeps processing 
subgraph queries on a dynamic data graph. This operation is essential to many 
applications, but it is usually time- consuming due to its high algorithmic 
complexity and large data volumes. In this thesis proposal, we study CSM on a 
dynamic graph with single and batch updates, and improve the matching 
performance on the GPU.

To understand the performance issues in CSM, we design a common framework based 
on incremental view maintenance to model CSM under single updates. We analyze 
and re-implement six representative CSM algorithms within the framework, and 
conduct extensive experiments to compare the overall performance of competing 
algorithms as well as individual techniques, such as indexing and the matching 
order, to pinpoint the key factors leading to performance differences.

To improve the performance of CSM, we first propose EGSM, an efficient approach 
to GPU-based subgraph matching. Specifically, we design a data structure Cuckoo 
trie to support dynamic maintenance of candidates for filtering, and order 
query vertices based on estimated numbers of candidate vertices on the fly. 
Furthermore, we perform a hybrid breadth-first and depth-first search with 
memory management for result enumeration.

Finally, we propose CSM-BU, a generic algorithm for continuous subgraph 
matching on dynamic graphs under batch updates, and describe the research plan.


Date:                   Monday, 18 March 2024

Time:                   2:00pm - 4:00pm

Venue:                  Room 5501
                        Lifts 25/26

Committee Members:      Prof. Qiong Luo (Supervisor)
                        Prof. Xiaofang Zhou (Chairperson)
                        Prof. Ke Yi
                        Prof. Wei Zhang (ECE)