{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T10:50:21Z","timestamp":1770979821947,"version":"3.50.1"},"reference-count":63,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2023,7,19]],"date-time":"2023-07-19T00:00:00Z","timestamp":1689724800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"National Key Research and Development Program of China","award":["2022YFB2404202"],"award-info":[{"award-number":["2022YFB2404202"]}]},{"DOI":"10.13039\/501100001809","name":"NSFC","doi-asserted-by":"crossref","award":["62072193"],"award-info":[{"award-number":["62072193"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Major Scientific Research Project of Zhejiang Lab","award":["2022PI0AC03"],"award-info":[{"award-number":["2022PI0AC03"]}]},{"name":"CCF-AFSG Research Fund","award":["RF20220211"],"award-info":[{"award-number":["RF20220211"]}]},{"name":"Young Top-notch Talent Cultivation Program of Hubei Province"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Archit. Code Optim."],"published-print":{"date-parts":[[2023,9,30]]},"abstract":"<jats:p>\n            With the increasing need for graph analysis, massive\n            <jats:italic>Concurrent iterative Graph Processing<\/jats:italic>\n            (CGP) jobs are usually performed on the common large-scale real-world graph. Although several solutions have been proposed, these CGP jobs are not coordinated with the consideration of the inherent dependencies in graph data driven by graph topology. As a result, they suffer from redundant and fragmented accesses of the same underlying graph dispersed over distributed platform, because the same graph is typically irregularly traversed by these jobs along different paths at the same time.\n          <\/jats:p>\n          <jats:p>\n            In this work, we develop\n            <jats:italic>GraphTune<\/jats:italic>\n            , which can be integrated into existing distributed graph processing systems, such as D-Galois, Gemini, PowerGraph, and Chaos, to efficiently perform CGP jobs and enhance system throughput. The key component of GraphTune is a dependency-aware synchronous execution engine in conjunction with several optimization strategies based on the constructed cross-iteration dependency graph of chunks. Specifically, GraphTune transparently regularizes the processing behavior of the CGP jobs in a novel synchronous way and assigns the chunks of graph data to be handled by them based on the topological order of the dependency graph so as to maximize the performance. In this way, it can transform the irregular accesses of the chunks into more regular ones so that as many CGP jobs as possible can fully share the data accesses to the common graph. Meanwhile, it also efficiently synchronizes the communications launched by different CGP jobs based on the dependency graph to minimize the communication cost. We integrate it into four cutting-edge distributed graph processing systems and a popular out-of-core graph processing system to demonstrate the efficiency of GraphTune. Experimental results show that GraphTune improves the throughput of CGP jobs by 3.1\u223c6.2, 3.8\u223c8.5, 3.5\u223c10.8, 4.3\u223c12.4, and 3.8\u223c6.9 times over D-Galois, Gemini, PowerGraph, Chaos, and GraphChi, respectively.\n          <\/jats:p>","DOI":"10.1145\/3600091","type":"journal-article","created":{"date-parts":[[2023,5,26]],"date-time":"2023-05-26T11:12:05Z","timestamp":1685099525000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["GraphTune: An Efficient Dependency-Aware Substrate to Alleviate Irregularity in Concurrent Graph Processing"],"prefix":"10.1145","volume":"20","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4217-7886","authenticated-orcid":false,"given":"Jin","family":"Zhao","sequence":"first","affiliation":[{"name":"Zhejiang Lab &amp; Huazhong University of Science and Technology, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0718-8045","authenticated-orcid":false,"given":"Yu","family":"Zhang","sequence":"additional","affiliation":[{"name":"Huazhong University of Science and Technology, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5671-0576","authenticated-orcid":false,"given":"Ligang","family":"He","sequence":"additional","affiliation":[{"name":"University of Warwick, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-9559-9800","authenticated-orcid":false,"given":"Qikun","family":"Li","sequence":"additional","affiliation":[{"name":"Huazhong University of Science and Technology, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0008-6054-6036","authenticated-orcid":false,"given":"Xiang","family":"Zhang","sequence":"additional","affiliation":[{"name":"Huazhong University of Science and Technology, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0029-6027","authenticated-orcid":false,"given":"Xinyu","family":"Jiang","sequence":"additional","affiliation":[{"name":"Huazhong University of Science and Technology, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6559-6111","authenticated-orcid":false,"given":"Hui","family":"Yu","sequence":"additional","affiliation":[{"name":"Huazhong University of Science and Technology, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6302-813X","authenticated-orcid":false,"given":"Xiaofei","family":"Liao","sequence":"additional","affiliation":[{"name":"Huazhong University of Science and Technology, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3934-7605","authenticated-orcid":false,"given":"Hai","family":"Jin","sequence":"additional","affiliation":[{"name":"Huazhong University of Science and Technology, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6525-9334","authenticated-orcid":false,"given":"Lin","family":"Gu","sequence":"additional","affiliation":[{"name":"Huazhong University of Science and Technology, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4290-1408","authenticated-orcid":false,"given":"Haikun","family":"Liu","sequence":"additional","affiliation":[{"name":"Huazhong University of Science and Technology, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8618-4581","authenticated-orcid":false,"given":"Bingsheng","family":"He","sequence":"additional","affiliation":[{"name":"National University of Singapore, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1244-2880","authenticated-orcid":false,"given":"Ji","family":"Zhang","sequence":"additional","affiliation":[{"name":"University of Southern Queensland, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0005-6700-4713","authenticated-orcid":false,"given":"Xianzheng","family":"Song","sequence":"additional","affiliation":[{"name":"ANT Group, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9807-9479","authenticated-orcid":false,"given":"Lin","family":"Wang","sequence":"additional","affiliation":[{"name":"ANT Group, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6033-6102","authenticated-orcid":false,"given":"Jun","family":"Zhou","sequence":"additional","affiliation":[{"name":"ANT Group, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,7,19]]},"reference":[{"key":"e_1_3_1_2_2","unstructured":"Facebook. 2023. Retrieved 21 March 2023 from http:\/\/www.facebook.com\/."},{"key":"e_1_3_1_3_2","unstructured":"Google. 2023. Retrieved 21 March 2023 from http:\/\/www.google.com\/."},{"key":"e_1_3_1_4_2","unstructured":"Graph500. 2023. Retrieved 21 March 2023 from http:\/\/graph500.org\/?page_id=12#sec-6_1.com\/."},{"key":"e_1_3_1_5_2","unstructured":"LAW. 2023. Retrieved 21 March 2023 from http:\/\/law.di.unimi.it\/datasets.php."},{"key":"e_1_3_1_6_2","unstructured":"SNAP. 2023.  Retrieved 21 March 2023 from http:\/\/snap.stanford.edu\/data\/index.html."},{"key":"e_1_3_1_7_2","unstructured":"Tencent. 2023. Retrieved 21 March 2023 from https:\/\/www.tencent.com\/en-us\/about.html\/."},{"key":"e_1_3_1_8_2","unstructured":"Twitter. 2023. Retrieved 21 March 2023 from https:\/\/www.twitter.com\/."},{"key":"e_1_3_1_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/2938436"},{"key":"e_1_3_1_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/2312005.2312058"},{"key":"e_1_3_1_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/1963405.1963488"},{"key":"e_1_3_1_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/1480506.1480511"},{"key":"e_1_3_1_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2463718"},{"key":"e_1_3_1_14_2","first-page":"49","volume-title":"Proceedings of the 2013 USENIX Annual Technical Conference","author":"Bronson Nathan","year":"2013","unstructured":"Nathan Bronson, Zach Amsden, George Cabrera, Prasad Chakka, Peter Dimov, Hui Ding, Jack Ferris, Anthony Giardullo, Sachin Kulkarni, Harry C. Li, Mark Marchukov, Dmitri Petrov, Lovro Puzar, Yee Jiun Song, and Venkateshwaran Venkataramani. 2013. TAO: Facebook\u2019s distributed data store for the social graph. In Proceedings of the 2013 USENIX Annual Technical Conference. 49\u201360."},{"key":"e_1_3_1_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/2063384.2063471"},{"key":"e_1_3_1_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/3458817.3476159"},{"key":"e_1_3_1_17_2","doi-asserted-by":"publisher","DOI":"10.1109\/CLUSTER.2017.72"},{"key":"e_1_3_1_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/3192366.3192404"},{"key":"e_1_3_1_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/321694.321699"},{"key":"e_1_3_1_20_2","first-page":"17","volume-title":"Proceedings of the 10th USENIX Symposium 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 Symposium on Operating Systems Design and Implementation. 17\u201330."},{"key":"e_1_3_1_21_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2016.0027"},{"key":"e_1_3_1_22_2","doi-asserted-by":"publisher","DOI":"10.14778\/3067421.3067425"},{"key":"e_1_3_1_23_2","doi-asserted-by":"publisher","DOI":"10.14778\/2777598.2777604"},{"key":"e_1_3_1_24_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.patcog.2017.04.018"},{"key":"e_1_3_1_25_2","doi-asserted-by":"publisher","DOI":"10.34133\/2022\/9806758"},{"key":"e_1_3_1_26_2","doi-asserted-by":"publisher","DOI":"10.1137\/0914041"},{"key":"e_1_3_1_27_2","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPSW.2017.151"},{"key":"e_1_3_1_28_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972818.11"},{"key":"e_1_3_1_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196915"},{"key":"e_1_3_1_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772751"},{"key":"e_1_3_1_31_2","first-page":"31","volume-title":"Proceedings of the 10th USENIX Symposium on Operating Systems Design and Implementation","author":"Kyrola Aapo","year":"2012","unstructured":"Aapo Kyrola, Guy Blelloch, and Carlos Guestrin. 2012. GraphChi: Large-scale graph computation on just a PC. In Proceedings of the 10th USENIX Symposium on Operating Systems Design and Implementation. 31\u201346."},{"key":"e_1_3_1_32_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2021.3098976"},{"key":"e_1_3_1_33_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11432-018-9450-8"},{"key":"e_1_3_1_34_2","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPSW.2014.155"},{"key":"e_1_3_1_35_2","doi-asserted-by":"publisher","DOI":"10.1109\/COMST.2017.2746083"},{"key":"e_1_3_1_36_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2017.2742503"},{"key":"e_1_3_1_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807184"},{"key":"e_1_3_1_38_2","doi-asserted-by":"publisher","DOI":"10.1109\/ISCC.2016.7543874"},{"key":"e_1_3_1_39_2","doi-asserted-by":"publisher","DOI":"10.1145\/3302424.3303974"},{"key":"e_1_3_1_40_2","first-page":"797","volume-title":"Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Meyer Ulrich","year":"2001","unstructured":"Ulrich Meyer. 2001. Single-source shortest-paths on arbitrary directed graphs in linear average-case time. In Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms. 797\u2013806."},{"key":"e_1_3_1_41_2","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522739"},{"key":"e_1_3_1_42_2","doi-asserted-by":"publisher","DOI":"10.1145\/2740908.2742141"},{"key":"e_1_3_1_43_2","volume-title":"The PageRank Citation Ranking: Bringing Order to the Web","author":"Page Lawrence","year":"1998","unstructured":"Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. 1998. The PageRank Citation Ranking: Bringing Order to the Web. Technical Report. Stanford Digital Library Technologies Project."},{"key":"e_1_3_1_44_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICCD.2017.40"},{"key":"e_1_3_1_45_2","doi-asserted-by":"publisher","DOI":"10.1145\/2815400.2815408"},{"key":"e_1_3_1_46_2","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522740"},{"key":"e_1_3_1_47_2","doi-asserted-by":"publisher","DOI":"10.14778\/3007263.3007267"},{"key":"e_1_3_1_48_2","first-page":"317","volume-title":"Proceedings of the 12th USENIX Symposium on Operating Systems Design and Implementation","author":"Shi Jiaxin","year":"2016","unstructured":"Jiaxin Shi, Youyang Yao, Rong Chen, Haibo Chen, and Feifei Li. 2016. Fast and concurrent RDF queries with RDMA-based distributed graph exploration. In Proceedings of the 12th USENIX Symposium on Operating Systems Design and Implementation. 317\u2013332."},{"key":"e_1_3_1_49_2","doi-asserted-by":"publisher","DOI":"10.1145\/3472456.3472457"},{"key":"e_1_3_1_50_2","doi-asserted-by":"publisher","DOI":"10.1137\/0201010"},{"key":"e_1_3_1_51_2","first-page":"429","volume-title":"Proceedings of the 2019 USENIX Annual Technical Conference","author":"Vora Keval","year":"2019","unstructured":"Keval Vora. 2019. LUMOS: Dependency-driven disk-based graph processing. In Proceedings of the 2019 USENIX Annual Technical Conference. 429\u2013442."},{"key":"e_1_3_1_52_2","doi-asserted-by":"publisher","DOI":"10.1145\/3190645"},{"key":"e_1_3_1_53_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2016.2618923"},{"key":"e_1_3_1_54_2","doi-asserted-by":"publisher","DOI":"10.1145\/2600212.2600222"},{"key":"e_1_3_1_55_2","doi-asserted-by":"publisher","DOI":"10.1145\/3341301.3359634"},{"key":"e_1_3_1_56_2","doi-asserted-by":"publisher","DOI":"10.1145\/3173162.3173208"},{"key":"e_1_3_1_57_2","doi-asserted-by":"publisher","DOI":"10.1145\/3132747.3132777"},{"key":"e_1_3_1_58_2","first-page":"441","volume-title":"Proceedings of the 2018 USENIX Annual Technical Conference","author":"Zhang Yu","year":"2018","unstructured":"Yu Zhang, Xiaofei Liao, Hai Jin, Lin Gu, Ligang He, Bingsheng He, and Haikun Liu. 2018. CGraph: A correlations-aware approach for efficient concurrent iterative graph processing. In Proceedings of the 2018 USENIX Annual Technical Conference. 441\u2013452."},{"key":"e_1_3_1_59_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2016.2624289"},{"key":"e_1_3_1_60_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2017.2781241"},{"key":"e_1_3_1_61_2","doi-asserted-by":"publisher","DOI":"10.1145\/3319406"},{"key":"e_1_3_1_62_2","doi-asserted-by":"publisher","DOI":"10.1145\/3295500.3356143"},{"key":"e_1_3_1_63_2","first-page":"301","volume-title":"Proceedings of the 12th USENIX Symposium on Operating Systems Design and Implementation","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 the 12th USENIX Symposium on Operating Systems Design and Implementation. 301\u2013316."},{"key":"e_1_3_1_64_2","first-page":"375","volume-title":"Proceedings of the 2015 USENIX Annual Technical Conference","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 the 2015 USENIX Annual Technical Conference. 375\u2013386."}],"container-title":["ACM Transactions on Architecture and Code Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3600091","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3600091","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:36:50Z","timestamp":1750178210000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3600091"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7,19]]},"references-count":63,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,9,30]]}},"alternative-id":["10.1145\/3600091"],"URL":"https:\/\/doi.org\/10.1145\/3600091","relation":{},"ISSN":["1544-3566","1544-3973"],"issn-type":[{"value":"1544-3566","type":"print"},{"value":"1544-3973","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,7,19]]},"assertion":[{"value":"2022-10-14","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-05-08","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-07-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}