{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,8]],"date-time":"2026-05-08T22:21:22Z","timestamp":1778278882896,"version":"3.51.4"},"reference-count":59,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2025,2,8]],"date-time":"2025-02-08T00:00:00Z","timestamp":1738972800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"The Research Grants Council of Hong Kong SAR","award":["CUHK14208521"],"award-info":[{"award-number":["CUHK14208521"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Storage"],"published-print":{"date-parts":[[2025,5,31]]},"abstract":"<jats:p>Fully-external graph computation systems exhibit optimal scalability by computing the ever-growing, large-scale graph with a constant amount of memory on a single machine. In particular, they keep the entire massive graph data in storage and iteratively load parts of them into memory for computation. Nevertheless, despite the merit of optimal scalability, their unreasonably-low efficiency often makes them uncompetitive, and even unpractical, to the other types of graph computation systems. The key rationale is that most existing fully-external graph computation systems over-emphasize retrieving graph data from storage through sequential access. Although this principle achieves high storage bandwidth, it often causes reading excessive and irrelevant data, which can severely degrade their overall efficiency.<\/jats:p>\n          <jats:p>\n            Therefore, this work presents Seraph, a fully-external graph computation system that achieves optimal\n            <jats:underline>S<\/jats:underline>\n            calability while toward satisfactory\n            <jats:underline>E<\/jats:underline>\n            fficiency improvement. Particularly, inspired by the modern storage offering comparable sequential and random access speeds, Seraph adopts the principle of\n            <jats:italic>on-demand processing<\/jats:italic>\n            to access the necessary graph data for saving I\/O while enjoying the decent speed in random access. On the basis of this principle, Seraph further devises three practical designs to bring excellent performance leap to fully-external graph computation: 1) the hybrid format to represent the graph data for striking a good balance between I\/O amount and access locality, 2) the vertex passing to enable efficient vertex updates on top of hybrid format, and 3) the selective pre-computation to re-use the loaded data for I\/O reduction. Our evaluations reveal that Seraph notably outperforms other state-of-the-art fully-external systems under all the evaluated billion-scale graphs and representative graph algorithms by up to two orders of magnitude.\n          <\/jats:p>","DOI":"10.1145\/3701037","type":"journal-article","created":{"date-parts":[[2024,11,23]],"date-time":"2024-11-23T10:13:13Z","timestamp":1732356793000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Leveraging On-demand Processing to Co-optimize Scalability and Efficiency for Fully-external Graph Computation"],"prefix":"10.1145","volume":"21","author":[{"ORCID":"https:\/\/orcid.org\/0009-0002-8992-480X","authenticated-orcid":false,"given":"Tsun-Yu","family":"Yang","sequence":"first","affiliation":[{"name":"The Chinese University of Hong Kong, Hong Kong, Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-8226-6856","authenticated-orcid":false,"given":"Yizou","family":"Chen","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong, Hong Kong, Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5974-8134","authenticated-orcid":false,"given":"Yuhong","family":"Liang","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong, Hong Kong, Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4029-757X","authenticated-orcid":false,"given":"Ming-Chang","family":"Yang","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong, Hong Kong, Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,2,8]]},"reference":[{"key":"e_1_3_2_2_2","first-page":"125","volume-title":"2017 USENIX Annual Technical Conference (USENIX ATC 17)","author":"Ai Zhiyuan","year":"2017","unstructured":"Zhiyuan Ai, Mingxing Zhang, Yongwei Wu, Xuehai Qian, Kang Chen, and Weimin Zheng. 2017. Squeezing out all the value of loaded data: An out-of-core graph processing system with reduced disk I\/O. In 2017 USENIX Annual Technical Conference (USENIX ATC 17). USENIX Association, Santa Clara, CA, USA, 125\u2013137. https:\/\/www.usenix.org\/conference\/atc17\/technical-sessions\/presentation\/ai"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1109\/SC.2012.50"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/1963405.1963488"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/988672.988752"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/2741948.2741970"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/3038912.3052608"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/3020078.3021739"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/3192366.3192404"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/3314221.3314598"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/644108.644226"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.5555\/3323298.3323327"},{"key":"e_1_3_2_13_2","unstructured":"Eu2015. https:\/\/law.di.unimi.it\/webdata\/eu-2015\/. Accessed December 1 2024."},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/316194.316229"},{"key":"e_1_3_2_15_2","first-page":"17","volume-title":"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). USENIX Association, Hollywood, CA, 17\u201330. https:\/\/www.usenix.org\/conference\/osdi12\/technical-sessions\/presentation\/gonzalez"},{"key":"e_1_3_2_16_2","unstructured":"Gsh2015. https:\/\/law.di.unimi.it\/webdata\/gsh-2015\/. Accessed December 1 2024."},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/511446.511513"},{"key":"e_1_3_2_18_2","doi-asserted-by":"crossref","unstructured":"John Hopcroft and Robert Tarjan. Algorithm 447: Efficient algorithms for graph manipulation.(Communications of the ACM 16(6):372\u2013378 1973.).","DOI":"10.1145\/362248.362272"},{"key":"e_1_3_2_19_2","unstructured":"Intel-Optane-905P-SSD.https:\/\/www.intel.com\/content\/www\/us\/en\/products\/details\/memory-storage\/consumer-ssds\/optane-ssd-9-series.html"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1038\/35075138"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1109\/ISCA.2018.00042"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1109\/PACT.2015.15"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ijinfomgt.2017.08.003"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/3364180"},{"key":"e_1_3_2_25_2","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, USA, 31\u201346. https:\/\/www.usenix.org\/conference\/osdi12\/technical-sessions\/presentation\/kyrola"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/3380942"},{"key":"e_1_3_2_27_2","first-page":"427","volume-title":"2018 USENIX Annual Technical Conference (USENIX ATC 18)","author":"Lakhotia Kartik","year":"2018","unstructured":"Kartik Lakhotia, Rajgopal Kannan, and Viktor Prasanna. 2018. Accelerating PageRank using partition-centric processing. In 2018 USENIX Annual Technical Conference (USENIX ATC 18). USENIX Association, Boston, MA, USA, 427\u2013440. https:\/\/www.usenix.org\/conference\/atc18\/presentation\/lakhotia"},{"key":"e_1_3_2_28_2","unstructured":"Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. http:\/\/snap.stanford.edu\/data. (June2014)."},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","unstructured":"Hang Liu H. Huang and Yang Hu. 2016. iBFS: Concurrent breadth-first search on GPUs. 403\u2013416. 10.1145\/2882903.2882959","DOI":"10.1145\/2882903.2882959"},{"key":"e_1_3_2_30_2","first-page":"285","volume-title":"15th USENIX Conference on File and Storage Technologies (FAST 17)","author":"Liu Hang","year":"2017","unstructured":"Hang Liu and H. Howie Huang. 2017. Graphene: Fine-grained IO management for graph computing. In 15th USENIX Conference on File and Storage Technologies (FAST 17). USENIX Association, Santa Clara, CA, USA, 285\u2013300. https:\/\/www.usenix.org\/conference\/fast17\/technical-sessions\/presentation\/liu"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2015.7113298"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.98.062413"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807184"},{"key":"e_1_3_2_34_2","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1145\/3447786.3456230","volume-title":"Proceedings of the Sixteenth European Conference on Computer Systems","author":"Mariappan Mugilan","year":"2021","unstructured":"Mugilan Mariappan, Joanna Che, and Keval Vora. 2021. DZiG: Sparsity-aware incremental processing of streaming graphs. In Proceedings of the Sixteenth European Conference on Computer Systems. 83\u201398."},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1145\/3302424.3303974"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/3307650.3322275"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2012.124"},{"key":"e_1_3_2_38_2","unstructured":"Edward F. Moore.The shortest path through a maze.(In Proceedings of the International Symposium on the Switching Theory 1959 pages 285\u2013292)."},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1145\/2807591.2807626"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522739"},{"key":"e_1_3_2_41_2","volume-title":"The PageRank Citation Ranking: Bringing Order to the Web.","author":"Page Lawrence","year":"1999","unstructured":"Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. 1999. The PageRank Citation Ranking: Bringing Order to the Web.Technical Report 1999-66. Stanford InfoLab. http:\/\/ilpubs.stanford.edu:8090\/422\/Previous number = SIDL-WP-1999-0120."},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457313"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522740"},{"key":"e_1_3_2_44_2","unstructured":"Samsung-860-EVO-SSD.https:\/\/www.samsung.com\/semiconductor\/minisite\/ssd\/product\/consumer\/860evo\/"},{"key":"e_1_3_2_45_2","unstructured":"Samsung-970-PRO-SSD.https:\/\/www.samsung.com\/semiconductor\/minisite\/ssd\/product\/consumer\/970pro\/"},{"key":"e_1_3_2_46_2","doi-asserted-by":"publisher","DOI":"10.14778\/2536336.2536344"},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","DOI":"10.1145\/2517327.2442530"},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.1109\/DCC.2015.8"},{"key":"e_1_3_2_49_2","doi-asserted-by":"publisher","DOI":"10.14778\/2735496.2735507"},{"key":"e_1_3_2_50_2","unstructured":"Twitter. https:\/\/law.di.unimi.it\/webdata\/twitter-2010\/. Accessed December 1 2024."},{"key":"e_1_3_2_51_2","first-page":"429","volume-title":"2019 USENIX Annual Technical Conference (USENIX ATC 19)","author":"Vora Keval","year":"2019","unstructured":"Keval Vora. 2019. LUMOS: Dependency-driven disk-based graph processing. In 2019 USENIX Annual Technical Conference (USENIX ATC 19). USENIX Association, Renton, WA, USA, 429\u2013442. https:\/\/www.usenix.org\/conference\/atc19\/presentation\/vora"},{"key":"e_1_3_2_52_2","doi-asserted-by":"publisher","DOI":"10.1145\/3037697.3037748"},{"key":"e_1_3_2_53_2","first-page":"507","volume-title":"2016 USENIX Annual Technical Conference (USENIX ATC 16)","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 2016 USENIX Annual Technical Conference (USENIX ATC 16). USENIX Association, Denver, CO, USA, 507\u2013522. https:\/\/www.usenix.org\/conference\/atc16\/technical-sessions\/presentation\/vora"},{"key":"e_1_3_2_54_2","doi-asserted-by":"publisher","DOI":"10.1145\/3620665.3640409"},{"key":"e_1_3_2_55_2","doi-asserted-by":"publisher","DOI":"10.2991\/msam-17.2017.68"},{"key":"e_1_3_2_56_2","doi-asserted-by":"publisher","DOI":"10.1145\/3296957.3173208"},{"key":"e_1_3_2_57_2","first-page":"45","volume-title":"13th USENIX Conference on File and Storage Technologies (FAST 15)","author":"Zheng Da","year":"2015","unstructured":"Da Zheng, Disa Mhembere, Randal Burns, Joshua Vogelstein, Carey E. Priebe, and Alexander S. Szalay. 2015. FlashGraph: Processing billion-node graphs on an array of commodity SSDs. In 13th USENIX Conference on File and Storage Technologies (FAST 15). USENIX Association, Santa Clara, CA, USA, 45\u201358. https:\/\/www.usenix.org\/conference\/fast15\/technical-sessions\/presentation\/zheng"},{"key":"e_1_3_2_58_2","first-page":"301","volume-title":"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, USA, 301\u2013316. https:\/\/www.usenix.org\/conference\/osdi16\/technical-sessions\/presentation\/zhu"},{"key":"e_1_3_2_59_2","volume-title":"Learning from Labeled and Unlabeled Data with Label Propagation","author":"Zhu Xiaojin","year":"2002","unstructured":"Xiaojin Zhu and Zoubin Ghahramani. 2002. Learning from Labeled and Unlabeled Data with Label Propagation. Technical Report."},{"key":"e_1_3_2_60_2","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, USA, 375\u2013386. https:\/\/www.usenix.org\/conference\/atc15\/technical-session\/presentation\/zhu"}],"container-title":["ACM Transactions on Storage"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3701037","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3701037","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:17:24Z","timestamp":1750295844000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3701037"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,2,8]]},"references-count":59,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,5,31]]}},"alternative-id":["10.1145\/3701037"],"URL":"https:\/\/doi.org\/10.1145\/3701037","relation":{},"ISSN":["1553-3077","1553-3093"],"issn-type":[{"value":"1553-3077","type":"print"},{"value":"1553-3093","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,2,8]]},"assertion":[{"value":"2024-05-29","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-10-04","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-02-08","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}