  If we cannot store all edges in a graph stream, which edges should we store
to estimate the triangle count accurately?
  Counting triangles (i.e., cycles of length three) is a fundamental graph
problem with many applications in social network analysis, web mining, anomaly
detection, etc. Recently, much effort has been made to accurately estimate
global and local triangle counts in streaming settings with limited space.
Although existing methods use sampling techniques without considering temporal
dependencies in edges, we observe temporal locality in real dynamic graphs.
That is, future edges are more likely to form triangles with recent edges than
with older edges.
  In this work, we propose a single-pass streaming algorithm called
Waiting-Room Sampling (WRS) for global and local triangle counting. WRS
exploits the temporal locality by always storing the most recent edges, which
future edges are more likely to form triangles with, in the waiting room, while
it uses reservoir sampling for the remaining edges. Our theoretical and
empirical analyses show that WRS is: (a) Fast and 'any time': runs in linear
time, always maintaining and updating estimates while new edges arrive, (b)
Effective: yields up to 47% smaller estimation error than its best competitors,
and (c) Theoretically sound: gives unbiased estimates with small variances
under the temporal locality.
