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: 7064
Venue: SIGMOD
Year: 2025
Pagerank: 4.541321e-05
Overall Rank: 8,264 | 42.57%
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.1905499e-05
10,161	Enabling Efficient Direct Update on Rule-Based Compressed Graph	2026	SIGMOD	4.1905499e-05
10,200	RadixGraph: A Fast, Space-Optimized Data Structure for Dynamic Graph Storage	2026	SIGMOD	4.1905499e-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.0019040811
286	High-Performance Concurrency Control Mechanisms for Main-Memory Databases	2012	VLDB	0.0002894802
327	The Ubiquity of Large Graphs and Surprising Challenges of Graph Processing	2018	VLDB	0.00027312381
341	EmptyHeaded: A Relational Engine for Graph Processing	2016	SIGMOD	0.00026850764
419	Fast Serializable Multi-Version Concurrency Control for Main-Memory Database Systems	2015	SIGMOD	0.00023720294
441	Parallelizing Sequential Graph Computations	2017	SIGMOD	0.00023172424
530	The LDBC Social Network Benchmark: Interactive Workload	2015	SIGMOD	0.00020823189
632	Staring into the Abyss: An Evaluation of Concurrency Control with One Thousand Cores	2015	VLDB	0.00018895506
1,424	LiveGraph: A Transactional Graph Storage System with Purely Sequential Adjacency List Scans	2020	VLDB	0.00012044472
1,431	An Empirical Evaluation of In-Memory Multi-Version Concurrency Control	2017	VLDB	0.00012021808
1,973	Speeding Up Set Intersections in Graph Algorithms using SIMD Instructions	2018	SIGMOD	9.8834701e-05
2,201	LDBC Graphalytics: A Benchmark for Large-Scale Graph Analysis on Parallel and Distributed Platforms	2016	VLDB	9.3042485e-05
2,821	An Experimental Study of Bitmap Compression vs. Inverted List Compression	2017	SIGMOD	8.0639288e-05
2,910	Teseo and the Analysis of Structural Dynamic Graphs	2021	VLDB	7.9276339e-05
2,962	Kuzu* Graph Database Management System	2023	CIDR	7.8069285e-05
3,365	An Adaptive Packed-Memory Array	2006	PODS	7.1675736e-05
3,670	The LDBC Social Network Benchmark: Business Intelligence Workload	2023	VLDB	6.8557811e-05
3,733	Sortledton: a Universal, Transactional Graph Data Structure	2022	VLDB	6.8067988e-05
4,091	RisGraph: A Real-Time Streaming System for Evolving Graphs to Support Sub-millisecond Per-update Analysis at Millions Ops/s	2021	SIGMOD	6.4529617e-05
4,238	Terrace: A Hierarchical Graph Container for Skewed Dynamic Graphs	2021	SIGMOD	6.3274465e-05
5,027	Nanosecond Indexing of Graph Data With Hash Maps and VLists	2019	SIGMOD	5.7449062e-05
5,234	ByteGraph: A High-Performance Distributed Graph Database in ByteDance	2022	VLDB	5.609287e-05
7,372	BG3: A Cost Effective and I/O Efficient Graph Database in ByteDance	2024	SIGMOD	4.7445723e-05
7,729	GraphZeppelin: Storage-Friendly Sketching for Connected Components on Dynamic Graph Streams	2022	SIGMOD	4.6614672e-05
9,177	HERO: A Hierarchical Set Partitioning and Join Framework for Speeding up the Set Intersection Over Graphs	2024	SIGMOD	4.3800806e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
5,005	Efficient Main Memory Data Management Using the DBGraph Storage Model	1990	VLDB	5.7599923e-05
2,910	Teseo and the Analysis of Structural Dynamic Graphs	2021	VLDB	7.9276339e-05
4,845	Graph Analytics Through Fine-Grained Parallelism	2016	SIGMOD	5.8731048e-05
10,161	Enabling Efficient Direct Update on Rule-Based Compressed Graph	2026	SIGMOD	4.1905499e-05
3,234	Managing Large Dynamic Graphs Efficiently	2012	SIGMOD	7.3302974e-05
5,857	Spruce: A Fast yet Space-saving Structure for Dynamic Graph Storage	2024	SIGMOD	5.2970837e-05
1,424	LiveGraph: A Transactional Graph Storage System with Purely Sequential Adjacency List Scans	2020	VLDB	0.00012044472
10,867	Towards Sufficient GPU-accelerated Dynamic Graph Management: Survey and Experiment	2025	VLDB	4.1905499e-05
10,696	RapidStore: An Efficient Dynamic Graph Storage System for Concurrent Queries	2025	VLDB	4.1905499e-05
7,694	LSMGraph: A High-Performance Dynamic Graph Storage System with Multi-Level CSR	2024	SIGMOD	4.6712753e-05