Oasis: An Out-of-core Approximate Graph System via All-Distances Sketches
summary
Oasis implements an out‑of‑core All‑Distances Sketch pipeline that builds ADS on storage using partitioning, equal‑size blocks and a duplicate active data separation file so iterations read only hot sketches; it further uses selective ads accessing by scanning much‑smaller edge blocks to decide which ADS to load. The system reduces ADS memory use by about 10×, slows end‑to‑end construction vs fully in‑memory by roughly 2×, and trades a slight accuracy drop for practical scalability.
AI-written summary · about
chapters (12)
- 0:00Oasis introduction
- 2:22Approximate graph processing
- 5:39All-Distance Sketches theory
- 7:26ADS construction workflow
- 8:52Oasis system architecture
- 9:56Memory-efficient ADS partitioning
- 11:41Active data separation
- 13:05Selective ADS accessing
- 14:10ADS estimation framework
- 15:53Evaluation results
- 17:42Performance trade-offs
- 18:46Summary of Oasis
related talks
24mSketching Algorithms: Making Sense of Big Data in a Single Stroke
32mLarge-Scale Graph Processing on Emerging Storage Devices
20mGraphWalker: An I/O-Efficient and Resource-Friendly Graph Analytic System...
18mSOWalker: An I/O-Optimized Out-of-CoreGraph Processing System for Second-Order...
01h 13mSketching High-Dimensional Data
28mAerospike's Journey Through Innovations, Sustainability, and Roadmap
30mAerospike Graph: Massively Scalable, High Performance
22mOSCA: An Online-Model Based Cache Allocation Scheme in Cloud Block Storage Systems