Tri-Fly: Distributed Estimation of Global and Local Triangle Counts in Graph Streams

Overview

Tri-Fly is a distributed streaming algorithm for global and local triangle counting in graph streams.
Tri-Fly has the following advantages compared to baselines:

• Accurate: Tri-Fly produces up to 4.5X smaller estimation error
• Fast: Tri-Fly runs in linear time up to 8.8X faster
• Theoretically Sound: Tri-Fly gives unbiased estimates with variances inversely proportional to the number of machines

Paper

Tri-Fly is described in the following paper:

• Tri-Fly: Distributed Estimation of Global and Local Triangle Counts in Graph Streams
  Kijung Shin, Mohammad Hammoud, Euiwoong Lee, Jinoh Oh, and Christos Faloutsos
  22nd Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD) 2018, Melbourne, Australia (To Appear)
  [PDF] [Supplementary Document] [BIBTEX]

Code

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

Datasets