Fast and Accurate Graph Stream Summarization

摘要: A graph stream is a continuous sequence of data items, in which each item indicates an edge, including its two endpoints and edge weight. It forms dynamic that changes with every item. Graph streams play important roles cyber security, social networks, cloud troubleshooting systems more. Due to the vast volume high update speed streams, traditional structures for storage such as adjacency matrix list are no longer sufficient. However, prior art summarization, like CM sketches, gSketches, TCM gMatrix, either supports limited kinds queries or suffers from poor accuracy query results. In this paper, we propose novel Stream Sketch (GSS short) summarize has linear space cost O(|E|) (E set graph) constant time (O(1)) most over controllable errors. Both theoretical analysis experiment results confirm superiority our solution regard time/space complexity results’ precision compared state-of-the-art.