{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,11]],"date-time":"2026-04-11T13:08:39Z","timestamp":1775912919517,"version":"3.50.1"},"reference-count":52,"publisher":"Association for Computing Machinery (ACM)","issue":"13","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2024,9]]},"abstract":"<jats:p>An efficient data structure is fundamental to meeting the growing demands in dynamic graph processing. However, the dual requirements for graph computation efficiency (with contiguous structures) and graph update efficiency (with linked list-like structures) present a conflict in the design principles of graph structures. After experimental studies of state-of-the-art dynamic graph structures, we observe that the overhead of cache misses accounts for a major portion of the graph computation time. This paper presents GastCoCo, a system with graph storage and coroutine-based prefetch co-design. By employing software prefetching via stackless coroutines and designing a prefetch-friendly data structure CBList, GastCoCo significantly alleviates the performance degradation caused by cache misses. Our results show that GastCoCo outperforms state-of-the-art graph storage systems by 1.3\u00d7 - 180\u00d7 in graph updates and 1.4\u00d7 - 41.1\u00d7 in graph computation.<\/jats:p>","DOI":"10.14778\/3704965.3704986","type":"journal-article","created":{"date-parts":[[2025,2,18]],"date-time":"2025-02-18T17:22:57Z","timestamp":1739899377000},"page":"4827-4839","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["GastCoCo: Graph Storage and Coroutine-Based Prefetch Co-Design for Dynamic Graph Processing"],"prefix":"10.14778","volume":"17","author":[{"given":"Hongfu","family":"Li","sequence":"first","affiliation":[{"name":"Northeastern Univ., China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Qian","family":"Tao","sequence":"additional","affiliation":[{"name":"Tongyi Lab, Alibaba Group"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Song","family":"Yu","sequence":"additional","affiliation":[{"name":"Northeastern Univ., China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shufeng","family":"Gong","sequence":"additional","affiliation":[{"name":"Northeastern Univ., China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yanfeng","family":"Zhang","sequence":"additional","affiliation":[{"name":"Northeastern Univ., China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Feng","family":"Yao","sequence":"additional","affiliation":[{"name":"Northeastern Univ., China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wenyuan","family":"Yu","sequence":"additional","affiliation":[{"name":"Tongyi Lab, Alibaba Group"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ge","family":"Yu","sequence":"additional","affiliation":[{"name":"Northeastern Univ., China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jingren","family":"Zhou","sequence":"additional","affiliation":[{"name":"Tongyi Lab, Alibaba Group"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,2,18]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"2023. Alibaba DAU. https:\/\/news.futunn.com\/en\/post\/33640347?level=1&data_ticket=1709021520459060."},{"key":"e_1_2_1_2_1","unstructured":"2024. Taobao. https:\/\/www.taobao.com\/."},{"key":"e_1_2_1_3_1","unstructured":"Renzo Angles J\u00e1nos Benjamin Antal Alex Averbuch Peter A. Boncz Orri Erling Andrey Gubichev Vlad Haprian Moritz Kaufmann Josep Llu\u00eds Larriba-Pey Norbert Mart\u00ednez-Bazan J\u00f3zsef Marton Marcus Paradies Minh-Duc Pham Arnau Prat-P\u00e9rez Mirko Spasic Benjamin A. Steer G\u00e1bor Sz\u00e1rnyas and Jack Waudby. 2020. The LDBC Social Network Benchmark. CoRR abs\/2001.02299 (2020)."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.compbiomed.2022.105766"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1150402.1150412"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings Supercomputing. ACM, 176--186","author":"Baer Jean-Loup","year":"1991","unstructured":"Jean-Loup Baer and Tien-Fu Chen. 1991. An effective on-chip preloading scheme to reduce data access penalty. In Proceedings Supercomputing. ACM, 176--186."},{"key":"e_1_2_1_7_1","volume-title":"2015 IEEE International Symposium on Workload Characterization(IISWC). IEEE Computer Society, 56--65","author":"Beamer Scott","unstructured":"Scott Beamer, Krste Asanovic, and David A. Patterson. 2015. Locality Exists in Graph Processing: Workload Characterization on an Ivy Bridge Server. In 2015 IEEE International Symposium on Workload Characterization(IISWC). IEEE Computer Society, 56--65."},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the Thirteenth International World Wide Web Conference (WWW). ACM Press, 595--601","author":"Boldi Paolo","year":"2004","unstructured":"Paolo Boldi and Sebastiano Vigna. 2004. The WebGraph Framework I: Compression Techniques. In Proceedings of the Thirteenth International World Wide Web Conference (WWW). ACM Press, 595--601."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/106975.106979"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2016.2634535"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1272743.1272747"},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the 35th Annual International Symposium on Microarchitecture (MICRO). ACM\/IEEE Computer Society, 62--73","author":"Collins Jamison D.","unstructured":"Jamison D. Collins, Suleyman Sair, Brad Calder, and Dean M. Tullsen. 2002. Pointer cache assisted prefetching. In Proceedings of the 35th Annual International Symposium on Microarchitecture (MICRO). ACM\/IEEE Computer Society, 62--73."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/356770.356776"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/366663.366704"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1462166.1462167"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3314221.3314598"},{"key":"e_1_2_1_17_1","unstructured":"Bolin Ding Kai Zeng and Wenyuan Yu. 2020. Alibaba Sponsor Talk at VLDB."},{"key":"e_1_2_1_18_1","volume-title":"IEEE Conference on High Performance Extreme Computing (HPEC). IEEE, 1--5.","author":"Ediger David","unstructured":"David Ediger, Robert McColl, E. Jason Riedy, and David A. Bader. 2012. STINGER: High performance data structure for streaming graphs. In IEEE Conference on High Performance Extreme Computing (HPEC). IEEE, 1--5."},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the 7th ACM\/SPEC International Conference on Performance Engineering (ICPE). ACM, 85--90","author":"Eisenman Assaf","year":"2016","unstructured":"Assaf Eisenman, Ludmila Cherkasova, Guilherme Magalhaes, Qiong Cai, Paolo Faraboschi, and Sachin Katti. 2016. Parallel Graph Processing: Prejudice and State of the Art. In Proceedings of the 7th ACM\/SPEC International Conference on Performance Engineering (ICPE). ACM, 85--90."},{"key":"e_1_2_1_20_1","volume-title":"Wenisch","author":"Falsafi Babak","year":"2014","unstructured":"Babak Falsafi and Thomas F. Wenisch. 2014. A Primer on Hardware Prefetching. Morgan & Claypool Publishers."},{"key":"e_1_2_1_21_1","volume-title":"RisGraph: A Real-Time Streaming System for Evolving Graphs. CoRR abs\/2004.00803","author":"Feng Guanyu","year":"2020","unstructured":"Guanyu Feng, Zixuan Ma, Daixuan Li, Xiaowei Zhu, Yanzheng Cai, Wentao Han, and Wenguang Chen. 2020. RisGraph: A Real-Time Streaming System for Evolving Graphs. CoRR abs\/2004.00803 (2020)."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/3514061.3514065"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/2733004.2733010"},{"key":"e_1_2_1_24_1","doi-asserted-by":"crossref","unstructured":"Tao He Shuxian Hu Longbin Lai Dongze Li Neng Li Xue Li Lexiao Liu Xiaojian Luo Binqing Lyu Ke Meng et al. 2023. GraphScope Flex: LEGO-like Graph Computing Stack. arXiv preprint arXiv:2312.12107 (2023).","DOI":"10.1145\/3626246.3653383"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.14778\/3430915.3430932"},{"key":"e_1_2_1_26_1","volume-title":"Intel 64 and IA-32 Architectures Software Developer Manuals. (Oct","author":"Intel Corporation","year":"2016","unstructured":"Intel Corporation. 2016. Intel 64 and IA-32 Architectures Software Developer Manuals. (Oct. 2016)."},{"key":"e_1_2_1_27_1","unstructured":"ISO\/IEC. 2017. Technical Specification --- C++ Extensions for Coroutines. https:\/\/www.iso.org\/standard\/73008.html."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/3236187.3236216"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.14778\/2856318.2856321"},{"key":"e_1_2_1_30_1","article-title":"GraphOne: A Data Store for Realtime Analytics on Evolving Graphs","volume":"15","author":"Kumar Pradeep","year":"2020","unstructured":"Pradeep Kumar and H. Howie Huang. 2020. GraphOne: A Data Store for Realtime Analytics on Evolving Graphs. ACM Trans. Storage 15, 4 (2020), 29:1--29:40.","journal-title":"ACM Trans. Storage"},{"key":"e_1_2_1_31_1","volume-title":"10th USENIX Symposium on Operating Systems Design and Implementation (OSDI). USENIX Association, 31--46","author":"Kyrola Aapo","year":"2012","unstructured":"Aapo Kyrola, Guy E. 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). USENIX Association, 31--46."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.14778\/3447689.3447708"},{"key":"e_1_2_1_33_1","volume-title":"Mowry","author":"Luk Chi-Keung","year":"1996","unstructured":"Chi-Keung Luk and Todd C. Mowry. 1996. Compiler-Based Prefetching for Recursive Data Structures. In Proceedings of the Seventh International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS). ACM Press, 222--233."},{"key":"e_1_2_1_34_1","volume-title":"31st IEEE International Conference on Data Engineering (ICDE). IEEE Computer Society, 363--374","author":"Macko Peter","unstructured":"Peter Macko, Virendra J. Marathe, Daniel W. Margo, and Margo I. Seltzer. 2015. LLAMA: Efficient graph analytics using Large Multiversioned Arrays. In 31st IEEE International Conference on Data Engineering (ICDE). IEEE Computer Society, 363--374."},{"key":"e_1_2_1_35_1","volume-title":"The pagerank citation ranking: bringing order to the web. Unpublished manuscript","author":"Page Larry","year":"1998","unstructured":"Larry Page, Sergey Brin, and R Motwani. 1998. Winograd., T. The pagerank citation ranking: bringing order to the web. Unpublished manuscript (1998)."},{"key":"e_1_2_1_36_1","volume-title":"Terrace: A Hierarchical Graph Container for Skewed Dynamic Graphs. In International Conference on Management of Data (SIGMOD). ACM, 1372--1385","author":"Pandey Prashant","year":"2021","unstructured":"Prashant Pandey, Brian Wheatman, Helen Xu, and Aydin Bulu\u00e7. 2021. Terrace: A Hierarchical Graph Container for Skewed Dynamic Graphs. In International Conference on Management of Data (SIGMOD). ACM, 1372--1385."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.14778\/3149193.3149202"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.14778\/3229863.3229874"},{"key":"e_1_2_1_39_1","volume-title":"Sohi","author":"Roth Amir","year":"1998","unstructured":"Amir Roth, Andreas Moshovos, and Gurindar S. Sohi. 1998. Dependence based prefetching for linked data structures. In Proceedings of the Eighth International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS). ACM Press, 115--126."},{"key":"e_1_2_1_40_1","volume-title":"Proceedings of the 26th Annual International Symposium on Computer Architecture (ISCA). IEEE Computer Society, 111--121","author":"Roth Amir","unstructured":"Amir Roth and Gurindar S. Sohi. 1999. Effective Jump-Pointer Prefetching for Linked Data Structures. In Proceedings of the 26th Annual International Symposium on Computer Architecture (ISCA). IEEE Computer Society, 111--121."},{"key":"e_1_2_1_41_1","doi-asserted-by":"crossref","unstructured":"Yousef Saad. 2003. Iterative methods for sparse linear systems. SIAM.","DOI":"10.1137\/1.9780898718003"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3186728.3164139"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.14778\/3007263.3007267"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/C-M.1978.218016"},{"key":"e_1_2_1_45_1","volume-title":"Proceedings of the 32nd ACM International Conference on Information and Knowledge Management (CIKM). ACM, 2482--2491","author":"Tu Ke","year":"2023","unstructured":"Ke Tu, Wei Qu, Zhengwei Wu, Zhiqiang Zhang, Zhongyi Liu, Yiming Zhao, Le Wu, Jun Zhou, and Guannan Zhang. 2023. Disentangled Interest importance aware Knowledge Graph Neural Network for Fund Recommendation. In Proceedings of the 32nd ACM International Conference on Information and Knowledge Management (CIKM). ACM, 2482--2491."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1162\/qss_a_00021"},{"key":"e_1_2_1_47_1","volume-title":"Packed Compressed Sparse Row: A Dynamic Graph Representation. In 2018 IEEE High Performance Extreme Computing Conference (HPEC). IEEE, 1--7.","author":"Wheatman Brian","year":"2018","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--7."},{"key":"e_1_2_1_48_1","volume-title":"Defining and Evaluating Network Communities Based on Ground-Truth. In 12th IEEE International Conference on Data Mining (ICDM). IEEE Computer Society, 745--754","author":"Yang Jaewon","year":"2012","unstructured":"Jaewon Yang and Jure Leskovec. 2012. Defining and Evaluating Network Communities Based on Ground-Truth. In 12th IEEE International Conference on Data Mining (ICDM). IEEE Computer Society, 745--754."},{"key":"e_1_2_1_49_1","first-page":"396","article-title":"A Review of Knowledge Graph","volume":"13","author":"Zamini Mohamad","year":"2022","unstructured":"Mohamad Zamini, Hassan Reza, and Minou Rabiei. 2022. A Review of Knowledge Graph Completion. Inf. 13, 8 (2022), 396.","journal-title":"Completion. Inf."},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.14778\/3636218.3636240"},{"key":"e_1_2_1_51_1","volume-title":"Gemini: A Computation-Centric Distributed Graph Processing System. In 12th USENIX Symposium on Operating Systems Design and Implementation, (OSDI). USENIX Association.","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). USENIX Association."},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.14778\/3384345.3384351"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3704965.3704986","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,18]],"date-time":"2025-02-18T17:28:03Z","timestamp":1739899683000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3704965.3704986"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,9]]},"references-count":52,"journal-issue":{"issue":"13","published-print":{"date-parts":[[2024,9]]}},"alternative-id":["10.14778\/3704965.3704986"],"URL":"https:\/\/doi.org\/10.14778\/3704965.3704986","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2024,9]]},"assertion":[{"value":"2025-02-18","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}