Youhuan Li’s paper “Time Constrained Continuous Subgraph Search over Streaming Graphs” was accepted by ICDE 2019.

Streaming Graphs is an unbounded time-evolving edge sequence where each edge has a unique timestamp that is sorted in ascending order. Given a time window, edges within the window form a subgraph of the streaming graph, called snapshot. In this paper, we study the subgraph isomorphism over the constantly updated snapshot for each window. Different from the traditional subgraph isomorphism, we impose timing order constraints between different query edges. In real scenario, subgraph represents a series relations and interactions between a group of objects and different timing order over these relations/interactions have different real-world meanings. For instance, for a group of people who are friends of each other, different timing order over the friend relations means different process building the entire friend group.

In this paper, we first propose a baseline solution for the subgraph search which greatly reduce the intermediate results to accelerate the computation. Then, we further reduce the space cost of those maintained results based on their huge overlaps on structures. Finally, we propose a fine-grained concurrent mechanism to improve the system throughput. The effectiveness of the proposed algorithm is confirmed over various experiments on different datasets.