{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,18]],"date-time":"2026-05-18T19:06:34Z","timestamp":1779131194227,"version":"3.51.4"},"reference-count":62,"publisher":"Association for Computing Machinery (ACM)","issue":"3","funder":[{"DOI":"10.13039\/501100001809","name":"the National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["62372264, 92467203"],"award-info":[{"award-number":["62372264, 92467203"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2026,5,18]]},"abstract":"<jats:p>As digital transformation accelerates, modern graph datasets routinely scale to billions of vertices and edges, demanding storage systems that simultaneously support dynamic updates, rapid neighbor retrieval, and high-performance analytics. However, existing systems face significant performance bottlenecks. While LSM-Tree-based approaches have gained popularity for their write efficiency, they suffer from fundamental read amplification problems that remain unresolved despite various optimization attempts. Moreover, most systems organize data by vertex IDs for simplicity, thereby sacrificing topological locality that could benefit graph algorithms. Although recent topology-aware methods offer improvements, they suffer from severe partition imbalance and fragility under updates. These challenges are further compounded by concurrency control designs in which structural modification operations block user requests, thereby limiting system throughput.<\/jats:p>\n                  <jats:p>To address these challenges, we present Bw-Graph, a graph storage system that harmonizes a Topology-Aware Tree with Paged CSR. Bw-Graph employs CSR pages for efficient neighbor access, while utilizing append-only \u0394 Pages to enable sequential writes to subgraphs. To enable efficient graph analytics, we propose a Topology-Aware Tree that hierarchically organizes graph data to co-locate densely connected vertices in contiguous physical storage. The underlying weight-constrained graph partitioning scheme ensures balanced partition sizes while preserving topological locality. To support high concurrency, we develop a tailored MVCC mechanism that leverages the append-only nature of \u0394 Pages for lightweight version management, and exploits a multi-version vertex index to guarantee consistency without blocking user requests during structural modification operations. Comprehensive evaluations demonstrate that Bw-Graph achieves significant performance improvements across diverse workloads. For analytics tasks, Bw-Graph further delivers performance comparable to that of dedicated graph processing systems (e.g., GridGraph).<\/jats:p>","DOI":"10.1145\/3802025","type":"journal-article","created":{"date-parts":[[2026,5,18]],"date-time":"2026-05-18T18:19:16Z","timestamp":1779128356000},"page":"1-27","source":"Crossref","is-referenced-by-count":0,"title":["Bw-Graph: An Efficient Graph Storage System Harmonizing Topology-Aware Tree with Paged CSR"],"prefix":"10.1145","volume":"4","author":[{"ORCID":"https:\/\/orcid.org\/0009-0001-4054-9853","authenticated-orcid":false,"given":"Songyao","family":"Wang","sequence":"first","affiliation":[{"name":"Tsinghua University, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2986-2574","authenticated-orcid":false,"given":"Chaokun","family":"Wang","sequence":"additional","affiliation":[{"name":"Tsinghua University, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-6248-1014","authenticated-orcid":false,"given":"Zecheng","family":"Li","sequence":"additional","affiliation":[{"name":"Tsinghua University, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0004-7067-9642","authenticated-orcid":false,"given":"Aoqi","family":"Zhang","sequence":"additional","affiliation":[{"name":"Tsinghua University, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2026,5,18]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1088\/1742-5468\/2008\/10\/P10008"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.587"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/988672.988752"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3769755"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.70.066111"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.14778\/3447689.3447708"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3093742.3093913"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457263"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.122653799"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the 10th USENIX Conference on Operating Systems Design and Implementation","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 Proceedings of the 10th USENIX Conference on Operating Systems Design and Implementation (Hollywood, CA, USA) (OSDI'12). USENIX Association, USA, 17\u201330."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ESA.2021.48"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.14778\/3748191.3748217"},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1023\/A:1011472308196","article-title":"Managing gigabytes-compressing and indexing documents and images","volume":"4","author":"Hersh William","year":"2001","unstructured":"William Hersh. 2001. Managing gigabytes-compressing and indexing documents and images. Information Retrieval, Vol. 4, 1 (2001), 79.","journal-title":"Information Retrieval"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.14778\/3718057.3718076"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.14778\/3007263.3007270"},{"key":"e_1_2_1_16_1","unstructured":"it 2004. 2004. IT-2004. https:\/\/law.di.unimi.it\/webdata\/it-2004\/. https:\/\/law.di.unimi.it\/webdata\/it-2004\/ Italian Web Graph from IIT-CNR."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020580"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177729694"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3364180"},{"key":"e_1_2_1_20_1","unstructured":"Kuzu. 2026. https:\/\/github.com\/kuzudb\/kuzu (last checked on 2026-01)."},{"key":"e_1_2_1_21_1","first-page":"31","volume-title":"10th USENIX Symposium on Operating Systems Design and Implementation (OSDI 12)","author":"Kyrola Aapo","year":"2012","unstructured":"Aapo Kyrola, Guy Blelloch, and Carlos Guestrin. 2012. GraphChi: Large-Scale Graph Computation on Just a PC. In 10th USENIX Symposium on Operating Systems Design and Implementation (OSDI 12). USENIX Association, Hollywood, CA, 31-46. https:\/\/www.usenix.org\/conference\/osdi12\/technical-sessions\/presentation\/kyrola"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.2203"},{"key":"e_1_2_1_23_1","unstructured":"Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. http:\/\/snap.stanford.edu\/data."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.79.066107"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544834"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3709738"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE55515.2023.00196"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.physa.2018.03.080"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00189"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCSS.2023.3303476"},{"key":"e_1_2_1_31_1","volume-title":"Proceedings of the Twenty-Sixth Conference on Uncertainty in Artificial Intelligence","author":"Low Yucheng","year":"2010","unstructured":"Yucheng Low, Joseph Gonzalez, Aapo Kyrola, Danny Bickson, Carlos Guestrin, and Joseph Hellerstein. 2010. GraphLab: a new framework for parallel machine learning. In Proceedings of the Twenty-Sixth Conference on Uncertainty in Artificial Intelligence (Catalina Island, CA) (UAI'10). AUAI Press, Arlington, Virginia, USA, 340\u2013349."},{"key":"e_1_2_1_32_1","first-page":"133","volume-title":"14th USENIX Conference on File and Storage Technologies (FAST 16)","author":"Lu Lanyue","unstructured":"Lanyue Lu, Thanumalayan Sankaranarayana Pillai, Andrea C. Arpaci-Dusseau, and Remzi H. Arpaci-Dusseau. 2016. WiscKey: Separating Keys from Values in SSD-conscious Storage. In 14th USENIX Conference on File and Storage Technologies (FAST 16). USENIX Association, Santa Clara, CA, 133-148. https:\/\/www.usenix.org\/conference\/fast16\/technical-sessions\/presentation\/lu"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3064176.3064191"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2015.7113298"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807184"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE53745.2022.00215"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3307650.3322275"},{"key":"e_1_2_1_38_1","unstructured":"METIS. 2025. https:\/\/github.com\/KarypisLab\/METIS (last checked on 2025-09)."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3709662"},{"key":"e_1_2_1_40_1","unstructured":"MySQL. 2025. https:\/\/github.com\/mysql\/mysql-server (last checked on 2025-10)."},{"key":"e_1_2_1_41_1","unstructured":"Neo4j. 2024. https:\/\/github.com\/neo4j\/neo4j (last checked on 2024-04)."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/s002360050048"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3654928"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.76.036106"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3172867"},{"key":"e_1_2_1_46_1","volume-title":"Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence","author":"Ryan","unstructured":"Ryan A. Rossi and Nesreen K. Ahmed. 2015. The network data repository with interactive graph analytics and visualization. In Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence (Austin, Texas) (AAAI'15). AAAI Press, 4292\u20134293."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/2815400.2815408"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522740"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/3639282"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/3037697.3037748"},{"key":"e_1_2_1_51_1","volume-title":"Proceedings of the 2016 USENIX Conference on Usenix Annual Technical Conference (Denver, CO, USA) (USENIX ATC '16). USENIX Association, USA, 507\u2013522","author":"Vora Keval","year":"2016","unstructured":"Keval Vora, Guoqing Xu, and Rajiv Gupta. 2016. Load the edges you need: a generic I\/O optimization for disk-based graph processing. In Proceedings of the 2016 USENIX Conference on Usenix Annual Technical Conference (Denver, CO, USA) (USENIX ATC '16). USENIX Association, USA, 507\u2013522."},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE51399.2021.00055"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.14778\/2794367.2794370"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE65448.2025.00267"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915220"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/2484425.2484427"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/3698818"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/3626246.3653373"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2017.2776115"},{"key":"e_1_2_1_60_1","first-page":"301","volume-title":"Gemini: A Computation-Centric Distributed Graph Processing System. In 12th USENIX Symposium on Operating Systems Design and Implementation (OSDI 16)","author":"Zhu Xiaowei","year":"2016","unstructured":"Xiaowei Zhu, Wenguang Chen, Weimin Zheng, and Xiaosong Ma. 2016. Gemini: A Computation-Centric Distributed Graph Processing System. In 12th USENIX Symposium on Operating Systems Design and Implementation (OSDI 16). USENIX Association, Savannah, GA, 301-316. https:\/\/www.usenix.org\/conference\/osdi16\/technical-sessions\/presentation\/zhu"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.14778\/3384345.3384351"},{"key":"e_1_2_1_62_1","first-page":"375","volume-title":"2015 USENIX Annual Technical Conference (USENIX ATC 15)","author":"Zhu Xiaowei","year":"2015","unstructured":"Xiaowei Zhu, Wentao Han, and Wenguang Chen. 2015. GridGraph: Large-Scale Graph Processing on a Single Machine Using 2-Level Hierarchical Partitioning. In 2015 USENIX Annual Technical Conference (USENIX ATC 15). USENIX Association, Santa Clara, CA, 375-386. https:\/\/www.usenix.org\/conference\/atc15\/technical-session\/presentation\/zhu"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3802025","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,18]],"date-time":"2026-05-18T18:26:22Z","timestamp":1779128782000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3802025"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5,18]]},"references-count":62,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2026,5,18]]}},"alternative-id":["10.1145\/3802025"],"URL":"https:\/\/doi.org\/10.1145\/3802025","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,5,18]]}}}