Thorny path to the Large Scale Graph Processing
summary
Shows concrete scales and tooling: a Moscow road graph of 250k nodes, 460k edges, an EU road graph on the order of 18M nodes, 42M edges, and web/social graphs up to ~1.5 billion nodes and ~1.5 trillion edges. Describes Pregel’s superstep/checkpoint model, explains why MapReduce is slow for iterative graph work, reports Facebook/Giraph experiments scaling to hundreds of billions of edges with near-linear worker scaling, and shows GraphChi handling ~40M-node datasets on a single laptop while counting triangles.
AI-written summary · about
chapters (21)
- 0:00Introduction
- 1:51Big data and graphs
- 3:57Graph processing problems
- 8:13Vertex importance
- 10:19Parallel graph processing
- 12:04Pregel model and supersteps
- 14:32Parallel approach problems
- 15:36Graph systems: Giraph and others
- 17:43Giraph advantages
- 19:50Giraph with ZooKeeper
- 20:51Scaling Giraph
- 22:15Giraph experiments
- 22:58GraphLab library
- 23:41Spark in graph processing
- 24:45Single-machine graph computing
- 27:34Graph applications
- 28:15Road graphs specifics
- 30:45Shortest path algorithms
- 34:13Algorithm optimization
- 36:40Computation errors and resilience
- 37:46Conclusion
related talks
27mData @scale Seattle - Yucheng Low
50mBig Data on Smallish Machines
43mBuilding Billion Node Graphs for Machine Learning
24mLarge Scale Graph Computation with Apache Giraph
28mLarge Scale Graph Mining with Spark: What I learned from mapping 15 million websites
26mLarge Scale Graph Processing & Machine Learning Algorithms
30mScalable Graph-Parallel Inference Algorithms and Systems
20mGraphWalker: An I/O-Efficient and Resource-Friendly Graph Analytic System...