Xiangyang Gou’s research paper "Fast and Accurate Graph Stream Summarization" is accepted by ICDE 2019.

A graph stream is a continuous sequence of data items, and each item describes an edge, including its vertexes and weight. It forms a dynamic graph that changes with every item in the stream. Graph streams play important roles in cyber security, social networks, cloud troubleshooting systems and other fields. Due to the vast volume and high update speed of graph streams, traditional data structures for graph storage such as the adjacency matrix and the adjacency list are no longer sufficient. Fortunately, it is usually not necessary to store graph streams precisely. Small and controllable errors are acceptable in most applications. Therefore, a practical approach to catch up with the update speed of the graph stream without unaffordable memory usage is to create a summarization of it in each time window. However, prior art of graph stream summarization, like CM sketches, gSketches and TCM, either supports limited kinds of queries or suffers from poor accuracy. In this paper, we propose Graph Stream Sketch (GSS). It has small memory usage and fast update speed, and supports most kinds of queries. Mathematical analysis and experiment results show that in these queries it has very high accuracy, much more accurate than the prior art of graph stream summarization.