Some Novel Computational Models to Think About

on YouTube ↗31m

" summary

Surveys practical computation models and gives concrete payoffs: algorithms for frequency moments reach surprising low-space single-pass bounds while matching multiparty communication lower bounds; MapReduce and simple filtering primitives enable scalable inverted indexes and billion‑edge graph tasks with near‑linear speedups in practice; semi‑streaming captures single‑pass graph algorithms like connected components with polylog memory per machine; and the parameter server design actually runs large‑scale deep learning across many machines and delivers usable convergence and wall‑clock speedups.

AI-written summary · about

" chapters (15)

1. 0:00Intro
2. 0:58Frequency Moments
3. 4:32Data Stream
4. 6:19Communication Complexity
5. 8:00MapReduce
6. 10:32Simple MapReduce
7. 13:24Summary
8. 15:00Comments
9. 16:45Semistreaming
10. 19:51MapReduce Filters
11. 22:36Parameters Server
12. 25:29Millville
13. 26:13Connected Components
14. 27:19The Message
15. 29:01Questions

" related talks

• 30mThree Goals in Parallel Graph Computations: High Performance, High Productivity, and Reduced Comm...Aydin Buluç · Parallel and Distributed Algorithms for Inference and Optimization (Simons Institute, Oct. 21–24, 2013)
• 16mPreview: Cloud ComputingKshiteej Mahajan · OSDI '21 / USENIX ATC '21
• 53mMapReduce AlgorithmicsSergei Vassilvitskii · Parallel and Distributed Algorithms for Inference and Optimization (Simons Institute, Oct. 21–24, 2013)
• 28mCommunication Avoiding Algorithms for Linear Algebra and BeyondJim Demmel · Parallel and Distributed Algorithms for Inference and Optimization (Simons Institute, Oct. 21–24, 2013)
• 01h 20mAn Introduction to Distributed, Massively Parallel, and Local Computation AlgorithmsMohsen Ghaffari · Sublinear Algorithms Boot Camp 2024
• 50mBig Data on Smallish MachinesGuy Blelloch · Parallel and Distributed Algorithms for Inference and Optimization (Simons Institute, Oct. 21–24, 2013)
• 39mSketching and Randomization for Distributed Submodular and Coverage OptimizationVahab Mirrokni · Learning, Algorithm Design and Beyond Worst-Case Analysis
• 43mKeynote: Tiny Data Collectors, Vastly (...) & the Land of Tiny ChallengesAnna-Lito Michala · ElixirConf EU 2024