Accelerating Continuous Subgraph Matching on Heterogeneous Processors

The Hong Kong University of Science and Technology
Department of Computer Science and Engineering


PhD Thesis 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 numbers of updates. In this thesis, 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 on static data graphs. 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 organize query vertices in groups and 
perform depth-first search within a group and breadth-first search among groups 
in result enumeration for a balance of time performance and memory consumption.

Finally, we develop GCSM-BU, a GPU-accelerated CSM-BU algorithm under batch 
updates. GCSM-BU adopts a GPU-friendly relational storage format for dynamic 
graphs and maintains a two-level index to efficiently process batches of 
updates. We also improve the matching strategy on leaf vertices to alleviate 
load imbalance and may switch from breadth-first to depth-first search at 
runtime to reduce memory footprint.


Date:                   Friday, 31 May 2024

Time:                   4:00pm - 6:00pm

Venue:                  Room 5510
                        Lifts 25/26

Chairman:               Prof. Lixin WU (MATH)

Committee Members:      Prof. Qiong LUO (Supervisor)
                        Prof. Ke YI
                        Prof. Xiaofang ZHOU
                        Prof. Wei ZHANG (ECE)
                        Prof. Jeffrey Xu YU (CUHK)