Experimental analysis of the application of the gsketch partitioning method onto the gmatrix graph-stream sketch

Abstract

This report presents a final year project that is about an experimental analysis of applying the gSketch partitioning method onto the gMatrix graph-stream sketch. The report first introduces how the gSketch partitioning method can be applied onto the gMatrix sketch and proposes optimizations for the method, and then analyzes how the gSketch partitioning method changes how gMatrix answers various query types, such as edge frequency, heavy-hitter edges, and node aggregate-frequency queries, and how the performance and probabilistic accuracy guarantees change, and after that, shows experimental results with metrics that each evaluates differently how partitioning affects gMatrix's accuracy for answering the different query types on up to three different graph-stream datasets. Finally, the report concludes that the gSketch partitioning method successfully improves the accuracy of gMatrix in query types such as edge frequency estimation and source-node aggregate-frequency estimation, although fails to bring the same improvements onto the destination-node aggregate-frequency estimation and heavy-hitter edge queries.