Big Data on Smallish Machines
Talkat Parallel and Distributed Algorithms for Inference and Optimization (Simons Institute, Oct. 21–24, 2013) · 2013-10-21..10-24·
summary
Argues that many “big” graphs actually fit on single shared‑memory servers: 6.6 billion edges fits on a $20k, 64‑core, 2 TB server and simple graph compression yields roughly 10× smaller storage (about one byte per edge). Delivers a lightweight C++ framework, Ligra: 1,500 lines C++, outperforms many graph libraries on 40 cores vs 240 cores (BFS 4–5× faster, near‑perfect PageRank scaling). Provides a disk‑based laptop prototype that processes billion‑edge graphs at ~30–40× slower but practical for small machines.
AI-written summary · about
chapters (21)
- 0:00Start
- 2:33Why use Large Clusters
- 6:03Large Data (Graphs) Web graph (centered around Wikipedia)
- 8:12Large Text
- 13:20Why Shared Memory
- 14:33Parallel Quicksort
- 16:38Quicksort Complexity
- 19:44Cover Trees
- 20:30Suffix Trees
- 22:39Ligra Interface
- 29:08Comparison to other systems
- 30:21Comparison to other graph processing systems
- 34:43Disk-Based Graph Algorithms
- 35:58PSW: Loading Sub-graph
- 37:26Experiment Setting
- 38:10PowerGraph Comparison
- 39:09Hybrid Approach
- 40:11Compressing Graphs
- 42:00Renumbering with Edge Separators
- 42:58Compressed Adjacency Tables
- 44:37Bits per edge for various graphs
related talks
27mData @scale Seattle - Yucheng Low
39mThorny path to the Large Scale Graph Processing
32mLarge-Scale Graph Processing on Emerging Storage Devices
39mThorny path to the Large Scale Graph Processing
09mEfficient Large Graph Processing with Chunk-Based Graph Representation Model
29mTed Willke, Senior Principal Engineer & GM, Datacenter Group, Intel
20mGraphWalker: An I/O-Efficient and Resource-Friendly Graph Analytic System...
13mMarius: Learning Massive Graph Embeddings on a Single Machine