Toward Accurate Weight-based Measurement and Periodic Edge Measurement in Graph Stream

Graph streams of sequentially arriving edges are commonly used to represent complex structured data in interactive networks. Typically, graph streams are extremely large and high-velocity. Existing schemes by using graph sketch for summarizing graph stream have demonstrated significant success in handling both storage and query tasks. However, the performance degradation caused by non-uniformly distributions of edge weight and node degree remains unresolved. Current schemes only consider one type of non-uniformly distributions. Meanwhile, there are many periodic edges appearing within the graph streams and finding such periodic edges is crucial for network applications. However, there are no established measurements that predominantly focus on finding periodic edge. To this end, a general graph sketch framework called PMatrix is proposed. PMatrix not only can detect periodic edges, but also adapts to the non-uniformly distributions of edge weight and node degree simultaneously. The performance of PMatrix is evaluated on both CPU and OVS platforms. The experimental results show that PMatrix achieves substantial improvements in measurement precision, reducing the ARE by 62.29% to 99.82% compared with the state-of-the-art graph sketches. For periodic edge measurement, PMatrix has low ARE and F1-Score reaches 100%.