Thorny path to the Large Scale Graph Processing
summary
Big graphs like the web hit sizes that break single servers — examples: Moscow road graph 250k nodes/460k edges, EU roads ~18M/42M, and web/facebook scales to ~1.5B vertices and ~1.5T edges; iterative algorithms force repeated disk checkpoints so systems adopt the Pregel superstep/message model. Open implementations include Giraph (Facebook scales experiments up to hundreds of billions of edges, message-passing, no locks, checkpointing on Hadoop) and single-machine GraphChi (40M users, triangle counting), while in-memory Spark GraphX trades persistence for much faster runs.
AI-written summary · about
chapters (18)
- 0:00Introduction to graphs
- 1:51Large graphs today
- 3:57Graph processing problems
- 8:13Vertex importance
- 10:19Parallel processing issues
- 12:04Pregel model for graphs
- 14:32Parallel approach problems
- 15:36Graph systems
- 17:43Giraph advantages
- 19:50Giraph scalability
- 22:58GraphLab library
- 24:45Comparison with Spark
- 25:50Single-computer graphs
- 28:15Graphs as tools
- 31:08Shortest paths in graphs
- 34:54Road network optimization
- 36:40Fault tolerance
- 37:46Summary and discussion
related talks
50mBig Data on Smallish Machines
27mData @scale Seattle - Yucheng Low
24mLarge Scale Graph Computation with Apache Giraph
43mBuilding Billion Node Graphs for Machine Learning
28mLarge Scale Graph Mining with Spark: What I learned from mapping 15 million websites
26mLarge Scale Graph Processing & Machine Learning Algorithms
56mGraph Analytic Systems
32mLarge-Scale Graph Processing on Emerging Storage Devices