CoCoS: Fast and Accurate Distributed Triangle Counting in Graph Streams

Overview

CoCoS is a distributed streaming algorithm for estimating global and local triangle counts in graph streams.
CoCoS processes and samples edges across multiple machines to reduce redundancy in computation and storage.
CoCoS 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.

Paper

CoCoS 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)
  [PDF] [BIBTEX]
  

Code

The source code used in the paper is available. [Github Repository]

Datasets

People

• Kijung Shin (KAIST)
• Euiwoong Lee (University of Michigan)
• Jinhoh Oh (Adobe Systems)
• Mohammad Hammoud (CMU at Qatar)
• Christos Faloutsos (CMU)