The Case for External Graph Sketching

Michael A. Bender, Martín Farach-Colton, Riko Jacob +3

Algorithms in the data stream model use $O(polylog(N))$ space to compute some property of an input of size $N$, and many of these algorithms are implemented and used in practice. H…