{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,18]],"date-time":"2026-08-18T01:46:02Z","timestamp":1787017562272,"version":"build-2736575974"},"reference-count":75,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2024,3,12]],"date-time":"2024-03-12T00:00:00Z","timestamp":1710201600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Nature Science Foundation of China","doi-asserted-by":"crossref","award":["61672480"],"award-info":[{"award-number":["61672480"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"111 Project 2.0","award":["BP0719016"],"award-info":[{"award-number":["BP0719016"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,3,12]]},"abstract":"<jats:p>Dynamic graphs have been gaining increasing popularity across various application domains. With the growing size of these graphs, the update performance as well as space occupancy is becoming a crucial aspect of dynamic graph storage. Although existing dynamic graph systems can handle massive streaming updates (e.g., insertions and deletions), they cannot achieve both high throughput and low memory footprint. Drawing inspiration from the basic operations of the van Emde Boas (vEB) tree in double-logarithmic time, we designed Spruce, a high-performance yet space-saving in-memory structure to store dynamic graphs. Spruce uses a compact representation to construct the tree-like multilevel structure, which shares the common prefixes of vertices and has no merging or splitting of nodes to achieve the requirements of low memory consumption and high-efficiency dynamic operations. Furthermore, Spruce incorporates a read-optimized concurrency protocol, which refines ROWEX and Optimistic Locking, to facilitate efficient simultaneous read\/write operations. Our experiment demonstrates that compared to Sortledton (the best of competitors), Spruce is up to 2.4X faster in ingesting graph updates, while saving up to 38.5% of memory space. As for graph analytics, Spruce shows high adaptability to different analytical workloads, and achieves comparable performance to other state-of-the-art dynamic graph structures.<\/jats:p>","DOI":"10.1145\/3639282","type":"journal-article","created":{"date-parts":[[2024,3,26]],"date-time":"2024-03-26T18:51:32Z","timestamp":1711479092000},"page":"1-26","source":"Crossref","is-referenced-by-count":19,"title":["Spruce: a Fast yet Space-saving Structure for Dynamic Graph Storage"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0009-0004-5026-508X","authenticated-orcid":false,"given":"Jifan","family":"Shi","sequence":"first","affiliation":[{"name":"University of Science and Technology of China, Hefei, Anhui, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0005-9308-7823","authenticated-orcid":false,"given":"Biao","family":"Wang","sequence":"additional","affiliation":[{"name":"University of Science and Technology of China, Hefei, Anhui, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-4850-3299","authenticated-orcid":false,"given":"Yun","family":"Xu","sequence":"additional","affiliation":[{"name":"University of Science and Technology of China, Hefei, Anhui, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,3,26]]},"reference":[{"key":"e_1_2_2_1_1","unstructured":"2015. TITAN: Distributed Graph Database. https:\/\/titan.thinkaurelius.com."},{"key":"e_1_2_2_2_1","unstructured":"2020. OrientDB Community. https:\/\/orientdb.org."},{"key":"e_1_2_2_3_1","unstructured":"2022. Neo4j Graph Database Platform. https:\/\/neo4j.com\/product\/neo4j-graph-database."},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.14778\/2336664.2336671"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3558481"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","unstructured":"A. Amir A. Efrat P. Indyk and H. Samet. 2001. Efficient Regular Data Structures and Algorithms for Dilation Location and Proximity Problems. Algorithmica 30 2 (01 Jun 2001) 164--187. https:\/\/doi.org\/10.1007\/s00453-001-0013-y","DOI":"10.1007\/s00453-001-0013-y"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465296"},{"key":"e_1_2_2_8_1","volume-title":"Cache-Conscious Collision Resolution in String Hash Tables","author":"Askitis Nikolas","unstructured":"Nikolas Askitis and Justin Zobel. 2005. Cache-Conscious Collision Resolution in String Hash Tables. In String Processing and Information Retrieval, Mariano Consens and Gonzalo Navarro (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 91--102."},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.14778\/2733085.2733094"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1734663.1734671"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/SC.2012.50"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2000.892128"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1292609.1292616"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196896"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3506692"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/988672.988752"},{"key":"e_1_2_2_17_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, Mark Marchukov, Dmitri Petrov, Lovro Puzar, Yee Jiun Song, and Venkat Venkataramani. 2013. TAO: Facebook's Distributed Data Store for the Social Graph. In 2013 USENIX Annual Technical Conference (USENIX ATC 13). USENIX Association, San Jose, CA, 49--60. https:\/\/www.usenix.org\/conference\/atc13\/technical-sessions\/presentation\/bronson"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2390021.2390023"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","unstructured":"Deepayan Chakrabarti Yiping Zhan and Christos Faloutsos. [n. d.]. R-MAT: A Recursive Model for Graph Mining. 442--446. https:\/\/doi.org\/10.1137\/1.9781611972740.43 arXiv:https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/1.9781611972740.43","DOI":"10.1137\/1.9781611972740.43"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/356770.356776"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2491245"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519939.3523733"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3314221.3314598"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/hpec.2012.6408680"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cels.2021.08.009"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457263"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.OPODIS.2020.17"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/367390.367400"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.14778\/3514061.3514065"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.37236\/11668"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1644893.1644931"},{"key":"e_1_2_2_32_1","volume-title":"Proceedings of the 11th USENIX Conference on Operating Systems Design and Implementation","author":"Gonzalez Joseph E.","year":"2014","unstructured":"Joseph E. Gonzalez, Reynold S. Xin, Ankur Dave, Daniel Crankshaw, Michael J. Franklin, and Ion Stoica. 2014. GraphX: Graph Processing in a Distributed Dataflow Framework. In Proceedings of the 11th USENIX Conference on Operating Systems Design and Implementation (Broomfield, CO) (OSDI'14). USENIX Association, USA, 599--613."},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/NetGames.2012.6404027"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.14778\/3007263.3007270"},{"key":"e_1_2_2_35_1","unstructured":"Andrew Lumsdaine Jeremy Siek Lie-Quan Lee. 2022. The Boost Graph Library (BGL). https:\/\/www.boost.org\/doc\/libs\/1_80_0\/libs\/graph\/doc\/index.html."},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-012-0283--9"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10822-016--9938--8"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3364180"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/319566.319567"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544812"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2933349.2933352"},{"key":"e_1_2_2_42_1","unstructured":"Dean De Leo and Peter Boncz. 2021. GFE Driver. https:\/\/github.com\/cwida\/gfe_driver."},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.14778\/3447689.3447708"},{"key":"e_1_2_2_44_1","volume-title":"Kronecker Graphs: An Approach to Modeling Networks. J. Mach. Learn. Res. 11 (mar","author":"Leskovec Jure","year":"2010","unstructured":"Jure Leskovec, Deepayan Chakrabarti, Jon Kleinberg, Christos Faloutsos, and Zoubin Ghahramani. 2010. Kronecker Graphs: An Approach to Modeling Networks. J. Mach. Learn. Res. 11 (mar 2010), 985--1042."},{"key":"e_1_2_2_45_1","unstructured":"Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. http:\/\/snap.stanford.edu\/data."},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE53745.2022.00102"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/2751205.2751209"},{"key":"e_1_2_2_48_1","volume-title":"AAAI Workshop - Technical Report (01","author":"Lu C.","year":"2012","unstructured":"C. Lu, W. Lam, and Y. Zhang. 2012. Twitter user modeling and tweets recommendation based on wikipedia concept graph. AAAI Workshop - Technical Report (01 2012), 33--38."},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2015.7113298"},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319870"},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/2567634.2567638"},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0196--6774(03)00076--2"},{"key":"e_1_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/2983551"},{"key":"e_1_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/MDM.2009.48"},{"key":"e_1_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457313"},{"key":"e_1_2_2_56_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2019.00157"},{"key":"e_1_2_2_57_1","unstructured":"Jeff Preshing. 2018. junction. https:\/\/https:\/\/github.com\/preshing\/junction."},{"key":"e_1_2_2_58_1","volume-title":"Proceedings of the 25th International Conference on Very Large Data Bases (VLDB '99)","author":"Rao Jun","unstructured":"Jun Rao and Kenneth A. Ross. 1999. Cache Conscious Indexing for Decision-Support in Main Memory. In Proceedings of the 25th International Conference on Very Large Data Bases (VLDB '99). Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 78--89."},{"key":"e_1_2_2_59_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-013-0303--4"},{"key":"e_1_2_2_60_1","volume-title":"Ahmed","author":"Rossi Ryan A.","year":"2015","unstructured":"Ryan A. Rossi and Nesreen K. Ahmed. 2015. The Network Data Repository with Interactive Graph Analytics and Visualization. In AAAI. https:\/\/networkrepository.com"},{"key":"e_1_2_2_61_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--981--19--5244--9_3"},{"key":"e_1_2_2_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2882950"},{"key":"e_1_2_2_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517327.2442530"},{"key":"e_1_2_2_64_1","doi-asserted-by":"publisher","DOI":"10.1109\/DCC.2015.8"},{"key":"e_1_2_2_65_1","unstructured":"Chris Siebenmann. 2012. Understanding Resident Set Size and the RSS problem on modern Unixes. https:\/\/utcc.utoronto.ca\/ cks\/space\/blog\/unix\/UnderstandingRSS."},{"key":"e_1_2_2_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/3289600.3290989"},{"key":"e_1_2_2_67_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2723732"},{"key":"e_1_2_2_68_1","unstructured":"Mahammad Valiyev Tum and Mahammad Valiyev. 2017. Graph Storage : How good is CSR really?"},{"key":"e_1_2_2_69_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1975.26"},{"key":"e_1_2_2_70_1","doi-asserted-by":"publisher","DOI":"10.1145\/384192.384193"},{"key":"e_1_2_2_71_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCBB.2010.127"},{"key":"e_1_2_2_72_1","doi-asserted-by":"publisher","DOI":"10.1109\/BigData52589.2021.9671836"},{"key":"e_1_2_2_73_1","doi-asserted-by":"publisher","DOI":"10.1109\/hpec.2018.8547566"},{"key":"e_1_2_2_74_1","doi-asserted-by":"publisher","DOI":"10.1038\/s41567-022-01784--9"},{"key":"e_1_2_2_75_1","doi-asserted-by":"publisher","DOI":"10.14778\/3384345.3384351"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3639282","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3639282","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,21]],"date-time":"2025-08-21T15:16:03Z","timestamp":1755789363000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3639282"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,12]]},"references-count":75,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,3,12]]}},"alternative-id":["10.1145\/3639282"],"URL":"https:\/\/doi.org\/10.1145\/3639282","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,3,12]]}}}