Using Set Cover to Optimize a Large-Scale Low Latency Distributed Graph
summary
LinkedIn converts real-time graph traversal into set intersections and builds a network cache service (NCS) that merges partial results; a modified greedy set cover uses a reverse mapping of partition→physical machines and picks a random input partition each iteration so intersections touch only its replica nodes. Deployed on half the NCS nodes as ~100 lines of Scala, it cuts second-degree cache creation 99th-percentile by ~40%, graph-distance 99th-percentile by ~25%, reduces outbound traffic ~40% and runs 1.5–2× the optimal result set.
AI-written summary · about
chapters (11)
- 0:00Start
- 0:25Outline
- 3:02Distributed Graph Architecture Diagram
- 5:08Linkedin's Distributed Graph Infrastructure
- 5:40Graph Distance Queries and Second Degree Creation
- 7:26The Scaling Problem Illustrated
- 9:40Set Cover Problem
- 12:00Modified Set Cover Algorithm Example Cont.
- 14:39Modified Set Cover Algorithm Example Solution
- 15:17Evaluation
- 17:51Conclusions and Future Work
related talks
27mData @scale Seattle - Yucheng Low
17mBGL: GPU-Efficient GNN Training by Optimizing Graph Data I/O and Preprocessing
24mGLogS: Interactive Graph Pattern Matching Query At Large Scale
50mBig Data on Smallish Machines
32mLarge-Scale Graph Processing on Emerging Storage Devices
18mEhtsham Elahi, Senior Research Engineer, Netflix @ MLconf SEA
39mThorny path to the Large Scale Graph Processing
41mScalable Spatial Scan Statistics with Coresets