Practicably Boosting the Processing Performance of BFS-like Algorithms...
summary
Builds an ordering called IOOrder that combines a BFS-from-high-degree reordering (BFDS ordering), an exponential-size binning layout (auto-beam) and a cheap greedy static-cache filler to reduce SSD I/O for BFS-like traversals. Implemented inside a semi‑external graph engine and measured on an SSD, the paper reports the prior degree-based “anode” achieves only 42% IO efficiency, the greedy preload needs heavy preprocessing, while IOOrder speeds BFS-like jobs by about 18.8% on average and its preprocessing is 32.9× faster than anode+GPS.
AI-written summary · about
chapters (13)
- 0:00Intro
- 0:21Semi-External Graph System
- 1:23BFS-like Algorithms on Semi-External System
- 2:45Existing Work for Optimizing BFS-like Algorithms
- 4:46I/O Efficiency
- 5:45Motivation
- 6:461/O-Efficient Graph Ordering (IOE-Order)
- 10:15Out-Degree Binning (Conti.)
- 11:22Evaluation Setup
- 12:18Overall Comparison
- 13:15Pre-processing Overhead
- 13:42Non-BFS Evaluation
- 14:38Conclusion
related talks
20mPre-Select Static Caching and Neighborhood Ordering for BFS-like Algorithms on Disk-based Graph Engines
20mGraphWalker: An I/O-Efficient and Resource-Friendly Graph Analytic System...
01h 00mGraph Mastery to AI
45mBeyond Lists: High Performance Data Structures
48mTricks from in-memory databases
30mDeveloping IO Prefetching for Postgres
35mFast on paper, slow in reality: what we got wrong about performance
17mPlanB: Efficient Software IPv6 Lookup with Linearized B+-Tree