  Given a graph stream, how can we estimate the number of triangles in it using
multiple machines with limited storage? Specifically, how should edges be
processed and sampled across the machines for rapid and accurate estimation?
  The count of triangles (i.e., cliques of size three) has proven useful in
numerous applications, including anomaly detection, community detection, and
link recommendation. For triangle counting in large and dynamic graphs, recent
work has focused largely on streaming algorithms and distributed algorithms but
little on their combinations for "the best of both worlds".
  In this work, we propose CoCoS, a fast and accurate distributed streaming
algorithm for estimating the counts of global triangles (i.e., all triangles)
and local triangles incident to each node. Making one pass over the input
stream, COCOS carefully processes and stores the edges across multiple machines
so that the redundant use of computational and storage resources is minimized.
Compared to baselines, CoCoS is (a) Accurate: giving up to 39X smaller
estimation error, (b) Fast: up to 10.4X faster, scaling linearly with the size
of the input stream, and (c) Theoretically sound: yielding unbiased estimates.
