We present CubeSketch, an \(\ell _0-\) sampling algorithm for vectors on the integers mod 2, which is smaller than the best existing general-purpose \(\ell _0\) -sampling algorithm and is asymptotically faster to update.
Since addition of characteristic vectors (Section REF ) can be thought of as addition over vectors \(\in \mathbb {Z}_2\) , CubeSketch is sufficient for solving the connected components problem. Additionally, CubeSketch may be useful for other sketching algorithms for problems such as edge- or vertex-connectivity, testing bipartiteness, and finding minimum spanning trees and densest subgraphs [1]}, [2]}, [3]}, [4]}.
