In this talk, I will first provide a quick overview of our works in the area of graph query processing. Then I will provide some details on our works on answering reachability and historical reachability queries. A reachability query asks, given two vertices u and v in a directed graph G, whether u can reach v, that is, whether there is a path from u to v in G. This problem has been well studied and there is a large body of literature. We show how a multi-level compression technique can speed-up reachability query answering. A historical reachability query asks, given an evolving directed graph that consists of a sequence of snapshots of the graph at different time moments, whether a vertex u can reach vertex v in any of the snapshots. We show how this problem can be converted into a conventional reachability query by building an index called the HR-index, which is a single compressed graph containing the reachability information of all snapshots. Experiments show our method far outperforms previous methods in both time and space efficiency.
Short bio: John (Junhu) Wang is an Associate Professor at Griffith University, Gold Coast Campus. He obtained his PhD in Computer Science from Griffith University in 2003. His current research interests include Graph Query Processing, Social Network Analysis, Text Data Analysis, Knowledge Representation & Reasoning, and Algorithm Design. He has published in top venues such as SIGMOD, VLDB, ICDE, EDBT, TKDE and TODS. More information can be found at https://experts.griffith.edu.au/7207-john-wang.
