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 requ...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on knowledge and data engineering 2023-05, Vol.35 (5), p.4713-4726
Main Authors: Li, Faming, Zou, Zhaonian, Li, Jianzhong
Format: Article
Language:English
Subjects:
Algorithms
durable subgraph matching
Graph matching
Graph theory
index
Indexes
Memory management
Merging
Network analyzers
Pattern matching
Prediction algorithms
Social networking (online)
subgraph isomorphism
Temporal graph
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1041-4347
1558-2191
DOI:10.1109/TKDE.2022.3148995