Parallel Cluster-BFS and Applications to Shortest Paths

on YouTube ↗29m

" summary

Parallel cluster-BFS implements simultaneous BFS from a cluster by combining bitwise parallelism with thread-level parallelism, with work O(d m (k/w + 1)) and span O(d log n). An optimized C++ implementation on a 96-core machine processes 640 sources per graph (clusters size 64, diameter 2) and yields up to >1000x speedups and a ~500x geomean speedup versus running single-source BFSes; applied to landmark distance oracles it cuts preprocessing time and usually lowers distortion for the same ~1KB-per-vertex index.

AI-written summary · about

" chapters (9)

1. 0:00Parallel cluster-BFS intro
2. 1:25What is cluster-BFS
3. 6:45Parallelizing with bitwise & threads
4. 10:21Algorithm overview & optimizations
5. 13:12Theoretical guarantees
6. 16:07Approximate distance oracles
7. 18:22Experimental results
8. 21:14Scalability & performance
9. 24:03Future work & summary

" 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)
• 30mScalable Graph-Parallel Inference Algorithms and SystemsJoseph E. Gonzalez · Parallel and Distributed Algorithms for Inference and Optimization (Simons Institute, Oct. 21–24, 2013)
• 30mParallelization by ApproximationKanat Tangwongsan · Parallel and Distributed Algorithms for Inference and Optimization (Simons Institute, Oct. 21–24, 2013)
• 19mBeeping Shortest Paths via Hypergraph Bipartite DecompositionFabien Dufoulon, Yuval Emek, Ran Gelles · ITCS 2023
• 10mGraph Based Pipeline ParallelismSanket Purandare, Simon Fan · PyTorch Conference Europe 2026
• 20mPre-Select Static Caching and Neighborhood Ordering for BFS-like Algorithms on Disk-based Graph EnginesEunjae Lee, Junghyun Kim, Keunhak Lim, Sam H. Noh, Jiwon Seo · USENIX ATC '19
• 50mBig Data on Smallish MachinesGuy Blelloch · Parallel and Distributed Algorithms for Inference and Optimization (Simons Institute, Oct. 21–24, 2013)
• 53mMapReduce AlgorithmicsSergei Vassilvitskii · Parallel and Distributed Algorithms for Inference and Optimization (Simons Institute, Oct. 21–24, 2013)