MapReduce Algorithmics

on YouTube ↗53m

" summary

MapReduce/Hadoop and related systems follow a BSP (Bulk Synchronous Parallel) model so algorithms must balance rounds and max per‑round work; with terabyte+ inputs even n·√n is infeasible and n log n may still be slow. Practical fixes shown: BSP underlies MapReduce and admits checkpointing and speculative copies; reordering (distributed transpose) uses linear communication; a k‑means D^2 coreset sampling gives constant‑factor approximations after oversampling (K→K+√K) and can be done in constant rounds by parallel oversampling; sampling+prune yields maximal matchings that shrink to O(n) edges in constant rounds given slightly superlinear memory; triangle counting requires separating low‑degree and high‑degree nodes with a √m threshold to avoid stragglers.

AI-written summary · about

" chapters (32)

1. 0:00Intro
2. 0:44What is Big Data?
3. 1:15Properties
4. 3:16Shape of Big Data
5. 3:30Big Data Shape Test
6. 5:56Big Data Wrangling: Outline
7. 6:29Parallelism To the Rescue!
8. 8:01BSP (Valiant '90)
9. 10:10Data Centers: the horrible truth
10. 11:33Modeling: BSP
11. 13:21Parallel Parameters
12. 14:29Systems Trade-offs
13. 16:12MapReduce Modeling
14. 19:00MapReduce Communication
15. 20:59MapReduce Algorithmics
16. 22:16Algorithmics: reordering
17. 24:19Data Shape: warm-up
18. 25:57Connected Components
19. 27:11Algorithm Execution
20. 29:07Algorithmics: coresets
21. 30:48Coreset Intuition
22. 32:56k-means clustering
23. 34:06Parallel Coreset Construction
24. 35:50Non Geometric Coresets
25. 36:44Warmup: Maximal Matchings
26. 37:42Analysis
27. 40:43Algorithmics: Load Balancing
28. 43:24How to Count Triangles
29. 47:01Dealing with Skew
30. 49:09Does it make a difference?
31. 50:12Final Parallel Algorithm
32. 51:02Conclusion

" related talks

• 10mMapReduce in 10 MinutesEvan Smith · PyOhio 2020
• 39mSketching and Randomization for Distributed Submodular and Coverage OptimizationVahab Mirrokni · Learning, Algorithm Design and Beyond Worst-Case Analysis
• 31mSome Novel Computational Models to Think AboutD Sivakumar · Information Theory in Complexity Theory and Combinatorics 2015
• 24mLarge Scale Graph Computation with Apache GiraphJakob Homan · Berlin Buzzwords 2012
• 01h 20mAn Introduction to Distributed, Massively Parallel, and Local Computation AlgorithmsMohsen Ghaffari · Sublinear Algorithms Boot Camp 2024
• 47mMassively Parallel Evaluation of Relational Queries IXiao Hu, Paris Koutris · Fine-Grained Complexity, Logic, and Query Evaluation 2023
• 01h 05mGraph Algorithms in the MPC ModelSlobodan Mitrovic · Sublinear Algorithms Boot Camp 2024
• 25mMergeable Summaries for High Scale, High Cardinality AnalyticsPeter Ballis · Systems @Scale Spring 2021