{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,2]],"date-time":"2026-07-02T23:48:49Z","timestamp":1783036129997,"version":"3.54.6"},"reference-count":53,"publisher":"Association for Computing Machinery (ACM)","issue":"2","funder":[{"name":"National Key Research and Development Program of China","award":["2023YFB4503400"],"award-info":[{"award-number":["2023YFB4503400"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Archit. Code Optim."],"published-print":{"date-parts":[[2025,6,30]]},"abstract":"<jats:p>Graph pattern mining is essential for deciphering complex networks. In the real world, graphs are dynamic and evolve over time, necessitating updates in mining patterns to reflect these changes. Traditional methods use fine-grained incremental computation to avoid full re-mining after each update, which improves speed but often overlooks potential gains from examining inter-update interactions holistically, thus missing out on overall efficiency improvements.<\/jats:p>\n          <jats:p>\n            In this article, we introduce Cheetah, a dynamic graph mining system that processes updates in a coarse-grained manner by leveraging\n            <jats:italic toggle=\"yes\">exploration domains<\/jats:italic>\n            . These domains exploit the community structure of real-world graphs to uncover data reuse opportunities typically missed by existing approaches. Exploration domains, which encapsulate extensive portions of the graph relevant to updates, allow multiple updates to explore the same regions efficiently. Cheetah dynamically constructs these domains using a management module that identifies and maintains areas of redundancy as the graph changes. By grouping updates within these domains and employing a neighbor-centric expansion strategy, Cheetah minimizes redundant data accesses. Our evaluation of Cheetah across five real-world datasets shows it outperforms current leading systems by an average factor of 2.63\u00d7.\n          <\/jats:p>","DOI":"10.1145\/3736173","type":"journal-article","created":{"date-parts":[[2025,5,16]],"date-time":"2025-05-16T11:15:21Z","timestamp":1747394121000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Cheetah: Accelerating Dynamic Graph Mining with Grouping Updates"],"prefix":"10.1145","volume":"22","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1845-0160","authenticated-orcid":false,"given":"Yi","family":"Zhang","sequence":"first","affiliation":[{"name":"National Engineering Research Center for Big Data Technology and System, Service Computing Technology and System Lab, Cluster and Grid Computing Lab, School of Computer Science and Technology, Huazhong University of Science and Technology","place":["Wuhan, China"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5792-9994","authenticated-orcid":false,"given":"Xiaomeng","family":"Yi","sequence":"additional","affiliation":[{"name":"Zhejiang Lab","place":["Hangzhou, China"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3927-1102","authenticated-orcid":false,"given":"Yu","family":"Huang","sequence":"additional","affiliation":[{"name":"National Engineering Research Center for Big Data Technology and System, Service Computing Technology and System Lab, Cluster and Grid Computing Lab, School of Software Engineering, Huazhong University of Science and Technology","place":["Wuhan, China"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2712-421X","authenticated-orcid":false,"given":"Jingrui","family":"Yuan","sequence":"additional","affiliation":[{"name":"National Engineering Research Center for Big Data Technology and System, Service Computing Technology and System Lab, Cluster and Grid Computing Lab, School of Computer Science and Technology, Huazhong University of Science and Technology","place":["Wuhan, China"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-8166-4012","authenticated-orcid":false,"given":"Chuangyi","family":"Gui","sequence":"additional","affiliation":[{"name":"Eastern Institute of Technology","place":["Ningbo, China"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4158-5239","authenticated-orcid":false,"given":"Dan","family":"Chen","sequence":"additional","affiliation":[{"name":"National University of Singapore","place":["Singapore, Singapore"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0008-7847-1909","authenticated-orcid":false,"given":"Long","family":"Zheng","sequence":"additional","affiliation":[{"name":"National Engineering Research Center for Big Data Technology and System, Service Computing Technology and System Lab, Cluster and Grid Computing Lab, School of Computer Science and Technology, Huazhong University of Science and Technology","place":["Wuhan, China"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1876-6931","authenticated-orcid":false,"given":"Jianhui","family":"Yue","sequence":"additional","affiliation":[{"name":"Michigan Technological University","place":["Houghton, United States"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6302-813X","authenticated-orcid":false,"given":"Xiaofei","family":"Liao","sequence":"additional","affiliation":[{"name":"National Engineering Research Center for Big Data Technology and System, Service Computing Technology and System Lab, Cluster and Grid Computing Lab, School of Computer Science and Technology, Huazhong University of Science and Technology","place":["Wuhan, China"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3934-7605","authenticated-orcid":false,"given":"Hai","family":"Jin","sequence":"additional","affiliation":[{"name":"National Engineering Research Center for Big Data Technology and System, Service Computing Technology and System Lab, Cluster and Grid Computing Lab, School of Computer Science and Technology, Huazhong University of Science and Technology","place":["Wuhan, China"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0380-3506","authenticated-orcid":false,"given":"Jingling","family":"Xue","sequence":"additional","affiliation":[{"name":"School of Computer Science and Engieering, UNSW Sydney","place":["Kensington, Australia"]}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,7,2]]},"reference":[{"key":"e_1_3_1_2_2","doi-asserted-by":"publisher","DOI":"10.14778\/2536258.2536263"},{"key":"e_1_3_1_3_2","doi-asserted-by":"publisher","DOI":"10.14778\/3229863.3229874"},{"key":"e_1_3_1_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11704-023-2759-8"},{"key":"e_1_3_1_5_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICMLA.2016.0172"},{"key":"e_1_3_1_6_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781316162750.016"},{"key":"e_1_3_1_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/2815400.2815410"},{"key":"e_1_3_1_8_2","first-page":"763","volume-title":"Proceedings of the Symposium on Operating Systems Design and Implementation","author":"Wang Kai","year":"2018","unstructured":"Kai Wang, Zhiqiang Zuo, John Thorpe, Tien Quang Nguyen, and Guoqing Harry Xu. 2018. RStream: Marrying relational algebra with streaming for efficient graph mining on a single machine. In Proceedings of the Symposium on Operating Systems Design and Implementation. 763\u2013782."},{"key":"e_1_3_1_9_2","first-page":"100:1\u2013100:14","volume-title":"Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis","author":"Shi Tianhui","year":"2020","unstructured":"Tianhui Shi, Mingshu Zhai, Yi Xu, and Jidong Zhai. 2020. GraphPi: High performance graph pattern matching through effective redundancy elimination. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis. 100:1\u2013100:14."},{"key":"e_1_3_1_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/3341301.3359633"},{"key":"e_1_3_1_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/3342195.3387548"},{"key":"e_1_3_1_12_2","doi-asserted-by":"publisher","DOI":"10.14778\/3389133.3389137"},{"key":"e_1_3_1_13_2","first-page":"47","volume-title":"Proceedings of the International Conference on Architectural Support for Programming Languages and Operating Systems","author":"Chen Jingji","year":"2023","unstructured":"Jingji Chen and Xuehai Qian. 2023. DecoMine: A compilation-based graph pattern mining system with pattern decomposition. In Proceedings of the International Conference on Architectural Support for Programming Languages and Operating Systems. 47\u201361."},{"key":"e_1_3_1_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/3552326.3567489"},{"key":"e_1_3_1_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/3466752.3480133"},{"key":"e_1_3_1_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/3627703.3629589"},{"key":"e_1_3_1_17_2","doi-asserted-by":"publisher","DOI":"10.1109\/IDCIoT56793.2023.10053454"},{"key":"e_1_3_1_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3035944"},{"key":"e_1_3_1_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465300"},{"key":"e_1_3_1_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196917"},{"key":"e_1_3_1_21_2","first-page":"691","volume-title":"Proceedings of the VLDB Endowment","volume":"11","author":"Ammar Khaled","year":"2018","unstructured":"Khaled Ammar, Frank McSherry, Semih Salihoglu, and Manas Joglekar. 2018. Distributed evaluation of subgraph queries using worst-case optimal and low-memory dataflows. In Proceedings of the VLDB Endowment. Vol. 11, 691\u2013704."},{"key":"e_1_3_1_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/3447786.3456253"},{"key":"e_1_3_1_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/3302424.3303974"},{"key":"e_1_3_1_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/3037697.3037748"},{"key":"e_1_3_1_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/2168836.2168846"},{"key":"e_1_3_1_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2882950"},{"key":"e_1_3_1_27_2","first-page":"269","volume-title":"Proceedings of the USENIX Annual Technical Conference","author":"Vaziri Pourya","year":"2021","unstructured":"Pourya Vaziri and Keval Vora. 2021. Controlling memory footprint of stateful streaming graph processing. In Proceedings of the USENIX Annual Technical Conference. 269\u2013283."},{"key":"e_1_3_1_28_2","unstructured":"Jure Leskovec and Andrej Krevl. 2014. SNAP datasets: Stanford large network dataset collection. Retrieved May 27 2025 from http:\/\/snap.stanford.edu\/data"},{"key":"e_1_3_1_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/3575693.3575743"},{"key":"e_1_3_1_30_2","doi-asserted-by":"publisher","DOI":"10.1109\/ISCA52012.2021.00052"},{"key":"e_1_3_1_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/3431920.3439288"},{"key":"e_1_3_1_32_2","first-page":"45:1\u201345:14","volume-title":"Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis","author":"Chen Dan","year":"2022","unstructured":"Dan Chen, Chuangyi Gui, Yi Zhang, Hai Jin, Long Zheng, Yu Huang, and Xiaofei Liao. 2022. GraphFly: Efficient asynchronous streaming graphs processing via dependency-flow. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis. 45:1\u201345:14."},{"key":"e_1_3_1_33_2","doi-asserted-by":"publisher","DOI":"10.1109\/99.660313"},{"key":"e_1_3_1_34_2","doi-asserted-by":"publisher","DOI":"10.1109\/MICRO50266.2020.00077"},{"key":"e_1_3_1_35_2","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457263"},{"key":"e_1_3_1_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522738"},{"key":"e_1_3_1_37_2","doi-asserted-by":"publisher","DOI":"10.1109\/DAC56929.2023.10247902"},{"key":"e_1_3_1_38_2","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772751"},{"key":"e_1_3_1_39_2","first-page":"318","volume-title":"Proceedings of the International Conference on Parallel Architectures and Compilation Techniques","author":"Gui Chuangyi","year":"2021","unstructured":"Chuangyi Gui, Xiaofei Liao, Long Zheng, Pengcheng Yao, Qinggang Wang, and Hai Jin. 2021. SumPA: Efficient pattern-centric graph mining with pattern abstraction. In Proceedings of the International Conference on Parallel Architectures and Compilation Techniques. 318\u2013330."},{"key":"e_1_3_1_40_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11432-023-3880-y"},{"key":"e_1_3_1_41_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE48307.2020.00064"},{"key":"e_1_3_1_42_2","doi-asserted-by":"publisher","DOI":"10.1002\/widm.1372"},{"key":"e_1_3_1_43_2","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989420"},{"key":"e_1_3_1_44_2","first-page":"157","volume-title":"Proceedings of the International Conference on Extending Database Technology","author":"Choudhury Sutanay","year":"2015","unstructured":"Sutanay Choudhury, Lawrence Holder, George Chin, Khushbu Agarwal, and John Feo. 2015. A selectivity based approach to continuous pattern detection in streaming graphs. In Proceedings of the International Conference on Extending Database Technology. 157\u2013168."},{"key":"e_1_3_1_45_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-015-0416-z"},{"key":"e_1_3_1_46_2","doi-asserted-by":"publisher","DOI":"10.1145\/3267809.3267811"},{"key":"e_1_3_1_47_2","doi-asserted-by":"publisher","DOI":"10.1145\/2992784"},{"key":"e_1_3_1_48_2","doi-asserted-by":"publisher","DOI":"10.1145\/3556976"},{"key":"e_1_3_1_49_2","doi-asserted-by":"publisher","DOI":"10.1145\/3701998"},{"key":"e_1_3_1_50_2","doi-asserted-by":"publisher","DOI":"10.1145\/3652604"},{"key":"e_1_3_1_51_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11704-023-3424-y"},{"key":"e_1_3_1_52_2","doi-asserted-by":"publisher","DOI":"10.1145\/3447786.3456230"},{"key":"e_1_3_1_53_2","doi-asserted-by":"publisher","DOI":"10.1145\/2442516.2442530"},{"key":"e_1_3_1_54_2","doi-asserted-by":"publisher","DOI":"10.1145\/3600091"}],"container-title":["ACM Transactions on Architecture and Code Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3736173","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,2]],"date-time":"2025-07-02T12:20:27Z","timestamp":1751458827000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3736173"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,30]]},"references-count":53,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,6,30]]}},"alternative-id":["10.1145\/3736173"],"URL":"https:\/\/doi.org\/10.1145\/3736173","relation":{},"ISSN":["1544-3566","1544-3973"],"issn-type":[{"value":"1544-3566","type":"print"},{"value":"1544-3973","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,6,30]]},"assertion":[{"value":"2024-09-23","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-04-21","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-07-02","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}