[Dmbu-l] Data Group Seminar
cmav at bu.edu
Thu Sep 29 23:05:03 EDT 2016
In case you didn't receive the previous email.
> Data Seminar
> "TRIÈST: Counting Local and Global Triangles in Fully-dynamic Streams with Fixed Memory Size
> Lorenzo De Stefani, Brown University
> Friday, September 30, 2016 at 10:30am in Hariri Seminar Room
> Speaker: Lorenzo De Stefani, Brown University
> Title: TRIÈST: Counting Local and Global Triangles in Fully-dynamic Streams with Fixed Memory Size
> 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 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.
> 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."
> This is joint work with Alessandro Epasto (Google Research NY), Matteo Riondato (Two Sigma Investments, LP) and Eli Upfal (Brown University).
> The paper was recently presented at SIG KDD 2016 were received the Best Student Paper Award.
> The full paper, code and other infos are available at http://bigdata.cs.brown.edu/triangles.html
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Dmbu-l