GraphZeppelin employs a new sketch algorithm, overcoming a computational bottleneck of existing linear sketching techniques in the semi-streaming graph algorithms literature [1]}. The asymptotically best existing streaming connected components algorithm is Ahn et al.'s StreamingCC  [2]}, [3]}, which has asymptotically low space and update time complexity. StreamingCC relies on \(\ell _0\) -sampling, which it uses to sample edges across arbitrary graph cuts. However, the best known \(\ell _0\) -sampling algorithm suffers from high constant and polylogarithmic factors in its space and update time, as we show in Section . This overhead makes any implementation of the StreamingCC data structure infeasibly slow and large. GraphZeppelin employs what we call CubeSketch, a specialized \(\ell _0\) -sampling algorithm for sampling edges across graph cuts, to solve the connected components problem. For large graphs CubeSketch uses 4 times less space than the best general \(\ell _0\) -sampling algorithm and can process updates more than three orders of magnitude faster.
