Algorithms on billion-scale graph using 10GB RAM: I love DataFusion
4 hours ago
- Implemented graph map-reduce using Apache DataFusion to handle billion-scale graph analytics with low memory.
- Offloaded computation to disk using bulk scans, enabling PageRank on 1B edges with 5GB memory and WCC on 2B edges with 10GB memory.
- Algorithms based on Pregel (PageRank) and in-database connected component analysis (WCC), using joins and aggregations.
- Results match ground truth; code is open-source on GitHub (graphframes-rs) written in Rust without LLM assistance.
- Challenges: deadlocks from FairSpillPool, need for pre-sorting in SMJ, potential optimizations like range partitioning and fusing join+agg.
- Demonstrates that laptop can replace Spark/GraphFrames for large-scale graph analytics.