$\mathcal{FR}_{B}$-Sketch: A Graph Stream Summarization Model Based on Pattern and Rank
Xinyao Chen, Xiujing Wen, Changyong Yu · 2024
Graph stream means that the graph's edges are sequentially updated as a stream, which has essential applications in network security and social networks. Different from static graphs, the graph stream has the characteristics of massiveness and fast dynamic update speed. How to efficiently summarize graph streams has become a key research topic. Given a graph, graph data stream summarization is to design a sketch that costs a much smaller space. However, the existing graph stream summarization algorithms have defects, such as only supporting limited query types and low hash space utilization. In this article, we propose a new data structure: a graph data stream summarization method based on Pattern and Rank (referred to as$\mathcal{FR}_{B}$-Sketch) that is a storage structure with high accuracy and high hash space utilization.$\mathcal{PR}_{B}$-Sketch can support multiple types of graph query algorithms. Both theoretical analysis and experimental results show that our method is superior to the prior arts in terms of query accuracy and hash space utilization when processing massive graph stream data.