Tiered Sampling: An Efficient Method for Approximate Counting Sparse Motifs in Massive Graph Streams

Lorenzo De Stefani, Erisa Terolli, Eli Upfal

We introduce Tiered Sampling, a novel technique for approximate counting sparse motifs in massive graphs whose edges are observed in a stream. Our technique requires only a single…