Large-Scale Graph Processing on Emerging Storage Devices
summary
Claims a vertex-only partitioning that fits each destination partition in DRAM and replaces GraphBoost’s big external sort, cutting I/O by streaming sources and updating small in-memory destination blocks. Evaluation on a 48-core, 256 GB DRAM machine with NVMe SSDs and a 3.5B-vertex, 128B-edge web graph (≈2.7 TB edges) shows up to ~2× speedup versus a state-of-the-art external system; mirror maintenance costs are modest, about 8–12% of runtime, and preprocessing removes the need to sort all updates.
AI-written summary · about
chapters (14)
- 0:00Intro
- 0:48Large-Scale Graph Processing Challenges
- 2:11Fine-Grained Access in External Graph Processing
- 5:17Programming Model
- 6:20Prior External Graph Processing -- Graf Boost
- 9:58Scalability Issue
- 12:27Partitioning Graph Data
- 14:19Instead, We Propose a Partitioning for Vertex Data
- 16:29Execution Flow
- 19:25Updating Vertex Mirrors on Different Partitions
- 20:16Experimental Setup
- 21:00Performance Evaluation
- 22:49Execution Time Breakdown
- 23:25Concluding Remarks
related talks
09mEfficient Large Graph Processing with Chunk-Based Graph Representation Model
50mBig Data on Smallish Machines
20mGraphWalker: An I/O-Efficient and Resource-Friendly Graph Analytic System...
27mData @scale Seattle - Yucheng Low
39mThorny path to the Large Scale Graph Processing
21mSeraph: Towards Scalable and Efficient Fully-external Graph Computation via On-demand...
39mThorny path to the Large Scale Graph Processing
44mHow We Store and Analyze a Large Social Graph