Implement trifly algroithm

vasia / gelly-streaming

An experimental Graph Streaming API for Apache Flink

Apache License 2.0

140 stars 44 forks source link

Implement trifly algroithm #44

Open jigsaw373 opened 4 years ago

jigsaw373 commented 4 years ago

The most powerful algorithm for triangle count based on Trifly article

Tri-Fly:

Accurate: yields up to 4.5X smaller estimation error
Fast: runs up to 8.8X faster with linear scalability
Theoretically sound: gives unbiased estimates with smaller variances

vasia commented 4 years ago

Hi @jigsaw373, Many thanks for the PR!

Could you add a short description on how this algorithm works and why it is a good fit for gelly-streaming? I would also be of great help if you could squash your commits to enable faster reviewing.

Thanks, -V.

jigsaw373 commented 4 years ago

Done! It could be a start for implementing limited resources ideas in the gelly stream, If you want we could share some charts to compare between these two methods with you to clarify this idea on real and large datasets!

jigsaw373 commented 3 years ago

@vasia