Sage: Parallel Semi-Asymmetric Graph Algorithms for NVRAMs

Summary: Proposes PSAM: graph data in read-only NVRAM, mutable state in DRAM, eliminating NVRAM writes for parallel graph analytics. Sage implements provably-efficient PSAM algorithms for many problems; on a 3.5B-vertex, 128B-edge Hyperlink graph with Optane, it beats prior NVRAM systems and nearly matches DRAM runtimes. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 12254
Venue: VLDB
Year: 2020
Pagerank: 5.1772034e-05
Overall Rank: 10,011 | 31.32%
DOI: 10.14778/3397230.3397251

Incoming Non-self Citations Over Time

Authors

1. Laxman Dhulipala (Carnegie Mellon University)
2. Charles McGuffey (Carnegie Mellon University)
3. Hongbo Kang (Tsinghua University)
4. Yan Gu (University of California Riverside)
5. Guy E. Blelloch (Carnegie Mellon University)
6. Phillip B. Gibbons (Carnegie Mellon University)
7. Julian Shun (Massachusetts Institute of Technology)

BibTeX Citation

@article{dhulipala_vldb20,
        title = {{Sage: Parallel Semi-Asymmetric Graph Algorithms for NVRAMs}},
        author = {Dhulipala, Laxman and McGuffey, Charles and Kang, Hongbo and Gu, Yan and Blelloch, Guy E. and Gibbons, Phillip B. and Shun, Julian},
        journal = {PVLDB},
        series = {{VLDB} '20},
        volume = {13},
        number = {9},
        pages = {1598--1613},
        doi = {10.14778/3397230.3397251},
        url = {https://doi.org/10.14778/3397230.3397251},
        year = {2020}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,368	Theoretically and Practically Efficient Parallel Nucleus Decomposition	2022	VLDB	5.8975125e-05
7,862	ConnectIt: A Framework for Static and Incremental Parallel Graph Connectivity Algorithms	2021	VLDB	5.5302333e-05
8,904	A Design Space Exploration and Evaluation for Main-Memory Hash Joins in Storage Class Memory	2023	VLDB	5.3483178e-05

Outgoing Citations (Sorted by Pagerank)

Showing 20 of 20 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
102	Truss Decomposition in Massive Networks	2012	VLDB	0.00034255289
189	Querying K-Truss Community in Large and Dynamic Graphs	2014	SIGMOD	0.00026114928
264	The Ubiquity of Large Graphs and Surprising Challenges of Graph Processing	2018	VLDB	0.00022980015
442	Efficient Subgraph Matching on Billion Node Graphs	2012	VLDB	0.00018398144
485	TurboISO: Towards UltraFast and Robust Subgraph Isomorphism Search in Large Graph Databases	2013	SIGMOD	0.00017717377
621	Persistent B+-Trees in Non-Volatile Main Memory	2015	VLDB	0.00015695264
658	Rethinking Database Algorithms for Phase Change Memory	2011	CIDR	0.0001523554
948	BzTree: A High-Performance Latch-free Range Index for Non-Volatile Memory	2018	VLDB	0.0001303916
1,085	GraMI: Frequent Subgraph and Pattern Mining in a Single Large Graph	2014	VLDB	0.0001225302
1,258	Managing Non-Volatile Memory in Database Systems	2018	SIGMOD	0.00011438197
1,416	Local Algorithms for Hierarchical Dense Subgraph Discovery	2019	VLDB	0.00010839488
1,640	Distance-generalized Core Decomposition	2019	SIGMOD	0.00010153865
1,996	Write-limited sorts and joins for persistent memory	2014	VLDB	9.3396464e-05
3,175	Single Machine Graph Analytics on Massive Datasets Using Intel Optane DC Persistent Memory	2020	VLDB	7.6656917e-05
3,455	How to Build a Non-Volatile Memory Database Management System	2017	SIGMOD	7.4000022e-05
3,616	Parallel Local Graph Clustering	2016	VLDB	7.2559471e-05
4,647	Memory Management Techniques for Large-Scale Persistent-Main-Memory Systems	2017	VLDB	6.5879506e-05
5,294	Theoretically-Efficient and Practical Parallel DBSCAN	2020	SIGMOD	6.2790627e-05
6,855	2-3 Cuckoo Filters for Faster Triangle Listing and Set Intersection	2017	PODS	5.753175e-05
7,447	Experimental Analysis of Distributed Graph Systems	2018	VLDB	5.6149936e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,456	LSMGraph: A High-Performance Dynamic Graph Storage System with Multi-Level CSR	2024	SIGMOD
2	4,323	TurboGraph++: A Scalable and Fast Graph Analytics System	2018	SIGMOD
3	1,911	Fast Iterative Graph Computation with Block Updates	2013	VLDB
4	4,787	Systems for Big-Graphs	2014	VLDB
5	6,490	CAVE: Concurrency-Aware Graph Processing on SSDs	2024	SIGMOD
6	11,096	A Single Machine System for Querying Big Graphs with PRAM	2025	VLDB
7	436	Trinity: A Distributed Graph Engine on a Memory Cloud	2013	SIGMOD
8	9,281	Sage: A System for Uncertain Network Analysis	2022	VLDB
9	3,175	Single Machine Graph Analytics on Massive Datasets Using Intel Optane DC Persistent Memory	2020	VLDB
10	7,491	Self-adaptive Graph Traversal on GPUs	2021	SIGMOD