TRIEST: Counting Local and Global Triangles in Fully Dynamic Streams with Fixed Memory Size

摘要

We present TRIEST, 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.