{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T17:43:26Z","timestamp":1757612606785,"version":"3.44.0"},"reference-count":49,"publisher":"Association for Computing Machinery (ACM)","issue":"10","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2025,6]]},"abstract":"<jats:p>Dynamic graph storage systems are essential for real-time applications such as social networks and recommendation, where the graph continuously evolves. However, they face significant challenges in efficiently handling concurrent read and write operations. We find that existing methods suffer from write queries interfering with read efficiency, substantial time and space overhead due to per-edge versioning, and an inability to balance performance, such as slow searches. To address these issues, we propose RapidStore, a holistic approach for efficient in-memory dynamic graph storage designed for read-intensive workloads. Our key idea is to exploit the characteristics of graph queries through a decoupled system design that separates the management of read and write queries and decouples version data from graph data. Besides, we design an efficient dynamic graph store to cooperate with the graph concurrency control mechanism. Experiments show that RapidStore enables fast and scalable concurrent graph queries, effectively balancing the performance of inserts, searches, and scans, and significantly improving efficiency in dynamic graph storage systems.<\/jats:p>","DOI":"10.14778\/3748191.3748217","type":"journal-article","created":{"date-parts":[[2025,9,4]],"date-time":"2025-09-04T13:50:16Z","timestamp":1756993816000},"page":"3587-3600","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["RapidStore: An Efficient Dynamic Graph Storage System for Concurrent Queries"],"prefix":"10.14778","volume":"18","author":[{"given":"Chiyu","family":"Hao","sequence":"first","affiliation":[{"name":"Shanghai Jiao Tong University"}]},{"given":"Jixian","family":"Su","sequence":"additional","affiliation":[{"name":"Shanghai Jiao Tong University"}]},{"given":"Shixuan","family":"Sun","sequence":"additional","affiliation":[{"name":"Shanghai Jiao Tong University"}]},{"given":"Hao","family":"Zhang","sequence":"additional","affiliation":[{"name":"Huawei"}]},{"given":"Sen","family":"Gao","sequence":"additional","affiliation":[{"name":"Shanghai Jiao Tong University"}]},{"given":"Jianwen","family":"Zhao","sequence":"additional","affiliation":[{"name":"Huawei"}]},{"given":"Chenyi","family":"Zhang","sequence":"additional","affiliation":[{"name":"Huawei"}]},{"given":"Jieru","family":"Zhao","sequence":"additional","affiliation":[{"name":"Shanghai Jiao Tong University"}]},{"given":"Chen","family":"Chen","sequence":"additional","affiliation":[{"name":"Shanghai Jiao Tong University"}]},{"given":"Minyi","family":"Guo","sequence":"additional","affiliation":[{"name":"Shanghai Jiao Tong University"}]}],"member":"320","published-online":{"date-parts":[[2025,9,4]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3129246"},{"key":"e_1_2_1_2_1","volume-title":"The GAP benchmark suite. arXiv preprint arXiv:1508.03619","author":"Beamer Scott","year":"2015","unstructured":"Scott Beamer, Krste Asanovi\u0107, and David Patterson. 2015. The GAP benchmark suite. arXiv preprint arXiv:1508.03619 (2015)."},{"key":"e_1_2_1_3_1","volume-title":"2013 USENIX Annual Technical Conference (USENIX ATC 13)","author":"Bronson Nathan","year":"2013","unstructured":"Nathan Bronson, Zach Amsden, George Cabrera, Prasad Chakka, Peter Dimov, Hui Ding, Jack Ferris, Anthony Giardullo, Sachin Kulkarni, Harry Li, et al. 2013. {TAO}:{Facebook's} distributed data store for the social graph. In 2013 USENIX Annual Technical Conference (USENIX ATC 13). 49\u201360."},{"key":"e_1_2_1_4_1","volume-title":"2016 IEEE 32nd International Conference on Data Engineering (ICDE). IEEE, 409\u2013420","author":"Chi Yuze","year":"2016","unstructured":"Yuze Chi, Guohao Dai, Yu Wang, Guangyu Sun, Guoliang Li, and Huazhong Yang. 2016. Nxgraph: An efficient graph processing system on a single machine. In 2016 IEEE 32nd International Conference on Data Engineering (ICDE). IEEE, 409\u2013420."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2491245"},{"key":"e_1_2_1_6_1","volume-title":"2019 IEEE 35th International Conference on Data Engineering (ICDE). IEEE, 830\u2013841","author":"Leo Dean De","year":"2019","unstructured":"Dean De Leo and Peter Boncz. 2019. Packed memory arrays-rewired. In 2019 IEEE 35th International Conference on Data Engineering (ICDE). IEEE, 830\u2013841."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.14778\/3447689.3447708"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519939.3523733"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3314221.3314598"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2463710"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/HPEC.2012.6408680"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457263"},{"key":"e_1_2_1_13_1","unstructured":"Xiyang Feng Guodong Jin Ziyi Chen Chang Liu and Semih Saliho\u011flu. 2023. K\u00f9zu Graph Database Management System. In CIDR."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.14778\/3514061.3514065"},{"key":"e_1_2_1_15_1","volume-title":"PowerGraph: Distributed Graph-Parallel Computation on Natural Graphs. In 10th USENIX symposium on operating systems design and implementation (OSDI 12)","author":"Gonzalez Joseph E","year":"2012","unstructured":"Joseph E Gonzalez, Yucheng Low, Haijie Gu, Danny Bickson, and Carlos Guestrin. 2012. PowerGraph: Distributed Graph-Parallel Computation on Natural Graphs. In 10th USENIX symposium on operating systems design and implementation (OSDI 12). 17\u201330."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.14778\/2733004.2733010"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the 2018 International Conference on Management of Data. 1587\u20131602","author":"Han Shuo","year":"2018","unstructured":"Shuo Han, Lei Zou, and Jeffrey Xu Yu. 2018. Speeding up set intersections in graph algorithms using simd instructions. In Proceedings of the 2018 International Conference on Management of Data. 1587\u20131602."},{"key":"e_1_2_1_18_1","unstructured":"Chiyu Hao Jixian Su Shixuan Sun Hao Zhang Sen Gao Jianwen Zhao Chenyi Zhang Jieru Zhao Chen Chen and Minyi Guo. 2025. RapidStore: An Efficient Dynamic Graph Storage System for Concurrent Queries. arXiv:2507.00839 [cs.DB] https:\/\/arxiv.org\/abs\/2507.00839"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3056445"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3364180"},{"key":"e_1_2_1_21_1","first-page":"4","volume-title":"Proceedings of the VLDB Endowment 5","author":"Larson Per-\u00c5ke","year":"2011","unstructured":"Per-\u00c5ke Larson, Spyros Blanas, Cristian Diaconu, Craig Freedman, Jignesh M Patel, and Mike Zwilling. 2011. High-Performance Concurrency Control Mechanisms for Main-Memory Databases. Proceedings of the VLDB Endowment 5, 4 (2011)."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544812"},{"key":"e_1_2_1_23_1","first-page":"4453","article-title":"Space-Efficient Subgraph Search Over Streaming Graph With Timing Order Constraint","volume":"34","author":"Li Youhuan","year":"2020","unstructured":"Youhuan Li, Lei Zou, M Tamer \u00d6zsu, and Dongyan Zhao. 2020. Space-Efficient Subgraph Search Over Streaming Graph With Timing Order Constraint. IEEE Transactions on Knowledge and Data Engineering 34, 9 (2020), 4453\u20134467.","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3064015"},{"key":"e_1_2_1_25_1","volume-title":"2015 IEEE 31st International Conference on Data Engineering. IEEE, 363\u2013374","author":"Macko Peter","year":"2015","unstructured":"Peter Macko, Virendra J Marathe, Daniel W Margo, and Margo I Seltzer. 2015. Llama: Efficient graph analytics using large multiversioned arrays. In 2015 IEEE 31st International Conference on Data Engineering. IEEE, 363\u2013374."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3302424.3303974"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2567634.2567638"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2749436"},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the 2021 International Conference on Management of Data. 1372\u20131385","author":"Pandey Prashant","year":"2021","unstructured":"Prashant Pandey, Brian Wheatman, Helen Xu, and Aydin Buluc. 2021. Terrace: A hierarchical graph container for skewed dynamic graphs. In Proceedings of the 2021 International Conference on Management of Data. 1372\u20131385."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.14778\/3229863.3229874"},{"key":"e_1_2_1_31_1","volume-title":"2015 11th International Conference on Signal-Image Technology & Internet-Based Systems (SITIS). IEEE, 512\u2013519","author":"Rathore M Mazhar","year":"2015","unstructured":"M Mazhar Rathore, Awais Ahmad, Anand Paul, and Gwanggil Jeon. 2015. Efficient graph-oriented smart transportation using internet of things generated big data. In 2015 11th International Conference on Signal-Image Technology & Internet-Based Systems (SITIS). IEEE, 512\u2013519."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-013-0303-4"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3186728.3164139"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.14778\/3007263.3007267"},{"key":"e_1_2_1_35_1","volume-title":"2023 USENIX Annual Technical Conference (USENIX ATC 23)","author":"Shen Sijie","year":"2023","unstructured":"Sijie Shen, Zihang Yao, Lin Shi, Lei Wang, Longbin Lai, Qian Tao, Li Su, Rong Chen, Wenyuan Yu, Haibo Chen, et al. 2023. Bridging the Gap between Relational {OLTP} and Graph-based {OLAP}. In 2023 USENIX Annual Technical Conference (USENIX ATC 23). 181\u2013196."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3639282"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2442516.2442530"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/DCC.2015.8"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3289600.3290989"},{"key":"e_1_2_1_40_1","volume-title":"Proceedings of the 23rd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. 290\u2013304","author":"Sun Yihan","year":"2018","unstructured":"Yihan Sun, Daniel Ferizovic, and Guy E Belloch. 2018. PAM: parallel augmented maps. In Proceedings of the 23rd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. 290\u2013304."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522713"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3037697.3037748"},{"key":"e_1_2_1_43_1","volume-title":"Proceedings of the 2017 ACM International Conference on Management of Data. 993\u20131008","author":"Wang Jianguo","year":"2017","unstructured":"Jianguo Wang, Chunbin Lin, Yannis Papakonstantinou, and Steven Swanson. 2017. An experimental study of bitmap compression vs. inverted list compression. In Proceedings of the 2017 ACM International Conference on Management of Data. 993\u20131008."},{"volume-title":"Packed compressed sparse row: A dynamic graph representation. In 2018 IEEE High Performance extreme Computing Conference (HPEC)","author":"Wheatman Brian","key":"e_1_2_1_44_1","unstructured":"Brian Wheatman and Helen Xu. 2018. Packed compressed sparse row: A dynamic graph representation. In 2018 IEEE High Performance extreme Computing Conference (HPEC). IEEE, 1\u20137."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3639284"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3380590"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3698818"},{"key":"e_1_2_1_48_1","volume-title":"Online Global Query Planning for Dynamic Road Networks. In 2022 IEEE 8th International Conference on Cloud Computing and Intelligent Systems (CCIS). IEEE, 666\u2013670","author":"Zhang Siyi","year":"2022","unstructured":"Siyi Zhang, Xiaoxi Cui, Yurong Cheng, Ye Yuan, and Guoren Wang. 2022. Online Global Query Planning for Dynamic Road Networks. In 2022 IEEE 8th International Conference on Cloud Computing and Intelligent Systems (CCIS). IEEE, 666\u2013670."},{"key":"e_1_2_1_49_1","volume-title":"Livegraph: A transactional graph storage system with purely sequential adjacency list scans. arXiv preprint arXiv:1910.05773","author":"Zhu Xiaowei","year":"2019","unstructured":"Xiaowei Zhu, Guanyu Feng, Marco Serafini, Xiaosong Ma, Jiping Yu, Lei Xie, Ashraf Aboulnaga, and Wenguang Chen. 2019. Livegraph: A transactional graph storage system with purely sequential adjacency list scans. arXiv preprint arXiv:1910.05773 (2019)."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3748191.3748217","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,4]],"date-time":"2025-09-04T13:51:11Z","timestamp":1756993871000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3748191.3748217"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6]]},"references-count":49,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2025,6]]}},"alternative-id":["10.14778\/3748191.3748217"],"URL":"https:\/\/doi.org\/10.14778\/3748191.3748217","relation":{},"ISSN":["2150-8097"],"issn-type":[{"type":"print","value":"2150-8097"}],"subject":[],"published":{"date-parts":[[2025,6]]},"assertion":[{"value":"2025-09-04","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}