{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,26]],"date-time":"2026-06-26T13:47:15Z","timestamp":1782481635134,"version":"3.54.5"},"reference-count":62,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2026,6,26]],"date-time":"2026-06-26T00:00:00Z","timestamp":1782432000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["62372455"],"award-info":[{"award-number":["62372455"]}],"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. Archit. Code Optim."],"published-print":{"date-parts":[[2026,6,30]]},"abstract":"<jats:p>Current Approximate Graph Pattern Mining (AGPM) systems rely on uniform and static sampler allocation strategies, which result in significant computational redundancy because most regions of the sampling space contribute little to the final estimate. However, existing systems overlook this critical characteristic and fail to account for the hierarchical memory architecture of modern servers, leading to slow convergence and substantial memory access overhead.<\/jats:p>\n                  <jats:p>To address these challenges, we propose HierMine, a novel AGPM system designed to overcome the aforementioned drawbacks. The core contributions of HierMine include: (i) a hierarchical sampling strategy that minimizes redundant computation and accelerates convergence; (ii) a dynamic sampling adjustment mechanism that partitions the sampling space online and reallocates samplers adaptively to enhance the hierarchical strategy; (iii) an online grouping-based convergence detection technique that enables the fine-grained dynamic sampling adjustment mechanism; and (iv) a hierarchical data layout optimized for memory access efficiency.<\/jats:p>\n                  <jats:p>Extensive experiments show that HierMine delivers an average speedup of up to 28.9\u00d7 over state-of-the-art AGPM systems such as ScaleGPM, while maintaining strong theoretical guarantees on estimation quality. It also consistently outperforms exact graph pattern mining systems, highlighting the practical benefits of our approximate approach.<\/jats:p>","DOI":"10.1145\/3814962","type":"journal-article","created":{"date-parts":[[2026,5,4]],"date-time":"2026-05-04T11:22:51Z","timestamp":1777893771000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["HierMine: Accelerating Graph Pattern Mining via Hierarchical Sampling"],"prefix":"10.1145","volume":"23","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8911-966X","authenticated-orcid":false,"given":"Guang","family":"Wu","sequence":"first","affiliation":[{"name":"National University of Defense Technology","place":["Changsha, China"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3622-1772","authenticated-orcid":false,"given":"Xinbiao","family":"Gan","sequence":"additional","affiliation":[{"name":"National University of Defense Technology","place":["Changsha, China"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4926-5953","authenticated-orcid":false,"given":"Songzhu","family":"Mei","sequence":"additional","affiliation":[{"name":"National University of Defense Technology","place":["Changsha, China"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2046-5043","authenticated-orcid":false,"given":"Zhengbin","family":"Pang","sequence":"additional","affiliation":[{"name":"National University of Defense Technology","place":["Changsha, China"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-6131-554X","authenticated-orcid":false,"given":"Hongxu","family":"Jin","sequence":"additional","affiliation":[{"name":"Zunyi Normal College","place":["Zunyi, China"]}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,6,26]]},"reference":[{"key":"e_1_3_2_2_2","volume-title":"Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis.","author":"Abdelhamid Ehab","year":"2016","unstructured":"Ehab Abdelhamid, Ibrahim Abdelaziz, Panos Kalnis, Zuhair Khayyat, and Fuad Jamour. 2016. Scalemine: Scalable parallel frequent subgraph mining in a single large graph. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis.IEEE, Piscataway, NJ, USA, Article 61, 12 pages. Retrieved from http:\/\/dl.acm.org\/citation.cfm?id=3014904.3014986"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btn163"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.14778\/3705829.3705831"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2019.6"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1126\/science.aad9029"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/3394486.3403073"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2012.87"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/1963405.1963488"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/3186586"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342640"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/3710848.3710889"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/3575693.3575743"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055502"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319875"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.14778\/2732286.2732289"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/3689341"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/3750450"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/3676846"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/3627535.3638498"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2021.3100785"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/3200691.3178506"},{"key":"e_1_3_2_23_2","article-title":"The NBER Patent Citation Data File: Lessons, Insights and Methodological Tools","author":"Hall B. H.","year":"2001","unstructured":"B. H. Hall, Jaffe A. B., and Trajtenberg M.2001. The NBER Patent Citation Data File: Lessons, Insights and Methodological Tools. Retrieved May 2025 from http:\/\/www.nber.org\/patents\/","journal-title":"Retrieved May 2025 from"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/3774934.3786416"},{"key":"e_1_3_2_25_2","first-page":"745","volume-title":"Proceedings of the 12th USENIX Conference on Operating Systems Design and Implementation.","author":"Iyer Anand Padmanabha","year":"2018","unstructured":"Anand Padmanabha Iyer, Zaoxing Liu, Xin Jin, Shivaram Venkataraman, Vladimir Braverman, and Ion Stoica. 2018. ASAP: Fast, approximate graph pattern mining at scale. In Proceedings of the 12th USENIX Conference on Operating Systems Design and Implementation.USENIX Association, Berkeley, CA, USA, 745\u2013761. Retrieved from http:\/\/dl.acm.org\/citation.cfm?id=3291168.3291224"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/3342195.3387548"},{"key":"e_1_3_2_27_2","volume-title":"Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis.","author":"Jia Menghan","year":"2022","unstructured":"Menghan Jia, Yiming Zhang, Xinbiao Gan, Dongsheng Li, Erci Xu, Ruibo Wang, and Kai Lu. 2022. vGraph: Memory-efficient multicore graph processing for traversal-centric algorithms. In Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis.IEEE, Dallas, Texas, Article 63, 14 pages."},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/3559009.3569658"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2004.10024"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.14778\/3773749.3773761"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/1081870.1081893"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2015.7113337"},{"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":"publisher","DOI":"10.1145\/3469379.3469383"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1145\/3341301.3359633"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1109\/CCGRID.2018.00080"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1126\/science.298.5594.824"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.2307\/2342192"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.14778\/2556549.2556569"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1145\/3447548.3467344"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/bth436"},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1109\/BigData.2017.8258022"},{"key":"e_1_3_2_43_2","volume-title":"Introduction to Probability Models (11th ed.)","author":"Ross Sheldon M.","year":"2014","unstructured":"Sheldon M. Ross. 2014. Introduction to Probability Models (11th ed.). Academic Press, USA."},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1109\/TNNLS.2018.2826529"},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3220097"},{"key":"e_1_3_2_46_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976830.13"},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","DOI":"10.1145\/3556541"},{"key":"e_1_3_2_48_2","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.IEEE Press, Atlanta, Georgia, Article 100, 14 pages."},{"key":"e_1_3_2_49_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-59003-1_4"},{"key":"e_1_3_2_50_2","first-page":"1","volume-title":"Proceedings of the International Scientific Conference and International Workshop: Present Day Trends of Innovations 2012","author":"Takac Lubos","year":"2012","unstructured":"Lubos Takac and Michal Zabovsky. 2012. Data analysis in public social networks. In Proceedings of the International Scientific Conference and International Workshop: Present Day Trends of Innovations 2012. snap, \u0141om\u017ca, Poland, 1\u20136."},{"key":"e_1_3_2_51_2","doi-asserted-by":"publisher","DOI":"10.1145\/2815400.2815410"},{"key":"e_1_3_2_52_2","doi-asserted-by":"publisher","DOI":"10.1007\/s13278-010-0001-9"},{"key":"e_1_3_2_53_2","doi-asserted-by":"publisher","DOI":"10.1145\/1557019.1557111"},{"key":"e_1_3_2_54_2","doi-asserted-by":"publisher","DOI":"10.1145\/3308558.3313534"},{"key":"e_1_3_2_55_2","volume-title":"Proceedings of the 16th USENIX Symposium on Operating Systems Design and Implementation","author":"Chen Xuhao","year":"2022","unstructured":"Xuhao Chen and Arvind. 2022 [pdf]. Efficient and scalable graph pattern mining on GPUs. In Proceedings of the 16th USENIX Symposium on Operating Systems Design and Implementation. USENIX, Carlsbad, CA, USA."},{"key":"e_1_3_2_56_2","first-page":"763","volume-title":"Proceedings of the 12th USENIX Conference 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 12th USENIX Conference on Operating Systems Design and Implementation.USENIX Association, Berkeley, CA, USA, 763\u2013782. Retrieved from http:\/\/dl.acm.org\/citation.cfm?id=3291168.3291225"},{"key":"e_1_3_2_57_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-013-0693-z"},{"key":"e_1_3_2_58_2","doi-asserted-by":"publisher","DOI":"10.1145\/2350190.2350193"},{"key":"e_1_3_2_59_2","doi-asserted-by":"publisher","DOI":"10.1145\/3485447.3512167"},{"key":"e_1_3_2_60_2","doi-asserted-by":"publisher","DOI":"10.1145\/2688500.2688507"},{"key":"e_1_3_2_61_2","doi-asserted-by":"publisher","DOI":"10.1145\/3276491"},{"key":"e_1_3_2_62_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICPP.2010.67"},{"key":"e_1_3_2_63_2","volume-title":"Proceedings of the 20th USENIX Symposium on Networked Systems Design and Implementation.","author":"Zhu Zeying","year":"2023","unstructured":"Zeying Zhu, Kan Wu, and Zaoxing Liu. 2023. Arya: Arbitrary graph pattern mining with decomposition-based sampling. In Proceedings of the 20th USENIX Symposium on Networked Systems Design and Implementation.USENIX, Boston, MA, USA."}],"container-title":["ACM Transactions on Architecture and Code Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3814962","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,26]],"date-time":"2026-06-26T12:56:22Z","timestamp":1782478582000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3814962"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,26]]},"references-count":62,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,6,30]]}},"alternative-id":["10.1145\/3814962"],"URL":"https:\/\/doi.org\/10.1145\/3814962","relation":{},"ISSN":["1544-3566","1544-3973"],"issn-type":[{"value":"1544-3566","type":"print"},{"value":"1544-3973","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,6,26]]},"assertion":[{"value":"2025-11-19","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-04-24","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-06-26","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}