is a distributed streaming algorithm for estimating global and local triangle counts in graph streams.
processes and samples edges across multiple machines to reduce redundancy in computation and storage.
has the following advantages:
- Accurate: CoCoS produces up to 30X smaller estimation error than its competitors with similar speeds
- Fast: CoCoS runs in linear time up to 10.4X faster while giving more accurate estimates
- Theoretically Sound: CoCoS gives unbiased estimates.
is described in the following paper:
CoCoS: Fast and Accurate Distributed Triangle Counting in Graph Streams
Kijung Shin, Euiwoong Lee, Jinoh Oh, Mohammad Hammoud, and Christos Faloutsos
ACM Transactions on Knowledge Discovery from Data (TKDD) (Accepted)
The source code used in the paper is available. [Github Repository]