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: hc52ec131ffcab524
Venue: VLDB
Year: 2020
Pagerank: 5.0610409e-05
Overall Rank: 10,202 | 31.41%
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
5,976	Theoretically and Practically Efficient Parallel Nucleus Decomposition	2022	VLDB	5.9300103e-05
7,997	ConnectIt: A Framework for Static and Incremental Parallel Graph Connectivity Algorithms	2021	VLDB	5.4105956e-05
9,064	A Design Space Exploration and Evaluation for Main-Memory Hash Joins in Storage Class Memory	2023	VLDB	5.2283159e-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
100	Truss Decomposition in Massive Networks	2012	VLDB	0.00033977856
184	Querying K-Truss Community in Large and Dynamic Graphs	2014	SIGMOD	0.00026100147
239	The Ubiquity of Large Graphs and Surprising Challenges of Graph Processing	2018	VLDB	0.000235107
443	Efficient Subgraph Matching on Billion Node Graphs	2012	VLDB	0.00018197688
490	TurboISO: Towards UltraFast and Robust Subgraph Isomorphism Search in Large Graph Databases	2013	SIGMOD	0.00017438618
631	Persistent B+-Trees in Non-Volatile Main Memory	2015	VLDB	0.0001541723
668	Rethinking Database Algorithms for Phase Change Memory	2011	CIDR	0.00014964806
964	BzTree: A High-Performance Latch-free Range Index for Non-Volatile Memory	2018	VLDB	0.00012810196
1,027	GraMI: Frequent Subgraph and Pattern Mining in a Single Large Graph	2014	VLDB	0.00012422544
1,282	Managing Non-Volatile Memory in Database Systems	2018	SIGMOD	0.00011210073
1,443	Local Algorithms for Hierarchical Dense Subgraph Discovery	2019	VLDB	0.00010635542
1,648	Distance-generalized Core Decomposition	2019	SIGMOD	9.9863775e-05
2,038	Write-limited sorts and joins for persistent memory	2014	VLDB	9.1498806e-05
3,244	Single Machine Graph Analytics on Massive Datasets Using Intel Optane DC Persistent Memory	2020	VLDB	7.4970778e-05
3,496	How to Build a Non-Volatile Memory Database Management System	2017	SIGMOD	7.2557397e-05
3,688	Parallel Local Graph Clustering	2016	VLDB	7.095356e-05
4,440	Memory Management Techniques for Large-Scale Persistent-Main-Memory Systems	2017	VLDB	6.5995676e-05
5,417	Theoretically-Efficient and Practical Parallel DBSCAN	2020	SIGMOD	6.138409e-05
6,957	2-3 Cuckoo Filters for Faster Triangle Listing and Set Intersection	2017	PODS	5.6341313e-05
7,286	Experimental Analysis of Distributed Graph Systems	2018	VLDB	5.565865e-05

Semantically Similar Papers

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