Practicably Boosting the Processing Performance of BFS-like Algorithms on Semi-External Graph System via I-O-Efficient Graph Ordering

Explore a 15-minute conference talk from FAST '22 that delves into boosting the processing performance of BFS-like algorithms on semi-external graph systems through I/O-efficient graph ordering. Learn about the challenges faced by external graph systems when processing large-scale graphs with billions of vertices and edges. Discover the innovative approach of I/O-Efficient Graph Ordering (IOE-Order), which comprises two main pre-processing steps: Breadth-First Degree-Second (BFDS) Ordering and Out-Degree Binning. Understand how these techniques improve I/O efficiency, enhance runtime graph processing, and offer flexibility in pre-caching vertices based on memory availability. Compare IOE-Order's efficiency and practicability to state-of-the-art pre-processing techniques for BFS-like algorithms, and gain insights into its lower pre-processing overhead and higher processing performance.

Intro
Semi-External Graph System
BFS-like Algorithms on Semi-External System
Existing Work for Optimizing BFS-like Algorithms
I/O Efficiency
Motivation
1/O-Efficient Graph Ordering (IOE-Order)
Out-Degree Binning (Conti.)
Evaluation Setup
Overall Comparison
Pre-processing Overhead
Non-BFS Evaluation
Conclusion