[Dmbu-l] Data Group Seminar

Harshal Chaudhari harshal at bu.edu
Fri Sep 30 09:38:29 EDT 2016


*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

-- Harshal
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs-mailman.bu.edu/pipermail/dmbu-l/attachments/20160930/64d70c40/attachment.html>


More information about the Dmbu-l mailing list