Главная
Study mode:
on
1
Intro
2
Semi-External Graph System
3
BFS-like Algorithms on Semi-External System
4
Existing Work for Optimizing BFS-like Algorithms
5
I/O Efficiency
6
Motivation
7
1/O-Efficient Graph Ordering (IOE-Order)
8
Out-Degree Binning (Conti.)
9
Evaluation Setup
10
Overall Comparison
11
Pre-processing Overhead
12
Non-BFS Evaluation
13
Conclusion
Description:
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.

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

USENIX
Add to list
0:00 / 0:00