RadixGraph: A Fast, Space-Optimized Data Structure for Dynamic Graph Storage (Extended Version) Conference: ; December 2025; Online CCS: Information systems Graph-based database models CCS: Information systems Data structures CCS: Information systems Main memory engines
Haoxuan Xie, Junfeng Liu, Siqiang Luo, Kai Wang · 2026
Read RadixGraph: A Fast, Space-Optimized Data Structure for Dynamic Graph Storage (Extended Version) Conference: ; December 2025; Online CCS: Information systems Graph-based database models CCS: Information systems Data structures CCS: Information systems Main memory engines by Haoxuan Xie, Junfeng Liu, Siqiang Luo, Kai Wang (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-01444.txt.
Introduction
Four authors led by Haoxuan Xie present RadixGraph, a data structure for storing graphs that change constantly, such as social networks and transaction webs. As graphs grow, fast updates and compact storage fight each other. RadixGraph indexes vertices with a radix tree tuned to the best balance between lookup speed and space among its design family.
Edges live in a hybrid store that pairs snapshots with a log of changes, giving updates a constant average cost. The system handles millions of updates per second while staying competitive at analytics queries. In experiments, it ingested updates up to about sixteen times faster than the best baseline and used about forty percent less memory on average. The code is open source. For engineers whose graphs never sit still, the design shows that a careful index plus a log can beat general-purpose stores at their own game.
Catalog record
| CREATOR | Haoxuan Xie, Junfeng Liu, Siqiang Luo, Kai Wang |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 81 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-01444
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
RadixGraph: A Fast, Space-Optimized Data Structure for Dynamic Graph Storage (Extended Version) Conference: ; December 2025; Online CCS: Information systems Graph-based database models CCS: Information systems Data structures CCS: Information systems Main memory engines Haoxuan Xie, Junfeng Liu, Siqiang Luo, Kai Wang Abstract . Dynamic graphs model many real-world applications, and as their sizes grow, efficiently storing and updating them becomes critical. We present RadixGraph, a fast and memory-efficient data structure for dynamic graph storage. RadixGraph features a carefully designed radix-tree-based vertex index that strikes an optimal trade-off between query efficiency and space among all pointer-array-based radix trees. For edge storage, it employs a hybrid snapshot-log architecture that enables amortized O ( 1 ) O(1) update time. RadixGraph supports millions of concurrent updates per second while maintaining competitive performance for graph analytics. Experimental results show that RadixGraph outperforms the most performant baseline by up to 16.27 × 16.27\times across various datasets in ingesting graph updates, and reduces memory usage by an average of 40.1 % 40.1\% . RadixGraph is open-source at https://github.com/ForwardStar/RadixGraph . 1. Introduction Graphs are fundamental structures in computer science and widely used to model relationships and interactions between entities, including biological networks ( 53 ; 26 ; 58 ) , financial networks ( 16 ; 38 ; 51 ) and social networks ( 14 ; 50 ; 74 ) . As real-world graphs evolve continuously, the storage and processing of dynamic graphs have become a significant area of focus for both academia and industry. For example, Facebook leverages dynamic graphs to model user relationships at a trillion-scale ( 17 ) , while Twitter employs large-scale dynamic graphs to generate real-time recommendations ( 32 ) . These applications demand not only the management of large-scale graphs but also the efficient processing of updates to the evolving graph. Given the high computational cost of graph algorithms and the need for fast query efficiency, there is an urgent need to design in-memory dynamic graph data structures supporting fast query and update operations, while being space efficient ( 66 ) . However, designing a graph data structure that supports dynamic updates is much more challenging than developing a static structure. It requires wise designs on both vertex index (using which we can locate an index) and edge index (using which we can store and retrieve neighbor edges of a vertex) to deliver both satisfying query and update performance. We summarize existing vertex and edge indices in Table 1 and discuss their limitations as follows. Vertex index Update Query Space Static array ( 41 ; 78 ) Fast Fast High Multi-level vector ( 28 ; 77 ) Moderate Fast Moderate Tree-based ( 20 ; 19 ; 21 ) Moderate Moderate Low Edge index Insert Delete Scan PMA-based ( 69 ; 1 ; 8 ) O(lg^{2}(d)) O(lg^{2}(d)) Fast Log-based ( 77 ; 78 ; 41 ) O(1) O(d) Fast Tree-based ( 28 ; 49 ) O(lg(d)) O(lg(d)) Moderate Table 1. Comparison of existing vertex and edge indices. “Scan” refers to the efficiency of sequential scan, which requires scanning a set of edges and is a common access pattern in graph queries. d represents the average degree of vertices. Challenges of vertex index. Existing graph systems adopt various vertex indexing schemes, each reflecting a trade-off among update efficiency , query performance , and space utilization . Common designs include: (1) static arrays that directly index vertices of contiguous IDs, (2) multi-level vectors that are often coupled with hash tables for ID translation, and (3) tree-based structures such as B-trees ( 4 ) and adaptive radix trees (ART) ( 45 ) . Static arrays ( 41 ; 78 ) provide constant-time access but incur relatively high space overhead especially when vertex identifiers are non-contiguous. Unfortunately, in dynamic graphs, IDs are often hashed or generated as UUIDs (e.g., DataStax Enterprise Graph uses URIs 1 1 1 https://docs.datastax.com/en/dse/6.9/graph/using/vertex-and-edge-ids.html ) which are inherently non-contiguous. Multi-level vectors ( 28 ; 77 ) mitigate the space issue by remapping arbitrary IDs into a compact range via hash tables, yet frequent reallocation and remapping operations during resizing can be a performance concern. Tree-based structures ( 19 ; 20 ; 21 ) are the state-of-the-art approaches that offer logarithmic-time lookups and better space elasticity, which achieves a better trade-off between space and operational costs. In this paper, we show that we can achieve an even better space and performance trade-off, by redesigning radix trees which inherently avoid costly operations such as node split and merge in typical tree-based approaches, while our new design on trie structure selection renders a nice space optimization. Challenges of edge index. Existing dynamic graph systems generally adopt one of three edge storage paradigms: (1) Packed Memory Array ( PMA-based ), (2) log-based , or (3) tree-based , each embodying distinct trade-offs among update efficiency , efficient sequential scan , and space overhead . PMA-based designs ( 69 ; 1 ; 8 ) reserve gaps within arrays for edge insertions, and rebalance the gaps during updates. This offers excellent spatial locality and sequential scan performance but incurs non-trivial space and maintenance costs to manage reserved gaps within the array. Log-based approaches ( 77 ; 78 ; 41 ) mainly store edge logs within an array, which delivers efficient sequential scan, low memory overhead and high insertion throughput via append-only updates. In this design, outdated entries must be located and invalidated through log traversal, incurring extra costs. Tree-based structures ( 28 ; 49 ) organize adjacent edges of each vertex in a hierarchical layout chained with pointers, which offer a balanced trade-off between update efficiency and memory usage but reduce sequential scan performance compared to flat or contiguous storage. The problem. Can we design a dynamic graph data structure that minimizes vertex space with high update/query efficiency, provides O(1) edge operations, and preserves efficient sequential access? Our solution. To address the problem, we propose RadixGraph, a highly performant for both updates and reads and space-efficient dynamic graph system that tackles the problem in the following ways: SORT: a space-efficient and high-performance vertex index. As an efficient data structure for indexing, the radix tree has emerged as a promising solution. The classical radix tree has a well-bounded query latency, coupled with its ability to avoid node splitting and merging when inserting vertices. Empirically, radix-tree-based solutions (Spruce ( 65 ) , RadixGraph) show higher vertex insertion throughput than other systems based on multi-level vectors or ARTs (Figure 8 (d)). Specifically, a recent work, Spruce ( 65 ) , employs the van Emde Boas tree (vEB-tree), which is a variant of the radix tree, to reduce the space cost by adjusting the fanouts of the trees. However, their adjustment is sub-optimal in the trade-offs between space cost and query performance, and how to optimally adjust the fanouts to achieve the best trade-off remains an open issue. To address this challenge, we firstly identify which possible radix tree structures can index a given ID universe, and formulate a constrained optimization program to select the best one that minimizes the space cost. Effectively solving the program gives us the space-optimized radix structure, dubbed as SORT. Snapshot-Log edge storage architecture: O(1) operation time for insert, update, and delete with sequential access support. Traditional approaches