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

This post introduces TRIÈST, a suite of one-pass streaming algorithms for computing unbiased, low-variance approximations of global and local triangle counts in fully-dynamic graphs. TRIÈST utilizes reservoir sampling and its variants to operate within a user-specified memory size, offering novel concentration bounds and outperforming state-of-the-art approaches in accuracy and update time on large graphs.