BEGIN:VCALENDAR
VERSION:2.0
PRODID:ECMLPKDD-MB
BEGIN:VEVENT
DTSTAMP;TZID=Europe/Dublin:20180826T200000
UID:_ecmlpkdd_8
DTSTART;TZID="Europe/Dublin":20180911T142000
DTEND;TZID="Europe/Dublin":20180911T144000
LOCATION:Hogan Mezz 2
TRANSP:TRANSPARENT
SEQUENCE:1
DESCRIPTION:Given a stream of edge additions and deletions, how can we estimate the count of triangles in it? If we can store only a subset of the edges, how can we obtain unbiased estimates with small variances? Counting triangles (i.e., cliques of size three) in a graph is a classical problem with applications in a wide range of research areas, including social network analysis, data mining, and databases. Recently, streaming algorithms for triangle counting have been extensively studied since they can naturally be used for large dynamic graphs. However, existing algorithms cannot handle edge deletions or suer from low accuracy. Can we handle edge deletions while achieving high accuracy? We propose ThinkD, which accurately estimates the counts of global triangles (i.e., all triangles) and local triangles associated with each node in a fully dynamic graph stream with edge additions and deletions. Compared to its best competitors, ThinkD is (a) Accurate: up to 4.3X_x0002_ more accurate within the same memory budget, (b) Fast: up to 2.2X_x0002_ faster for the same accuracy requirements, and (c) Theoretically sound: always maintaining unbiased estimates with small variances.
SUMMARY:Think before You Discard: Accurate Triangle Counting in Graph Streams with Deletions
CLASS:PUBLIC
END:VEVENT
END:VCALENDAR