Pre-Select Static Caching and Neighborhood Ordering for BFS-like Algorithms on Disk-based Graph Engines
Talkat USENIX ATC '19 · on Thursday, 2019-07-11· at 12:15· USENIX ATC Track II: Grand Ballroom VII–IX·
summary
Proposes a pre-selected in-memory static cache called Basc that stores chosen vertices' edge lists throughout traversal and an I/O-cost-driven graph reorder called Norder that reorders on-disk adjacency to cut random reads. Implements both on two disk-based graph engines and measures on five real-world graphs including Twitter (1.9 billion edges); reports collective, substantial speedups for BFS-like algorithms, with analyses showing reduced page reads and higher cache hit rates.
AI-written summary · about
chapters (9)
- 0:00Static caching for BFS-like
- 2:24Pre-select static caching
- 5:03Neighborhood ordering in graphs
- 8:05Greedy heuristics for performance
- 10:23Benchmarking results
- 13:19Real-world case studies
- 16:12Challenges and limitations
- 17:42Future directions
- 19:13Q&A
related talks
15mPracticably Boosting the Processing Performance of BFS-like Algorithms...
09mEfficient Large Graph Processing with Chunk-Based Graph Representation Model
50mBig Data on Smallish Machines
29mParallel Cluster-BFS and Applications to Shortest Paths
01h 00mGraph Mastery to AI
52mEnhance your work with graph database
30mCaching for Speed: Practical Performance Optimization in OpenSearch & Lucene
38mModern B-Tree techniques