Revisiting the Design of In-Memory Dynamic Graph Storage

Summary: Proposes a common abstraction and test framework to compare in-memory dynamic graph storage (LLAMA, Aspen, LiveGraph, Teseo, Sortledton) for read/write, space, and concurrency. Shows large memory overhead (Aspen 3.3–10.8x CSR; fine-grained 4.1–8.9x), architecture-aware bottlenecks, and high-degree vertex contention, suggesting future directions. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 7063
Venue: SIGMOD
Year: 2025
Pagerank: 4.545679e-05
Overall Rank: 8,267 | 42.49%
DOI: 10.1145/3709720

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,082	Gem: Scalable Monotonic Graph Processing Beyond Billion-Scale on a Single Machine	2026	SIGMOD	4.1945683e-05
10,161	Enabling Efficient Direct Update on Rule-Based Compressed Graph	2026	SIGMOD	4.1945683e-05
10,200	RadixGraph: A Fast, Space-Optimized Data Structure for Dynamic Graph Storage	2026	SIGMOD	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 25 of 25 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
4	Pregel: A System for Large-Scale Graph Processing	2010	SIGMOD	0.0019005923
289	High-Performance Concurrency Control Mechanisms for Main-Memory Databases	2012	VLDB	0.00028938503
331	The Ubiquity of Large Graphs and Surprising Challenges of Graph Processing	2018	VLDB	0.00027214222
342	EmptyHeaded: A Relational Engine for Graph Processing	2016	SIGMOD	0.00026795977
419	Fast Serializable Multi-Version Concurrency Control for Main-Memory Database Systems	2015	SIGMOD	0.00023720338
444	Parallelizing Sequential Graph Computations	2017	SIGMOD	0.00022987918
536	The LDBC Social Network Benchmark: Interactive Workload	2015	SIGMOD	0.00020722862
635	Staring into the Abyss: An Evaluation of Concurrency Control with One Thousand Cores	2015	VLDB	0.00018879031
1,426	LiveGraph: A Transactional Graph Storage System with Purely Sequential Adjacency List Scans	2020	VLDB	0.00012050977
1,432	An Empirical Evaluation of In-Memory Multi-Version Concurrency Control	2017	VLDB	0.00012017544
1,973	Speeding Up Set Intersections in Graph Algorithms using SIMD Instructions	2018	SIGMOD	9.8913631e-05
2,200	LDBC Graphalytics: A Benchmark for Large-Scale Graph Analysis on Parallel and Distributed Platforms	2016	VLDB	9.3075881e-05
2,862	An Experimental Study of Bitmap Compression vs. Inverted List Compression	2017	SIGMOD	7.9898539e-05
2,905	Teseo and the Analysis of Structural Dynamic Graphs	2021	VLDB	7.9352789e-05
2,962	Kuzu* Graph Database Management System	2023	CIDR	7.8101752e-05
3,366	An Adaptive Packed-Memory Array	2006	PODS	7.1726818e-05
3,668	The LDBC Social Network Benchmark: Business Intelligence Workload	2023	VLDB	6.8591612e-05
3,729	Sortledton: a Universal, Transactional Graph Data Structure	2022	VLDB	6.8133526e-05
4,096	RisGraph: A Real-Time Streaming System for Evolving Graphs to Support Sub-millisecond Per-update Analysis at Millions Ops/s	2021	SIGMOD	6.4555664e-05
4,236	Terrace: A Hierarchical Graph Container for Skewed Dynamic Graphs	2021	SIGMOD	6.3335374e-05
5,030	Nanosecond Indexing of Graph Data With Hash Maps and VLists	2019	SIGMOD	5.7501994e-05
5,231	ByteGraph: A High-Performance Distributed Graph Database in ByteDance	2022	VLDB	5.6145466e-05
7,375	BG3: A Cost Effective and I/O Efficient Graph Database in ByteDance	2024	SIGMOD	4.7491278e-05
7,769	GraphZeppelin: Storage-Friendly Sketching for Connected Components on Dynamic Graph Streams	2022	SIGMOD	4.6562896e-05
9,173	HERO: A Hierarchical Set Partitioning and Join Framework for Speeding up the Set Intersection Over Graphs	2024	SIGMOD	4.3842827e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
5,004	Efficient Main Memory Data Management Using the DBGraph Storage Model	1990	VLDB	5.76478e-05
2,905	Teseo and the Analysis of Structural Dynamic Graphs	2021	VLDB	7.9352789e-05
4,845	Graph Analytics Through Fine-Grained Parallelism	2016	SIGMOD	5.8795333e-05
10,161	Enabling Efficient Direct Update on Rule-Based Compressed Graph	2026	SIGMOD	4.1945683e-05
3,232	Managing Large Dynamic Graphs Efficiently	2012	SIGMOD	7.336861e-05
5,847	Spruce: A Fast yet Space-saving Structure for Dynamic Graph Storage	2024	SIGMOD	5.302174e-05
1,426	LiveGraph: A Transactional Graph Storage System with Purely Sequential Adjacency List Scans	2020	VLDB	0.00012050977
10,863	Towards Sufficient GPU-accelerated Dynamic Graph Management: Survey and Experiment	2025	VLDB	4.1945683e-05
10,688	RapidStore: An Efficient Dynamic Graph Storage System for Concurrent Queries	2025	VLDB	4.1945683e-05
7,694	LSMGraph: A High-Performance Dynamic Graph Storage System with Multi-Level CSR	2024	SIGMOD	4.6757592e-05