Back to papers
Spruce: A Fast yet Space-saving Structure for Dynamic Graph Storage
Summary: Spruce is an in-memory dynamic-graph store with a vEB-inspired multilevel structure that shares vertex prefixes to reduce space. Read-optimized concurrency enables fast updates with 2.4x ingestion and 38% memory savings vs top competitors, analytics on par.
(summarized by gpt-5-nano on Feb 09 2026)
Paper ID
6898
Venue
SIGMOD
Year
2024
Pagerank
6.4319457e-05
Overall Rank
4,946 | 66.07%
DOI
10.1145/3639282
Incoming Non-self Citations Over Time
Authors
1.
Jifan Shi
(University of Science and Technology Beijing)
2.
Biao Wang
(University of Science and Technology Beijing)
3.
Yun Xu
(University of Science and Technology Beijing)
BibTeX Citation
Copy BibTeX
@inproceedings{shi_sigmod24,
title = {{Spruce: A Fast yet Space-saving Structure for Dynamic Graph Storage}},
author = {Shi, Jifan and Wang, Biao and Xu, Yun},
series = {{SIGMOD} '24},
booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
publisher = {Association for Computing Machinery},
doi = {10.1145/3639282},
url = {https://dl.acm.org/doi/10.1145/3639282},
year = {2024}
}
Incoming Citations (Sorted by Pagerank)
Showing 10 of 10 citing papers.
Rank
Citing Paper
Year
Venue
Pagerank
6,456
LSMGraph: A High-Performance Dynamic Graph Storage System with Multi-Level CSR
2024
SIGMOD
5.8741786e-05
8,896
Aster: Enhancing LSM-structures for Scalable Graph Database
2025
SIGMOD
5.3495662e-05
8,897
BACH: Bridging Adjacency List and CSR Format using LSM-Trees for HGTAP Workloads
2025
VLDB
5.3495662e-05
9,624
RapidStore: An Efficient Dynamic Graph Storage System for Concurrent Queries
2025
VLDB
5.2434488e-05
9,784
Dynamic Graph Databases with Out-of-order Updates
2024
VLDB
5.2209769e-05
9,891
GTX: A Write-Optimized Latch-free Graph Data System with Transactional Support
2025
SIGMOD
5.1997534e-05
10,207
Bw-Graph: An Efficient Graph Storage System Harmonizing Topology-Aware Tree with Paged CSR
2026
SIGMOD
5.093636e-05
10,450
Enabling Efficient Direct Update on Rule-Based Compressed Graph
2026
SIGMOD
5.093636e-05
10,489
RadixGraph: A Fast, Space-Optimized Data Structure for Dynamic Graph Storage
2026
SIGMOD
5.093636e-05
10,707
Catching up with Disorder: Dynamic Graphs with Out-of-Order Updates
2025
SIGMOD
5.093636e-05
Outgoing Citations (Sorted by Pagerank)
Showing 15 of 15 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
Rank
Cited Paper
Year
Venue
Pagerank
204
Cache Conscious Indexing for Decision-Support in Main Memory
1999
VLDB
0.00025342994
232
LinkBench: a Database Benchmark Based on the Facebook Social Graph
2013
SIGMOD
0.00023830978
882
HOT: A Height Optimized Trie Index for Main-Memory Database Systems
2018
SIGMOD
0.0001342403
1,226
LiveGraph: A Transactional Graph Storage System with Purely Sequential Adjacency List Scans
2020
VLDB
0.00011589731
1,492
BF-Tree: Approximate Tree Indexing
2014
VLDB
0.00010588267
1,563
LDBC Graphalytics: A Benchmark for Large-Scale Graph Analysis on Parallel and Distributed Platforms
2016
VLDB
0.00010352314
1,591
SQLGraph: An Efficient Relational-Based Property Graph Store
2015
SIGMOD
0.00010255536
2,141
Teseo and the Analysis of Structural Dynamic Graphs
2021
VLDB
9.0978534e-05
2,950
An Adaptive Packed-Memory Array
2006
PODS
7.9260861e-05
3,027
Sortledton: a Universal, Transactional Graph Data Structure
2022
VLDB
7.8374092e-05
3,068
RisGraph: A Real-Time Streaming System for Evolving Graphs to Support Sub-millisecond Per-update Analysis at Millions Ops/s
2021
SIGMOD
7.7939351e-05
3,778
Terrace: A Hierarchical Graph Container for Skewed Dynamic Graphs
2021
SIGMOD
7.1334329e-05
4,686
Tornado: A System For Real-Time Iterative Analysis Over Evolving Data
2016
SIGMOD
6.5620646e-05
7,277
Real Time Discovery of Dense Clusters in Highly Dynamic Graphs: Identifying Real World Events in Highly Dynamic Environments
2012
VLDB
5.6581746e-05
8,015
Hyperion: Building the Largest In-memory Search Tree
2019
SIGMOD
5.5071737e-05
Semantically Similar Papers
#
Overall Rank
Paper
Year
Venue
1
2,141
Teseo and the Analysis of Structural Dynamic Graphs
2021
VLDB
2
8,657
An Experimental Comparison of Tree-data Structures for Connectivity Queries on Fully-dynamic Undirected Graphs
2025
SIGMOD
3
7,647
GraphZeppelin: Storage-Friendly Sketching for Connected Components on Dynamic Graph Streams
2022
SIGMOD
4
11,198
Constant-time Connectivity Querying in Dynamic Graphs
2024
SIGMOD
5
3,154
Dynamic Spanning Trees for Connectivity Queries on Fully-dynamic Undirected Graphs
2022
VLDB
6
9,624
RapidStore: An Efficient Dynamic Graph Storage System for Concurrent Queries
2025
VLDB
7
8,154
Revisiting the Design of In-Memory Dynamic Graph Storage
2025
SIGMOD
8
10,450
Enabling Efficient Direct Update on Rule-Based Compressed Graph
2026
SIGMOD
9
10,489
RadixGraph: A Fast, Space-Optimized Data Structure for Dynamic Graph Storage
2026
SIGMOD
10
6,456
LSMGraph: A High-Performance Dynamic Graph Storage System with Multi-Level CSR
2024
SIGMOD