Hasse diagram based algorithm for continuous temporal subgraph query in graph stream

摘要

Continuous subgraph pattern matching is an extension of the traditional subgraph pattern matching and becoming a subject that attracts increasing interest. It requires the near real-time responses and is used in many applications, for example, abnormal monitoring in social networks, cyber attacks monitoring in cyber networks. As the dynamic graph changes with time, the temporal subgraph pattern (i.e., the edges have temporal relation) is considered. In this paper, the Hasse diagram is introduced to represent the temporal relation of the query graph. Then we design the Hasse-cache structure, and propose a continuous temporal subgraph pattern matching algorithm based on the Hasse diagram. The algorithm uses the probability of dynamic graph to reduce the intermediate results, and can implement the matching of topology and the verification of temporal relation simultaneously. Our experiments with real-world datasets show that the proposed algorithm has 10x speedups over the previous approaches.