Sampling massive streaming call graphs

What is it about?

The problem of analyzing massive graph streams in real time is growing along with the size of streams. Sampling techniques have been used to analyze data streams in real time. However, there are very few techniques for sampling graph streams. Therefore, we propose sequential sampling techniques for sampling evolving network streams. We used the state of the art Space Saving algorithm for generating topK edges' network samples, We also propose a simple biased version of reservoir sampling, which shows better comparative results than Reservoir Sampling. When sampling evolving network streams it is difficult to answer questions like, which structures are well preserved by the sampling techniques over the evolution of streams? Which sampling techniques yield proper estimates for directed and weighted graphs? Which techniques have least time complexity etc.? In this work, we have answered the above questions by comparing and analyzing the evolving samples of such graph streams. Further, evaluated the sampling techniques by comparing the structural measures from their samples.

Featured Image