ThinkD (Think before you Discard)
is a streaming algorithm for triangle counting in a fully dynamic graph stream with edge additions and deletions.
estimates the counts of global and local triangles by making a single pass over the stream.
has the following advantages:
- Accurate: ThinkD is up to 4.3X more accurate than its best competitors within the same memory budget
- Fast: ThinkD is up to 2.2X faster for the same accuracy requirements
- Theoretically Sound: ThinkD always maintains unbiased estimates
is described in the following papers:
Think before You Discard: Accurate Triangle Counting in Graph Streams with Deletions
Kijung Shin, Jisu Kim, Bryan Hooi, and Christos Faloutsos
European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML/PKDD) 2018, Dublin, Ireland
[Paper] [Supplementary Document] [BIBTEX]
Fast, Accurate and Provable Triangle Counting in Fully Dynamic Graph Streams
Kijung Shin, Sejoon Oh, Jisu Kim, Bryan Hooi, and Christos Faloutsos
ACM Transactions on Knowledge Discovery from Data (TKDD) (Accepted)
The source code used in the paper is available. [Github Repository]