YoVDO

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

Offered By: USENIX via YouTube

Tags

FAST (File and Storage Technologies) Courses Breadth-First Search (BFS) Courses Algorithm Optimization Courses

Course Description

Overview

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.

Syllabus

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


Taught by

USENIX

Related Courses

Understanding the Robustness of SSDs under Power Fault
USENIX via YouTube
BetrFS - A Right-Optimized Write-Optimized File System
USENIX via YouTube
F2FS - A New File System for Flash Storage
USENIX via YouTube
DNA Data Storage and Near-Molecule Processing for the Yottabyte Era
USENIX via YouTube
FAST '21 Work-in-Progress Reports
USENIX via YouTube