A Survey on Continuous Subgraph Matching

PhD Qualifying Examination


Title: "A Survey on Continuous Subgraph Matching"

by

Mr. Xibo SUN


Abstract:

Continuous subgraph matching algorithms find the occurrences of a query 
graph in a stream of data graphs online. Many incremental algorithms have 
been proposed, utilizing indices, filtering techniques, and graph 
exploration strategies. However, these algorithms are designed and 
implemented in various frameworks, which makes it hard to conduct 
comparison studies. In this survey, we present these algorithms in a 
uniform framework and categorize them as subgraph-view, vertex-view, or 
edge-view, depending on how they reduce redundant computation. 
Specifically, subgraph-view algorithms identify a subgraph in the data 
graph that may yield incremental results and prune the graph components 
outside the subgraph on each update; Vertex-view methods define a state 
for each vertex in the data graph and perform incremental matching based 
on state changes of the vertices; Edge-view algorithms model a graph 
update as a single edge insertion or deletion, and handle incremental 
matching by directly exploring the data graph from the inserted or deleted 
edge. Additionally, We discuss variants of this problem and future 
directions.


Date:			Thursday, 14 January 2021

Time:                  	2:00pm - 4:00pm

Zoom meeting: 
https://hkust.zoom.us/j/92736781468?pwd=MG5sMHU2WnNrM2VQQ0k2UzY2czNMQT09

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


**** ALL are Welcome ****