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

Posted on July 18, 2017

Authors: Matteo Riondato (Two Sigma), Lorenzo De Stefani, Alessandro Epasto, Eli Upfal

Published in: ACM Transactions on Knowledge Discovery from Data, 11(4):43:1–43:50

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 require hard-to-choose parameters (e.g., a fixed sampling probability) and other no guarantees on the amount of memory they use. We analyze the variance of the estimations and show novel concentration bounds for these quantities. Our experimental results on very large graphs demonstrate that TRIÈST outperforms state-of-the-art approaches in accuracy and exhibits a small update time.

DOI: https://doi.org/10.1145/3059194

Download PDF — 1.74 MB
References

This is the author’s version of the work. It is posted here for your personal use. Not for redistribution. The definitive Version of Record was published in the ACM Transactions on Knowledge Discovery from Data (TKDD). http://dx.doi.org/10.1145/3059194.

The views expressed above are not necessarily the views of Two Sigma Investments, LP or any of its affiliates (collectively, “Two Sigma”).  The information presented above is only for informational and educational purposes and is not an offer to sell or the solicitation of an offer to buy any securities or other instruments. Additionally, the above information is not intended to provide, and should not be relied upon for investment, accounting, legal or tax advice. Two Sigma makes no representations, express or implied, regarding the accuracy or completeness of this information, and the reader accepts all risks in relying on the above information for any purpose whatsoever. Click here for other important disclaimers and disclosures.

Related Articles

Life at Two Sigma

We’re rigorous about our work and developing our people.

Learn More