{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T05:02:32Z","timestamp":1750309352248,"version":"3.41.0"},"reference-count":62,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2024,11,20]],"date-time":"2024-11-20T00:00:00Z","timestamp":1732060800000},"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":["2023YFF1204101"],"award-info":[{"award-number":["2023YFF1204101"]}]},{"name":"Huawei Technologies Co., Ltd","award":["YBN2021035018A5"],"award-info":[{"award-number":["YBN2021035018A5"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Archit. Code Optim."],"published-print":{"date-parts":[[2024,12,31]]},"abstract":"<jats:p>\n            There are usually a large number of\n            <jats:italic>concurrent graph queries<\/jats:italic>\n            (CGQs) requirements in streaming graphs. However, existing graph processing systems mainly optimize a single graph query in streaming graphs or CGQs in static graphs. They have a large number of redundant computations and expensive memory access overhead, and cannot process CGQs in streaming graphs efficiently. To address these issues, we propose\n            <jats:italic>PMGraph<\/jats:italic>\n            , a software-hardware collaborative accelerator for efficient processing of CGQs in streaming graphs. First, PMGraph centers on fine-grained data, selects graph queries that meet the requirements through vertex data, and utilizes the similarity between different graph queries to merge the same vertices they need to process to address the problem of a large amount of repeated access to the same data by different graph queries in CGQs, thereby reducing memory access overhead. Furthermore, it adopts the update strategy that regularizes the processing order of vertices in each graph query according to the order of the vertex dependence chain, consequently effectively reducing redundant computations. Second, we propose a CGQs-oriented scheduling strategy to increase the data overlap when different graph queries are processed, thereby further improving the performance. Finally, PMGraph prefetches the vertex information according to the global active vertex set Frontier of all graph queries, hiding the memory access latency. It also provides prefetching for the same vertices that need to be processed by different graph queries, reducing the memory access overhead. Compared with the state-of-the-art concurrent graph query software systems Kickstarter-C and Tripoline, PMGraph achieves average speedups of 5.57\u00d7 and 4.58\u00d7, respectively. Compared with the state-of-the-art hardware accelerators Minnow, HATS, LCCG, and JetStream, PMGraph achieves the speedup of 3.65\u00d7, 3.41\u00d7, 1.73\u00d7, and 1.38\u00d7 on average, respectively. Experimental results show that our proposed PMGraph outperforms the state-of-the-art concurrent graph processing systems and hardware accelerators.\n          <\/jats:p>","DOI":"10.1145\/3689337","type":"journal-article","created":{"date-parts":[[2024,8,20]],"date-time":"2024-08-20T11:25:15Z","timestamp":1724153115000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["PMGraph: Accelerating Concurrent Graph Queries over Streaming Graphs"],"prefix":"10.1145","volume":"21","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2589-0073","authenticated-orcid":false,"given":"Fubing","family":"Mao","sequence":"first","affiliation":[{"name":"Huazhong University of Science and Technology, Wuhan, China"}]},{"ORCID":"https:\/\/orcid.org\/0009-0006-2866-6893","authenticated-orcid":false,"given":"Xu","family":"Liu","sequence":"additional","affiliation":[{"name":"Huazhong University of Science and Technology, Wuhan, China"}]},{"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, Wuhan, China"}]},{"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, Wuhan, China"}]},{"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, Wuhan, China"}]},{"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, Wuhan, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7622-6714","authenticated-orcid":false,"given":"Wei","family":"Zhang","sequence":"additional","affiliation":[{"name":"Department of Electronic and Computer Engineering, Hong Kong University of Science and Technology, Hong Kong, Hong Kong"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-9015-5485","authenticated-orcid":false,"given":"Jian","family":"Zhou","sequence":"additional","affiliation":[{"name":"Huazhong University of Science and Technology, Wuhan, China"}]},{"ORCID":"https:\/\/orcid.org\/0009-0006-4432-8640","authenticated-orcid":false,"given":"Yufei","family":"Wu","sequence":"additional","affiliation":[{"name":"Huazhong University of Science and Technology, Wuhan, China"}]},{"ORCID":"https:\/\/orcid.org\/0009-0005-5303-2078","authenticated-orcid":false,"given":"Longyu","family":"Nie","sequence":"additional","affiliation":[{"name":"Huazhong University of Science and Technology, Wuhan, China"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-6932-0561","authenticated-orcid":false,"given":"Yapu","family":"Guo","sequence":"additional","affiliation":[{"name":"Huazhong University of Science and Technology, Wuhan, China"}]},{"ORCID":"https:\/\/orcid.org\/0009-0005-2347-0472","authenticated-orcid":false,"given":"Zihan","family":"Jiang","sequence":"additional","affiliation":[{"name":"Huazhong University of Science and Technology, Wuhan, China"}]},{"ORCID":"https:\/\/orcid.org\/0009-0001-1076-0009","authenticated-orcid":false,"given":"Jingkang","family":"Liu","sequence":"additional","affiliation":[{"name":"Huazhong University of Science and Technology, Wuhan, China"}]}],"member":"320","published-online":{"date-parts":[[2024,11,20]]},"reference":[{"key":"e_1_3_1_2_2","unstructured":"Salman Aslam. 2023. Twitter by the Numbers: Stats Demographics and Fun Facts. Retrieved July 28th 2023 from https:\/\/www.omnicoreagency.com\/twitter-statistics\/"},{"key":"e_1_3_1_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/1150402.1150412"},{"key":"e_1_3_1_4_2","doi-asserted-by":"publisher","DOI":"10.1109\/HPCA51647.2021.00062"},{"key":"e_1_3_1_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/3466752.3480096"},{"key":"e_1_3_1_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/988672.988752"},{"key":"e_1_3_1_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/2063384.2063454"},{"key":"e_1_3_1_8_2","doi-asserted-by":"publisher","DOI":"10.1109\/ISCA45697.2020.00044"},{"key":"e_1_3_1_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/3458817.3476159"},{"key":"e_1_3_1_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11704-023-3401-5"},{"key":"e_1_3_1_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/2168836.2168846"},{"key":"e_1_3_1_12_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11704-023-2675-y"},{"key":"e_1_3_1_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/2847263.2847339"},{"key":"e_1_3_1_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/3178876.3186183"},{"key":"e_1_3_1_15_2","doi-asserted-by":"publisher","DOI":"10.1109\/HPCA47549.2020.00028"},{"key":"e_1_3_1_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3452796"},{"key":"e_1_3_1_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457263"},{"key":"e_1_3_1_18_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11704-023-2656-1"},{"key":"e_1_3_1_19_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11704-022-2327-7"},{"key":"e_1_3_1_20_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2017.2763951"},{"key":"e_1_3_1_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/3469379.3469382"},{"key":"e_1_3_1_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/3447786.3456226"},{"key":"e_1_3_1_23_2","doi-asserted-by":"publisher","DOI":"10.1109\/DAC56929.2023.10247904"},{"key":"e_1_3_1_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/2429384.2429446"},{"key":"e_1_3_1_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/1081870.1081893"},{"key":"e_1_3_1_26_2","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2009.10129177"},{"issue":"2","key":"e_1_3_1_27_2","first-page":"1","article-title":"ReCSA: A dedicated sort accelerator using ReRAM-based content addressable memory","volume":"17","author":"Li Huize","year":"2022","unstructured":"Huize Li, Hai Jin, Long Zheng, Yu Huang, and Xiaofei Liao. 2022. ReCSA: A dedicated sort accelerator using ReRAM-based content addressable memory. Frontiers of Computer Science 17, 2 (2022), 1\u201313.","journal-title":"Frontiers of Computer Science"},{"key":"e_1_3_1_28_2","doi-asserted-by":"publisher","DOI":"10.14778\/3415478.3415482"},{"key":"e_1_3_1_29_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11704-023-3307-2"},{"key":"e_1_3_1_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457253"},{"key":"e_1_3_1_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/3447786.3456230"},{"key":"e_1_3_1_32_2","doi-asserted-by":"publisher","DOI":"10.1145\/3302424.3303974"},{"key":"e_1_3_1_33_2","first-page":"797","volume-title":"Proceedings of the 12th 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 ACM-SIAM Symposium on Discrete Algorithms. 797\u2013806."},{"key":"e_1_3_1_34_2","doi-asserted-by":"publisher","DOI":"10.1109\/MICRO.2018.00010"},{"key":"e_1_3_1_35_2","doi-asserted-by":"publisher","DOI":"10.1109\/HPCA.2017.54"},{"key":"e_1_3_1_36_2","first-page":"1","volume-title":"Proceedings of the 1999 International Conference on the Web Conference","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. In Proceedings of the 1999 International Conference on the Web Conference. 1\u201317."},{"key":"e_1_3_1_37_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICCD.2017.40"},{"key":"e_1_3_1_38_2","doi-asserted-by":"publisher","DOI":"10.1109\/MICRO50266.2020.00078"},{"key":"e_1_3_1_39_2","doi-asserted-by":"publisher","DOI":"10.1145\/3466752.3480126"},{"key":"e_1_3_1_40_2","doi-asserted-by":"publisher","DOI":"10.14778\/3007263.3007267"},{"issue":"5","key":"e_1_3_1_41_2","first-page":"1","article-title":"ARCHER: A ReRAM-based accelerator for compressed recommendation systems","volume":"18","author":"Shen Xinyang","year":"2023","unstructured":"Xinyang Shen, Xiaofei Liao, Long Zheng, Yu Huang, Dan Chen, and Hai Jin. 2023. ARCHER: A ReRAM-based accelerator for compressed recommendation systems. Frontiers of Computer Science 18, 5 (2023), 1\u201314.","journal-title":"Frontiers of Computer Science"},{"key":"e_1_3_1_42_2","doi-asserted-by":"publisher","DOI":"10.1145\/3267809.3267811"},{"key":"e_1_3_1_43_2","doi-asserted-by":"publisher","DOI":"10.1145\/2442516.2442530"},{"key":"e_1_3_1_44_2","doi-asserted-by":"publisher","DOI":"10.1109\/HPCA.2018.00052"},{"issue":"1","key":"e_1_3_1_45_2","first-page":"1","article-title":"UCat: Heterogeneous memory management for unikernels","volume":"17","author":"Tian Chong","year":"2022","unstructured":"Chong Tian, Haikun Liu, Xiaofei Liao, and Hai Jin. 2022. UCat: Heterogeneous memory management for unikernels. Frontiers of Computer Science 17, 1 (2022), 1\u201311.","journal-title":"Frontiers of Computer Science"},{"key":"e_1_3_1_46_2","doi-asserted-by":"publisher","DOI":"10.1145\/3037697.3037748"},{"key":"e_1_3_1_47_2","doi-asserted-by":"publisher","DOI":"10.1109\/HiPC50609.2020.00014"},{"key":"e_1_3_1_48_2","doi-asserted-by":"publisher","DOI":"10.14778\/2733085.2733103"},{"key":"e_1_3_1_49_2","doi-asserted-by":"publisher","DOI":"10.1145\/3352460.3358318"},{"key":"e_1_3_1_50_2","doi-asserted-by":"publisher","DOI":"10.1145\/3097983.3098069"},{"key":"e_1_3_1_51_2","doi-asserted-by":"publisher","DOI":"10.1145\/3567955.3567963"},{"key":"e_1_3_1_52_2","doi-asserted-by":"publisher","DOI":"10.1145\/3173162.3173197"},{"issue":"6","key":"e_1_3_1_53_2","first-page":"5823","article-title":"EGraph: Efficient concurrent GPU-based dynamic graph processing","volume":"35","author":"Zhang Yu","year":"2022","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. 2022. EGraph: Efficient concurrent GPU-based dynamic graph processing. IEEE Transactions on Knowledge and Data Engineering 35, 6 (2022), 5823\u20135836.","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"key":"e_1_3_1_54_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2016.2624289"},{"key":"e_1_3_1_55_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2017.2781241"},{"key":"e_1_3_1_56_2","doi-asserted-by":"publisher","DOI":"10.1145\/3297858.3304029"},{"key":"e_1_3_1_57_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2017.2776115"},{"key":"e_1_3_1_58_2","doi-asserted-by":"publisher","DOI":"10.1145\/3319406"},{"key":"e_1_3_1_59_2","doi-asserted-by":"publisher","DOI":"10.1145\/3470496.3527409"},{"key":"e_1_3_1_60_2","doi-asserted-by":"publisher","DOI":"10.1145\/3458817.3480854"},{"key":"e_1_3_1_61_2","doi-asserted-by":"publisher","DOI":"10.1145\/3295500.3356143"},{"key":"e_1_3_1_62_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11432-022-3846-1"},{"key":"e_1_3_1_63_2","doi-asserted-by":"publisher","DOI":"10.1145\/3352460.3358256"}],"container-title":["ACM Transactions on Architecture and Code Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3689337","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3689337","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:05:45Z","timestamp":1750291545000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3689337"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,11,20]]},"references-count":62,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,12,31]]}},"alternative-id":["10.1145\/3689337"],"URL":"https:\/\/doi.org\/10.1145\/3689337","relation":{},"ISSN":["1544-3566","1544-3973"],"issn-type":[{"type":"print","value":"1544-3566"},{"type":"electronic","value":"1544-3973"}],"subject":[],"published":{"date-parts":[[2024,11,20]]},"assertion":[{"value":"2024-02-02","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-08-05","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-11-20","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}