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) 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× across various datasets in ingesting graph updates, and reduces memory usage by an average of 40.1%. RadixGraph is open-source at https://github.com/ForwardStar/RadixGraph.
Building similarity graph...
Analyzing shared references across papers
Loading...
Haoxuan Xie
Junfeng Liu
Siqiang Luo
Proceedings of the ACM on Management of Data
Nanyang Technological University
Harbin Institute of Technology
Building similarity graph...
Analyzing shared references across papers
Loading...
Xie et al. (Thu,) studied this question.
www.synapsesocial.com/papers/69d8940c6c1944d70ce04fef — DOI: https://doi.org/10.1145/3786686