{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,16]],"date-time":"2026-05-16T20:19:54Z","timestamp":1778962794250,"version":"3.51.4"},"reference-count":62,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2022,11,11]],"date-time":"2022-11-11T00:00:00Z","timestamp":1668124800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100012166","name":"National Key R&D Program of China","doi-asserted-by":"crossref","award":["2018YFB1800203"],"award-info":[{"award-number":["2018YFB1800203"]}],"id":[{"id":"10.13039\/501100012166","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100004739","name":"Youth Innovation Promotion Association CAS","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100004739","id-type":"DOI","asserted-by":"crossref"}]},{"name":"GRF","award":["14200420"],"award-info":[{"award-number":["14200420"]}]},{"DOI":"10.13039\/501100001809","name":"National Science Foundation of China","doi-asserted-by":"crossref","award":["62172361"],"award-info":[{"award-number":["62172361"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Storage"],"published-print":{"date-parts":[[2022,11,30]]},"abstract":"<jats:p>\n            Traditional graph systems mainly use the iteration-based model, which iteratively loads graph blocks into memory for analysis so as to reduce random I\/Os. However, this iteration-based model limits the efficiency and scalability of running random walk, which is a fundamental technique to analyze large graphs. In this article, we first propose a state-aware I\/O model to improve the I\/O efficiency of running random walk, then we develop a block-centric indexing and buffering scheme for managing walk data, and leverage an asynchronous walk updating strategy to improve random walk efficiency. We implement an I\/O-efficient graph system,\n            <jats:sans-serif>GraphWalker<\/jats:sans-serif>\n            , which is efficient to handle very large disk-resident graphs and also scalable to run tens of billions of random walks with only a single commodity machine. Experiments show that\n            <jats:sans-serif>GraphWalker<\/jats:sans-serif>\n            can achieve more than an order of magnitude speedup when compared with DrunkardMob, which is tailored for random walks based on the classical graph system GraphChi, as well as two state-of-the-art single-machine graph systems, Graphene and GraFSoft. Furthermore, when compared with the most recent distributed system KnightKing,\n            <jats:sans-serif>GraphWalker<\/jats:sans-serif>\n            still achieves comparable performance with only a single machine, thereby making it a more cost-effective alternative.\n          <\/jats:p>","DOI":"10.1145\/3533579","type":"journal-article","created":{"date-parts":[[2022,9,27]],"date-time":"2022-09-27T11:25:22Z","timestamp":1664277922000},"page":"1-33","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Toward Fast and Scalable Random Walks over Disk-Resident Graphs via Efficient I\/O Management"],"prefix":"10.1145","volume":"18","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8915-4169","authenticated-orcid":false,"given":"Rui","family":"Wang","sequence":"first","affiliation":[{"name":"University of Science and Technology of China, Hefei, The People\u2019s Republic of China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3743-8511","authenticated-orcid":false,"given":"Yongkun","family":"Li","sequence":"additional","affiliation":[{"name":"University of Science and Technology of China, Hefei, The People\u2019s Republic of China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9586-0561","authenticated-orcid":false,"given":"Yinlong","family":"Xu","sequence":"additional","affiliation":[{"name":"University of Science and Technology of China, Hefei, The People\u2019s Republic of China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7935-7210","authenticated-orcid":false,"given":"Hong","family":"Xie","sequence":"additional","affiliation":[{"name":"Chongqing University, Chongqing, The People\u2019s Republic of China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7466-0384","authenticated-orcid":false,"given":"John C. S.","family":"Lui","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong, Hong Kong SAR, The People\u2019s Republic of China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7075-4153","authenticated-orcid":false,"given":"Shuibing","family":"He","sequence":"additional","affiliation":[{"name":"Zhejiang University, Hangzhou, The People\u2019s Republic of China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,11,11]]},"reference":[{"key":"e_1_3_1_2_2","unstructured":"Friendster. [n.d]. Home Page. http:\/\/konect.uni-koblenz.de\/networks\/friendster."},{"key":"e_1_3_1_3_2","unstructured":"Graph500. [n.d]. Home Page. Retrieved October 5 2022 from https:\/\/graph500.org\/."},{"key":"e_1_3_1_4_2","unstructured":"Web Data Commons. [n.d]. The 2012 Common Crawl Graph. Available at http:\/\/webdatacommons.org."},{"key":"e_1_3_1_5_2","unstructured":"ANLAB Traces. [n.d]. Twitter. Available at http:\/\/an.kaist.ac.kr\/traces\/WWW2010.html."},{"key":"e_1_3_1_6_2","unstructured":"Yahoo! [n.d]. Yahoo Webscope Program. Retrieved October 5 2022 from http:\/\/webscope.sandbox.yahoo.com."},{"key":"e_1_3_1_7_2","volume-title":"Proceedings of USENIX ATC","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 Proceedings of USENIX ATC."},{"key":"e_1_3_1_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/1367497.1367525"},{"key":"e_1_3_1_9_2","volume-title":"Proceedings of VLDB","author":"Bar-Yossef Ziv","year":"2000","unstructured":"Ziv Bar-Yossef, Alexander Berg, Steve Chien, Jittat Fakcharoenphol, and Dror Weitz. 2000. Approximating aggregate queries about web pages via random walks. In Proceedings of VLDB."},{"key":"e_1_3_1_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/3190508.3190545"},{"key":"e_1_3_1_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/2741948.2741970"},{"key":"e_1_3_1_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/1557019.1557047"},{"key":"e_1_3_1_13_2","volume-title":"Proceedings of FAST","author":"Zheng Disa Mhembere Da","year":"2015","unstructured":"Disa Mhembere Da Zheng, Randal Burns, Joshua Vogelstein, Carey E. Priebe, and Alexander S. Szalay. 2015. FlashGraph: Processing billion-node graphs on an array of commodity SSDs. In Proceedings of FAST."},{"key":"e_1_3_1_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/1367497.1367646"},{"key":"e_1_3_1_15_2","volume-title":"Proceedings of FAST","author":"Elyasi Nima","year":"2019","unstructured":"Nima Elyasi, Changho Choi, and Anand Sivasubramaniam. 2019. Large-scale graph processing on emerging storage devices. In Proceedings of FAST."},{"key":"e_1_3_1_16_2","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2005.10129104"},{"key":"e_1_3_1_17_2","volume-title":"Proceedings of VLDB","author":"Gonzalez Hector","year":"2007","unstructured":"Hector Gonzalez, Jiawei Han, Xiaolei Li, Margaret Myslinska, and John Paul Sondag. 2007. Adaptive fastest path computation on a road network: A traffic mining approach. In Proceedings of VLDB."},{"key":"e_1_3_1_18_2","volume-title":"Proceedings of OSDI","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 OSDI."},{"key":"e_1_3_1_19_2","volume-title":"Proceedings of OSDI","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 OSDI."},{"key":"e_1_3_1_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939754"},{"key":"e_1_3_1_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/511446.511513"},{"key":"e_1_3_1_22_2","doi-asserted-by":"publisher","DOI":"10.1016\/S1389-1286(99)00016-X"},{"key":"e_1_3_1_23_2","doi-asserted-by":"crossref","unstructured":"Sungpack Hong Hassan Chafi Edic Sedlar and Kunle Olukotun. 2012. Green-Marl: A DSL for easy and efficient graph analysis. ACM SIGPLAN Notices 47 4 (2012) 349\u2013362.","DOI":"10.1145\/2248487.2151013"},{"key":"e_1_3_1_24_2","volume-title":"Proceedings of LWA","author":"Hotho Andreas","year":"2006","unstructured":"Andreas Hotho, Robert J\u00e4schke, Christoph Schmitz, Gerd Stumme, and Klaus-Dieter Althoff. 2006. FolkRank: A ranking algorithm for folksonomies. In Proceedings of LWA."},{"key":"e_1_3_1_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/1557019.1557067"},{"key":"e_1_3_1_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/775047.775126"},{"key":"e_1_3_1_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/775152.775191"},{"key":"e_1_3_1_28_2","doi-asserted-by":"publisher","DOI":"10.1109\/ISCA.2018.00042"},{"key":"e_1_3_1_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/956750.956769"},{"key":"e_1_3_1_30_2","volume-title":"Proceedings of USENIX ATC","author":"Khan Arijit","year":"2018","unstructured":"Arijit Khan, Gustavo Segovia, and Donald Kossmann. 2018. On smart query routing: For distributed graph querying with decoupled storage. In Proceedings of USENIX ATC."},{"key":"e_1_3_1_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/2600212.2600227"},{"key":"e_1_3_1_32_2","doi-asserted-by":"publisher","DOI":"10.1145\/2507157.2507173"},{"key":"e_1_3_1_33_2","volume-title":"Proceedings of OSDI","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 Proceedings of OSDI."},{"key":"e_1_3_1_34_2","volume-title":"Internet Mathematics","year":"2004","unstructured":"A. N. Langville and C. D. Meyer. 2004. Deeper inside PageRank. Internet Mathematics 1, 3 (2004), 335\u2013380."},{"key":"e_1_3_1_35_2","doi-asserted-by":"publisher","DOI":"10.1145\/2254756.2254795"},{"key":"e_1_3_1_36_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2014.6816696"},{"key":"e_1_3_1_37_2","doi-asserted-by":"crossref","unstructured":"Hang Liu and H. Howie Huang. 2015. Enterprise: Breadth-first graph traversal on GPUs. In Proceedings of SC . IEEE Los Alamitos CA.","DOI":"10.1145\/2807591.2807594"},{"key":"e_1_3_1_38_2","volume-title":"Proceedings of FAST","author":"Liu Hang","year":"2017","unstructured":"Hang Liu and H. Howie Huang. 2017. Graphene: Fine-grained IO management for graph computing. In Proceedings of FAST."},{"key":"e_1_3_1_39_2","unstructured":"Christian Lochert Hannes Hartenstein Jing Tian Holger Fussler Dagmar Hermann and Martin Mauve. 2003. A routing strategy for vehicular ad hoc networks in city environments. In Proceedings of IV . IEEE Los Alamitos CA."},{"key":"e_1_3_1_40_2","doi-asserted-by":"publisher","DOI":"10.14778\/2212351.2212354"},{"key":"e_1_3_1_41_2","doi-asserted-by":"publisher","DOI":"10.1145\/3064176.3064191"},{"key":"e_1_3_1_42_2","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807184"},{"key":"e_1_3_1_43_2","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522739"},{"key":"e_1_3_1_44_2","article-title":"The PageRank Citation Ranking: Bring Order to the Web","author":"Page Larry","year":"1998","unstructured":"Larry Page. 1998. The PageRank Citation Ranking: Bring Order to the Web. Technical Report. Stanford University.","journal-title":"Technical Report."},{"key":"e_1_3_1_45_2","doi-asserted-by":"publisher","DOI":"10.1145\/1014052.1014135"},{"key":"e_1_3_1_46_2","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btl301"},{"key":"e_1_3_1_47_2","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/bth436"},{"key":"e_1_3_1_48_2","doi-asserted-by":"publisher","DOI":"10.1145\/1879141.1879192"},{"key":"e_1_3_1_49_2","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522740"},{"key":"e_1_3_1_50_2","volume-title":"Proceedings of AAAI","author":"Rusmevichientong Paat","year":"2001","unstructured":"Paat Rusmevichientong, David M. Pennock, Steve Lawrence, and C. Lee Giles. 2001. Methods for sampling pages uniformly from the World Wide Web. In Proceedings of AAAI."},{"key":"e_1_3_1_51_2","doi-asserted-by":"crossref","unstructured":"Julian Shun and Guy E. Blelloch. 2013. Ligra: A lightweight graph processing framework for shared memory. ACM SIGPLAN Notices 48 8 (2013) 135\u2013146.","DOI":"10.1145\/2517327.2442530"},{"key":"e_1_3_1_52_2","doi-asserted-by":"publisher","DOI":"10.1145\/2815400.2815410"},{"key":"e_1_3_1_53_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2006.70"},{"key":"e_1_3_1_54_2","volume-title":"Proceedings of USENIX ATC","author":"Vora Keval","year":"2019","unstructured":"Keval Vora. 2019. LUMOS: Dependency-driven disk-based graph processing. In Proceedings of USENIX ATC."},{"key":"e_1_3_1_55_2","volume-title":"Proceedings of USENIX ATC","author":"Vora Keval","year":"2016","unstructured":"Keval Vora, Guoqing (Harry) Xu, and Rajiv Gupta. 2016. Load the edges you need: A generic I\/O optimization for disk-based graph processing. In Proceedings of USENIX ATC."},{"key":"e_1_3_1_56_2","doi-asserted-by":"publisher","DOI":"10.1504\/IJHPCN.2019.099747"},{"key":"e_1_3_1_57_2","doi-asserted-by":"crossref","unstructured":"Yangzihao Wang Andrew Davidson Yuechao Pan Yuduo Wu Andy Riffel and John D. Owens. 2016. Gunrock: A high-performance graph processing library on the GPU. ACM SIGPLAN Notices 51 8 (2016) Article 11 12 pages.","DOI":"10.1145\/3016078.2851145"},{"key":"e_1_3_1_58_2","doi-asserted-by":"publisher","DOI":"10.1145\/3477132.3483575"},{"key":"e_1_3_1_59_2","doi-asserted-by":"publisher","DOI":"10.1145\/3341301.3359634"},{"key":"e_1_3_1_60_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-55699-4_20"},{"key":"e_1_3_1_61_2","volume-title":"Proceedings of OSDI","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 Proceedings of OSDI."},{"key":"e_1_3_1_62_2","doi-asserted-by":"publisher","DOI":"10.14778\/3384345.3384351"},{"key":"e_1_3_1_63_2","volume-title":"Proceedings of USENIX ATC","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 Proceedings of USENIX ATC."}],"container-title":["ACM Transactions on Storage"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3533579","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3533579","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:00:17Z","timestamp":1750186817000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3533579"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,11,11]]},"references-count":62,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,11,30]]}},"alternative-id":["10.1145\/3533579"],"URL":"https:\/\/doi.org\/10.1145\/3533579","relation":{},"ISSN":["1553-3077","1553-3093"],"issn-type":[{"value":"1553-3077","type":"print"},{"value":"1553-3093","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,11,11]]},"assertion":[{"value":"2021-08-30","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-04-25","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-11-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}