TRIEST is 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. The 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 require hard-to-choose parameters (e.g., a fixed sampling probability) and offer no guarantees on the amount of memory they use. We analyze the variance of the estimations and show novel concentration bounds for these quantities.
This is joint work with Lorenzo De Stefani, Alessandro Epasto, and Eli Upfal. It received the best student paper award at ACM KDD’16.
Matteo Riondato is a Research Scientist in the Labs at Two Sigma Investments and a Visiting Assistant Professor in Computer Science at Brown University. His research focus is in algorithmic data science, developing theory and methods to extract the most useful information from large datasets, as fast as possible and in a statistically sound way. He obtained is PhD from Brown and held postdoc positions at Brown and Stanford. His works received the best student poster award at the 2014 SIAM International Conference on Data Mining (SDM) and the best student paper award at the 2016 ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD).
Faculty Host: Andy Pavlo