Durable Subgraph Matching on Temporal Graphs

Durable subgraph matching on a temporal graph finds all subgraphs in the temporal graph that not only match the given query graph but also have duration longer than a user-specified duration threshold. The state-of-the-art algorithm (Semertzidis and Pitoura, 2016, 2019) for solving this problem requires lots of memory when the input temporal graph is large. In this paper, a new algorithm is proposed to solve this problem. Many effective techniques are developed to improve the performance of this algorithm, including the DFS-based query decomposition method, the TD-tree index structure, the sort-based vertex matching order, and the time instance set compaction method. The experimental results show that the proposed algorithm is an order of magnitude faster and requires significantly less memory than the state-of-the-art algorithm.