WRS (Waiting Room Sampling)
is a single-pass streaming algorithm for global and local triangle counting in (fully dynamic) real graph streams.
exploits a temporal dependency pattern in real dynamic graph streams.
has the following properties:
- Fast and Any time: WRS scales linearly with the number of edges in the input graph stream, and gives estimates at any time while the input graph grows
- Effective: estimation error in WRS is up to 47% smaller than those in state-of-the-art methods
- Theoretically Sound: WRS gives unbiased estimates with small variance under the temporal locality.
is described in the following paper:
WRS: Waiting Room Sampling for Accurate Triangle Counting in Real Graph Streams.
IEEE International Conference on Data Mining (ICDM) 2017, New Orleans, USA
[PDF] [Supplementary Document] [BIBTEX]
Temporal Locality-Aware Sampling for Accurate Triangle Counting in Real Graph Streams.
Dongjin Lee, Kijung Shin, and Christos Faloutsos
The VLDB Journal, 2020,
The source code used in the paper is available. [Github Repository]