Efficient graph stream summarization method for heavy hitter flows and heavy changer flows
Tianxiang Ma, Mingwei Zhao, Dan Li, Zhuoran Li, Zhuo Li · 2025
To enable accurate queries for heavy hitter and heavy changer flows in graph data, we propose Heavy Matrix, a novel and efficient graph stream summarization method. It comprises three matrices: the Cuckoo Matrix as the main structure, the Buffer Matrix for additional conflict edges, and the Mark Matrix for heavy hitter flows with low volume but high weights. Each matrix has its own function and they work together to efficiently measure these flows and perform well in general queries. Heavy Matrix also improves the traversal algorithm with a flag for location determination, reducing traversal time and boosting insertion throughput. Simulation experiments on real-network datasets verify the method's effectiveness for heavy hitter and heavy changer flows through accuracy and throughput analysis.