TRIÈST: Counting Local and Global Triangles in Fully-Dynamic Streams with Fixed Memory Size
Venue
ACM SIGKDD (2016) (to appear)
Publication Year
2016
Authors
Lorenzo De Stefani, Alessandro Epasto, Matteo Riondato, Eli Upfal
BibTeX
Abstract
We present TRIÈST, a suite of one-pass streaming algorithms to compute unbiased,
low-variance, high-quality approximations of the global and local (i.e., incident
to each vertex) number of triangles in a fully-dynamic graph represented as an
adversarial stream of edge insertions and deletions. Our algorithms use reservoir
sampling and its variants to exploit the user-specified memory space at all times.
This is in contrast with previous approaches which use hard-to-choose parameters
(e.g., a fixed sampling probability) and offer no guarantees on the amount of
memory they will use. We show a full analysis of the variance of the estimations
and novel concentration bounds for these quantities. Our experimental results on
very large graphs show that TRIÈST outperforms state-of-the-art approaches in
accuracy and exhibits a small update time
