GeminiSketch: An Accurate and Efficient Sketch for Summarizing Temporal Graph Streams with Rolling-Out Elimination

A temporal graph stream represents a graph stream with dynamic behaviors, where the edges connecting vertices change over time. It can model a wide range of network behaviors, e.g., describing changes of subscribers in a social network, monitoring call duration within a mobile network. Analyzing the temporal graph streams needs to timely eliminate expired edges as time goes on. However, existing graph stream summarization methods inadequately handle this temporal characteristic, causing problems in query accuracy and efficiency. In this paper, we propose GeminiSketch, a novel accurate and efficient sketch to summarize temporal graph streams with Rolling-out elimination. GeminiSketch adopts a dual-matrix design to separately record graph edges based on temporal information and vertex relationship, thereby reducing the summarization error and facilitating the management of graph edges. For temporal graph queries, it can quickly access the graph information from the corresponding matrix, which addresses the efficiency problem. Furthermore, GeminiSketch employs a new Rolling-out elimination strategy to efficiently and accurately eliminate expired edges from a large number of edges in a directional way instead of a full traversal, solving the accuracy problem caused by expired edges that are not removed in time. Experimental results demonstrate that GeminiSketch significantly outperforms prior work by supporting various types of temporal graph queries, achieving smaller errors and higher process speed under same experiment settings. The source code of GeminiSketch is available on GitHub.