Parallelization by Approximation

on YouTube ↗30m

" summary

Shows how greedy set cover becomes parallel by geometric bucketing plus a near-maximal independent-set routine that uses random priorities, yielding essentially log n approximation with linear work and polylog depth and cache cost comparable to sorting m. Implements reservoir sampling and batch (bulk) processing. On real data (1.4B elements, 500M sets) it gives 9–23.4× speedup on 40 cores and ≈14× faster than prior greedy; streaming triangle counter processes up to 5B edges, ≈8 million edges per second with <5% error using ~2M estimators.

AI-written summary · about

" chapters (19)

1. 0:00Intro
2. 1:55[Unweighted] Set Cover
3. 2:29Greedy Set Cover [Johnson 74, Chvatal79]
4. 3:32Parallelizing Greedy Set Cover
5. 4:39Idea I: Geometric-Scale Bucketing handle sets in the same bucket altogether
6. 5:53Idea II: Bulk Sieving
7. 7:03Parallel Greedy Set Cover
8. 8:30Set Cover Experiments
9. 8:48Performance: Set Cover
10. 9:57A Simple Linear-Work MaNIS
11. 12:17Streaming graph: = a sequence of edges "flying" by
12. 14:25How to be lean? a recipe for designing streaming algorithms
13. 15:32A straw man solution: Step 1: Build an estimator with the right expectation
14. 16:33Our Solution: Neighborhood Sampling Pick a random triangle from a stream of edges
15. 19:15Realizing Neighborhood Sampling
16. 20:32How to be fast? Simple Implementation
17. 21:55Sketch: Picking Level-2 Edges
18. 23:19Experimental Findings: Summary
19. 24:29Extensions

" related talks

• 39mSketching and Randomization for Distributed Submodular and Coverage OptimizationVahab Mirrokni · Learning, Algorithm Design and Beyond Worst-Case Analysis
• 31mNearest Neighbor Based Greedy Coordinate DescentPradeep Ravikumar · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 29mSampling Algorithms for Combinatorial Pure ExplorationAnupam Gupta · Optimization, Statistics and Uncertainty
• 47mSuccinct Representations and Efficient Algorithms Based on Linear ProgrammingSudipto Guha · Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)
• 17mSolving Max-Min Fair Resource Allocations Quickly on Large GraphsUmesh Krishnaswamy, Himanshu Raj, Santiago Segarra, Pooria Namyar, Behnaz Arzani, Srikanth Kandula, Daniel Crankshaw, Ramesh Govindan · 21st USENIX Symposium on Networked Systems Design and Implementation (NSDI '24)
• 01h 00mContinuous Methods 4Maryam Fazel, Lorenzo Orecchia, Stefanie Jegelka, Reza Eghbali · Bridging Continuous and Discrete Optimization Boot Camp 2017
• 41mScalable Spatial Scan Statistics with CoresetsJeff Phillips · Sublinear Algorithms and Nearest-Neighbor Search
• 35mDistributed Vertex Cover ReconfigurationYannic Maus, Keren Censor-Hillel, Shahar Romem-Peled, Tigran Tonoyan · ITCS 2022