Date: Tue, 2017-11-07
Time: 2:30 pm
Location: 216 Atanasoff
Title: Triangle counting in graph streams: Power of multi-sampling
Abstract: Some of the well known streaming algorithms to estimate number of triangles in a graph stream work as follows: Sample a single triangle with high enough probability and repeat this basic step to obtain a global triangle count. For example, one such algorithm uniformly at random picks a single vertex v and a single edge e and checks whether the two cross edges that connect v to e appear in the stream. In this algorithm, the basic sampling step is repeated multiple times to obtain an estimate for the global triangle count in the input graph stream. This work, proposes a multi-sampling variant of this algorithm: Instead of randomly choosing a single vertex and edge, randomly sample multiple vertices and multiple edges and collect cross edges that connect sampled vertices to the sampled edges. We provide a theoretical analysis of this algorithm and prove that this simple modification improves upon the known space and accuracy bounds. We experimentally show that the proposed algorithm out performs several well known triangle counting streaming algorithms.