{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,11]],"date-time":"2026-04-11T13:08:09Z","timestamp":1775912889283,"version":"3.50.1"},"reference-count":54,"publisher":"Association for Computing Machinery (ACM)","issue":"11","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2025,7]]},"abstract":"<jats:p>Leveraging GPUs' high parallelism can significantly improve the real-time computation efficiency of streaming graph processing. However, when a large-scale graph exceeds GPU memory capacity, CPU-GPU cooperative processing often results in substantial and irregular CPU-to-GPU data transfer overhead. This stems from the extensive redundant graph accesses during continuous computation, which can hardly be addressed by existing solutions. In this work, we present Grapin, an out-of-memory GPU streaming graph processing system designed to minimize graph data transfer via two effective techniques for eliminating redundant accesses: (1) Extending advanced incremental processing algorithms to GPUs by converting their heavyweight data dependency processing into GPU-friendly forms, eliminating redundant graph accesses from the computation side; and (2) providing a lightweight yet efficient GPU hot subgraph management framework that finely caches the frequently accessed dynamic subgraphs in a vertex-centric manner. Experimental results demonstrate that Grapin can efficiently process large-scale streaming graphs with billions of edges on a single NVIDIA A5000 GPU. Enabling incremental computation reduces data transfer by 61%, and the integration of GPU hot subgraph reuse further reduces the remaining transfer by 72%, resulting in a total reduction of 89%. Compared with CPU-based solutions, Grapin achieves speedups ranging from 1.8x to 96.9x (17.9x on average).<\/jats:p>","DOI":"10.14778\/3749646.3749659","type":"journal-article","created":{"date-parts":[[2025,9,4]],"date-time":"2025-09-04T17:55:06Z","timestamp":1757008506000},"page":"3854-3867","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Efficient Graph Data Access for Out-of-Memory GPU Streaming Graph Processing"],"prefix":"10.14778","volume":"18","author":[{"given":"Qiange","family":"Wang","sequence":"first","affiliation":[{"name":"National University of Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yongze","family":"Yan","sequence":"additional","affiliation":[{"name":"Northeastern University, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hongshi","family":"Tan","sequence":"additional","affiliation":[{"name":"National University of Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Cheng","family":"Chen","sequence":"additional","affiliation":[{"name":"ByteDance Inc, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Cheng","family":"Zhao","sequence":"additional","affiliation":[{"name":"ByteDance Inc, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jiaming","family":"Tian","sequence":"additional","affiliation":[{"name":"Northeastern University, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jiaxin","family":"Jiang","sequence":"additional","affiliation":[{"name":"National University of Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiaoliang","family":"Cong","sequence":"additional","affiliation":[{"name":"ByteDance Inc, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yanfeng","family":"Zhang","sequence":"additional","affiliation":[{"name":"Northeastern University, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ge","family":"Yu","sequence":"additional","affiliation":[{"name":"Northeastern University, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Weng-Fai","family":"Wong","sequence":"additional","affiliation":[{"name":"National University of Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bingsheng","family":"He","sequence":"additional","affiliation":[{"name":"National University of Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,9,4]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"uk-2005 2005. https:\/\/www.cise.ufl.edu\/research\/sparse\/matrices\/LAW\/uk-2005.html."},{"key":"e_1_2_1_2_1","first-page":"64","volume-title":"International Conference for High Performance Computing, Networking, Storage and Analysis, SC 2021","author":"Tyler","year":"2021","unstructured":"Tyler N. Allen and Rong Ge. In-depth analyses of unified virtual memory system for GPU accelerated computing. In Bronis R. de Supinski, Mary W. Hall, and Todd Gamblin, editors, International Conference for High Performance Computing, Networking, Storage and Analysis, SC 2021, St. Louis, Missouri, USA, November 14\u201319, 2021, page 64. ACM, 2021."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS47924.2020.00081"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3018743.3018756"},{"key":"e_1_2_1_5_1","first-page":"1016","volume-title":"SIGMOD '22: International Conference on Management of Data","author":"Boeschen Nils","year":"2022","unstructured":"Nils Boeschen and Carsten Binnig. Gacco - A gpu-accelerated OLTP DBMS. In Zachary G. Ives, Angela Bonifati, and Amr El Abbadi, editors, SIGMOD '22: International Conference on Management of Data, Philadelphia, PA, USA, June 12 \u2013 17, 2022, pages 1003\u20131016. ACM, 2022."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/HPEC.2018.8547541"},{"key":"e_1_2_1_7_1","unstructured":"Nvidia thrust 2024. https:\/\/developer.nvidia.com\/thrust."},{"key":"e_1_2_1_8_1","unstructured":"Deep graph library:towards efficient and scalable deep learning on graphs 2020. https:\/\/www.dgl.ai\/."},{"key":"e_1_2_1_9_1","unstructured":"Alibaba cloud services 2023. https:\/\/www.alibabacloud.com\/."},{"key":"e_1_2_1_10_1","first-page":"471","volume-title":"SIGMOD '21: International Conference on Management of Data","author":"Fan Wenfei","year":"2021","unstructured":"Wenfei Fan, Chao Tian, Ruiqi Xu, Qiang Yin, Wenyuan Yu, and Jingren Zhou. Incrementalizing graph algorithms. In Guoliang Li, Zhanhuai Li, Stratos Idreos, and Divesh Srivastava, editors, SIGMOD '21: International Conference on Management of Data, Virtual Event, China, June 20\u201325, 2021, pages 459\u2013471. ACM, 2021."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457263"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.14778\/3514061.3514065"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.14778\/3384345.3384358"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.14778\/3461535.3461550"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/HPEC.2016.7761622"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCGrid54584.2022.00016"},{"key":"e_1_2_1_17_1","unstructured":"Cuda threads and atomicsc 2023. https:\/\/mc.stanford.edu\/cgi-bin\/images\/3\/34\/Darve_cme343_cuda_3.pdf."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3627703.3629571"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/PACT.2015.15"},{"key":"e_1_2_1_20_1","first-page":"990","volume-title":"Seo, Jiwon Seo, and Wook-Shin Han. iturbograph: Scaling and automating incremental graph analytics. In SIGMOD '21: International Conference on Management of Data","author":"Ko Seongyun","year":"2021","unstructured":"Seongyun Ko, Taesung Lee, Kijae Hong, Wonseok Lee, In Seo, Jiwon Seo, and Wook-Shin Han. iturbograph: Scaling and automating incremental graph analytics. In SIGMOD '21: International Conference on Management of Data, Virtual Event, China, June 20\u201325, 2021, pages 977\u2013990. ACM, 2021."},{"key":"e_1_2_1_21_1","volume-title":"22nd International World Wide Web Conference, WWW '13","author":"Kunegis J\u00e9r\u00f4me","year":"2013","unstructured":"J\u00e9r\u00f4me Kunegis. KONECT: the koblenz network collection. In 22nd International World Wide Web Conference, WWW '13, Rio de Janeiro, Brazil, May 13\u201317, 2013, Companion Volume, pages 1343\u20131350, 2013."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772751"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/HPCA.2014.6835937"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2023.3268662"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3447786.3456230"},{"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.14778\/3425879.3425883"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476249.3476264"},{"key":"e_1_2_1_29_1","unstructured":"Nsight systems 2023."},{"key":"e_1_2_1_30_1","unstructured":"Open computing language opencl 2023. https:\/\/developer.nvidia.com\/opencl."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3342195.3387537"},{"key":"e_1_2_1_32_1","volume-title":"Everything you need to know about unified memory. https:\/\/on-demand.gputechconf.com\/gtc\/2018\/presentation\/s8430-everything-you-need-to-know-about-unified-memory.pdf","author":"Sakharnykh Nikolay","year":"2018","unstructured":"Nikolay Sakharnykh. Everything you need to know about unified memory. https:\/\/on-demand.gputechconf.com\/gtc\/2018\/presentation\/s8430-everything-you-need-to-know-about-unified-memory.pdf, 2018."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-43659-3_24"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.14778\/3151113.3151122"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3472456.3472457"},{"key":"e_1_2_1_36_1","unstructured":"Thrust 2023. https:\/\/nvidia.github.io\/cccl\/thrust\/api."},{"key":"e_1_2_1_37_1","unstructured":"Nvidia unified addressing 2023. https:\/\/docs.nvidia.com\/cuda\/cuda-driver-api\/group__CUDA__UNIFIED.html."},{"key":"e_1_2_1_38_1","first-page":"283","volume-title":"2021 USENIX Annual Technical Conference, USENIX ATC 2021, July 14\u201316","author":"Vaziri Pourya","year":"2021","unstructured":"Pourya Vaziri and Keval Vora. Controlling memory footprint of stateful streaming graph processing. In Irina Calciu and Geoff Kuenning, editors, 2021 USENIX Annual Technical Conference, USENIX ATC 2021, July 14\u201316, 2021, pages 269\u2013283. USENIX Association, 2021."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3037697.3037748"},{"key":"e_1_2_1_40_1","first-page":"52","volume-title":"Proceedings of the 24th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP 2019","author":"Wang Hao","year":"2019","unstructured":"Hao Wang, Liang Geng, Rubao Lee, Kaixi Hou, Yanfeng Zhang, and Xiaodong Zhang. Sep-graph: finding shortest execution paths for graph processing under a hybrid framework on GPU. In Proceedings of the 24th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP 2019, Washington, DC, USA, February 16\u201320, 2019, pages 38\u201352, 2019."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3444844"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE55515.2023.00049"},{"key":"e_1_2_1_43_1","first-page":"2454","volume-title":"Proceedings of the 2020 International Conference on Management of Data, SIGMOD Conference 2020, online conference [Portland, OR, USA], June 14\u201319","author":"Wang Qiange","year":"2020","unstructured":"Qiange Wang, Yanfeng Zhang, Hao Wang, Liang Geng, Rubao Lee, Xiaodong Zhang, and Ge Yu. Automating incremental and asynchronous evaluation for recursive aggregate data processing. In David Maier, Rachel Pottinger, AnHai Doan, Wang-Chiew Tan, Abdussalam Alawini, and Hung Q. Ngo, editors, Proceedings of the 2020 International Conference on Management of Data, SIGMOD Conference 2020, online conference [Portland, OR, USA], June 14\u201319, 2020, pages 2439\u20132454. ACM, 2020."},{"key":"e_1_2_1_44_1","first-page":"252","volume-title":"The 23rd International Symposium on High-Performance Parallel and Distributed Computing, HPDC'14","author":"Wang Yangzihao","year":"2014","unstructured":"Yangzihao Wang, Andrew A. Davidson, Yuechao Pan, Yuduo Wu, Andy Riffel, and John D. Owens. Gunrock: a high-performance graph processing library on the GPU. In Rafael Asenjo and Tim Harris, editors, The 23rd International Symposium on High-Performance Parallel and Distributed Computing, HPDC'14, Vancouver, BC, Canada - June 23 \u2013 27, 2014, pages 239\u2013252. ACM, 2016."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/SC.2018.00063"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/HPEC.2017.8091058"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-013-0693-z"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/3620665.3640409"},{"key":"e_1_2_1_49_1","series-title":"Lecture Notes in Computer Science","first-page":"484","volume-title":"Wenjie Zhang","author":"Zhang Fan","year":"2021","unstructured":"Fan Zhang, Lei Zou, and Yanpeng Yu. LPMA - an efficient data structure for dynamic graph on gpus. In Wenjie Zhang, Lei Zou, Zakaria Maamar, and Lu Chen, editors, Web Information Systems Engineering - WISE 2021 - 22nd International Conference on Web Information Systems Engineering, WISE 2021, Melbourne, VIC, Australia, October 26\u201329, 2021, Proceedings, Part I, volume 13080 of Lecture Notes in Computer Science, pages 469\u2013484. Springer, 2021."},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2013.235"},{"issue":"6","key":"e_1_2_1_51_1","first-page":"5823","article-title":"Efficient concurrent gpu-based dynamic graph processing","volume":"35","author":"Zhang Yu","year":"2023","unstructured":"Yu Zhang, Yuxuan Liang, Jin Zhao, Fubing Mao, Lin Gu, Xiaofei Liao, Hai Jin, Haikun Liu, Song Guo, Yangqing Zeng, Hang Hu, Chen Li, Ji Zhang, and Biao Wang. Egraph: Efficient concurrent gpu-based dynamic graph processing. IEEE Trans. Knowl. Data Eng., 35(6):5823\u20135836, 2023.","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/3477603"},{"key":"e_1_2_1_53_1","first-page":"588","volume-title":"2020 USENIX Annual Technical Conference, USENIX ATC 2020, July 15\u201317","author":"Zheng Long","year":"2020","unstructured":"Long Zheng, Xianliang Li, Yaohui Zheng, Yu Huang, Xiaofei Liao, Hai Jin, Jingling Xue, Zhiyuan Shao, and Qiang-Sheng Hua. Scaph: Scalable gpu-accelerated graph processing with value-driven differential scheduling. In Ada Gavrilovska and Erez Zadok, editors, 2020 USENIX Annual Technical Conference, USENIX ATC 2020, July 15\u201317, 2020, pages 573\u2013588. USENIX Association, 2020."},{"key":"e_1_2_1_54_1","volume-title":"2015 USENIX Annual Technical Conference, USENIX ATC '15, July 8\u201310","author":"Zhu Xiaowei","year":"2015","unstructured":"Xiaowei Zhu, Wentao Han, and Wenguang Chen. Gridgraph: Large-scale graph processing on a single machine using 2-level hierarchical partitioning. In Shan Lu and Erik Riedel, editors, 2015 USENIX Annual Technical Conference, USENIX ATC '15, July 8\u201310, Santa Clara, CA, USA, pages 375\u2013386. USENIX Association, 2015."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3749646.3749659","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,5]],"date-time":"2025-09-05T03:06:28Z","timestamp":1757041588000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3749646.3749659"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7]]},"references-count":54,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2025,7]]}},"alternative-id":["10.14778\/3749646.3749659"],"URL":"https:\/\/doi.org\/10.14778\/3749646.3749659","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2025,7]]},"assertion":[{"value":"2025-09-04","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}