search

tannal / ohmywork

0 stars 0 forks source link

Pregel Algorithms for Graph Connectivity Problems with Performance Guarantees #56

Open tannal opened 7 months ago

tannal commented 7 months ago

https://www.vldb.org/pvldb/vol7/p1821-yan.pdf

tannal commented 3 months ago

The paper proposes Pregel algorithms with performance guarantees for three fundamental graph connectivity problems: connected components (CCs), biconnected components (BCCs), and strongly connected components (SCCs).

It introduces the concept of Practical Pregel Algorithms (PPAs) that satisfy strict performance constraints:

  1. Linear space usage
  2. Linear computation cost per iteration
  3. Linear communication cost per iteration

At most logarithmic number of iterations PPAs aim to ensure good performance and avoid ad hoc algorithm design.

tannal commented 3 months ago

https://research.google/pubs/pregel-a-system-for-large-scale-graph-processing/