{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,12]],"date-time":"2026-03-12T02:10:37Z","timestamp":1773281437578,"version":"3.50.1"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2026,3,6]],"date-time":"2026-03-06T00:00:00Z","timestamp":1772755200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Indiana University Bloomington were supported by Department of Energy","award":["DE-SC0025228"],"award-info":[{"award-number":["DE-SC0025228"]}]},{"name":"National Science Foundation","award":["OAC-2414474, OAC-2414185, OAC-2313191"],"award-info":[{"award-number":["OAC-2414474, OAC-2414185, OAC-2313191"]}]},{"DOI":"10.13039\/501100001459","name":"Ministry of Education, Singapore","doi-asserted-by":"crossref","award":["Academic Research Fund: Tier 2 Award MOE-T2EP20224-0011 and Tier 1 Award RG20\/24"],"award-info":[{"award-number":["Academic Research Fund: Tier 2 Award MOE-T2EP20224-0011 and Tier 1 Award RG20\/24"]}],"id":[{"id":"10.13039\/501100001459","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2026,6,30]]},"abstract":"<jats:p>Finding frequent subgraph patterns in a big graph is an important problem with many applications such as classifying chemical compounds and building indexes to speed up graph queries. Since this problem is NP-hard, some recent parallel and distributed systems have been developed to accelerate the mining. However, they often have a huge memory cost, very long running time, suboptimal load balancing, poor scale-out capability, and possibly inaccurate results. In this article, we propose an efficient system called T-FSM for parallel mining of frequent subgraph patterns in a big graph. T-FSM supports a new anti-monotonic frequentness measure called Fraction-Score, which is more accurate than the widely used MNI measure. The execution engine of T-FSM supports both intra-machine parallelism and inter-machine parallelism. For intra-machine parallelism, T-FSM adopts a novel task-based execution model to ensure high multithreading concurrency, bounded memory consumption, and effective load balancing. For inter-machine parallelism, T-FSM ensures good scale-out performance with a lightweight pattern rebalancing approach that reduces workload skewness of pattern evaluations among machines. To avoid recomputing the contexts for migrated patterns, we design a novel context cache table to support concurrent and asynchronous requesting and caching of remote context data, which can timely evict and garbage collect used pattern contexts that are no longer needed to keep memory consumption bounded. Extensive experiments show that T-FSM is orders of magnitude faster than existing state-of-the-art parallel systems (more than 10\u00d7, 51\u00d7, 131\u00d7, 55\u00d7 speedup over ScaleMine, DistGraph, Pangolin and Peregrine, respectively) and distributed systems (more than 42\u00d7 and 88\u00d7 over ScaleMine and DistGraph, respectively) for frequent subgraph pattern mining, and it scales out satisfactorily to 512 CPU cores on the Polaris supercomputer at Argonne National Laboratory.<\/jats:p>","DOI":"10.1145\/3771994","type":"journal-article","created":{"date-parts":[[2025,10,16]],"date-time":"2025-10-16T11:07:05Z","timestamp":1760612825000},"page":"1-54","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["T-FSM: A Scalable Distributed Task-Based System for Frequent Subgraph Pattern Mining from a Big Graph"],"prefix":"10.1145","volume":"51","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4374-8161","authenticated-orcid":false,"given":"Lyuheng","family":"Yuan","sequence":"first","affiliation":[{"name":"Computer Science, Indiana University Bloomington","place":["Bloomington, United States"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4653-0408","authenticated-orcid":false,"given":"Da","family":"Yan","sequence":"additional","affiliation":[{"name":"Computer Science, Indiana University Bloomington","place":["Bloomington, United States"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5422-4497","authenticated-orcid":false,"given":"Dingwen","family":"Tao","sequence":"additional","affiliation":[{"name":"Indiana University Bloomington","place":["Bloomington, United States"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0004-4152-182X","authenticated-orcid":false,"given":"Jiao","family":"Han","sequence":"additional","affiliation":[{"name":"Computer Science, Indiana University Bloomington","place":["Bloomington, United States"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7846-2200","authenticated-orcid":false,"given":"Saugat","family":"Adhikari","sequence":"additional","affiliation":[{"name":"Computer Science, Indiana University Bloomington","place":["Bloomington, United States"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6806-8405","authenticated-orcid":false,"given":"Cheng","family":"Long","sequence":"additional","affiliation":[{"name":"College of Computing and Data Science, Nanyang Technological University","place":["Singapore, Singapore"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7839-4933","authenticated-orcid":false,"given":"Yang","family":"Zhou","sequence":"additional","affiliation":[{"name":"Computer Science and Software Engineering, Auburn University","place":["Auburn, United States"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2026,3,6]]},"reference":[{"key":"e_1_3_4_2_2","doi-asserted-by":"publisher","DOI":"10.1109\/SC.2016.60"},{"key":"e_1_3_4_3_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2001.959892"},{"key":"e_1_3_4_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-68125-0_84"},{"key":"e_1_3_4_5_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00136"},{"key":"e_1_3_4_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/3190508.3190545"},{"key":"e_1_3_4_7_2","doi-asserted-by":"publisher","DOI":"10.14778\/3389133.3389137"},{"key":"e_1_3_4_8_2","doi-asserted-by":"publisher","DOI":"10.1109\/TITB.2009.2028234"},{"key":"e_1_3_4_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/2324796.2324831"},{"key":"e_1_3_4_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/800157.805047"},{"key":"e_1_3_4_11_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2005.127"},{"key":"e_1_3_4_12_2","volume-title":"SC","author":"Dinan James","year":"2009","unstructured":"James Dinan, D. Brian Larkins, P. Sadayappan, Sriram Krishnamoorthy, and Jarek Nieplocha. 2009. Scalable work stealing. In SC. ACM."},{"key":"e_1_3_4_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319875"},{"key":"e_1_3_4_14_2","doi-asserted-by":"publisher","DOI":"10.14778\/2732286.2732289"},{"key":"e_1_3_4_15_1","unstructured":"Argonne Leadership Computing Facility. [n. d.]. Polaris machine overview. Retrieved April 16 2024 from https:\/\/docs.alcf.anl.gov\/polaris\/"},{"key":"e_1_3_4_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319880"},{"key":"e_1_3_4_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376660"},{"key":"e_1_3_4_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/3342195.3387548"},{"key":"e_1_3_4_19_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-005-0003-9"},{"key":"e_1_3_4_20_2","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342643"},{"key":"e_1_3_4_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/277651.277687"},{"key":"e_1_3_4_22_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.entcs.2004.12.039"},{"key":"e_1_3_4_23_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-15939-8_14"},{"key":"e_1_3_4_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3380581"},{"key":"e_1_3_4_25_2","doi-asserted-by":"publisher","DOI":"10.14778\/3425879.3425888"},{"key":"e_1_3_4_26_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-016-0466-x"},{"key":"e_1_3_4_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/2815400.2815410"},{"key":"e_1_3_4_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/321921.321925"},{"key":"e_1_3_4_29_2","first-page":"763","volume-title":"OSDI","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 OSDI. USENIX Association, 763\u2013782."},{"key":"e_1_3_4_30_2","first-page":"69:1\u201369:14","volume-title":"SC","author":"Xiang Lizhi","year":"2021","unstructured":"Lizhi Xiang, Arif Khan, Edoardo Serra, Mahantesh Halappanavar, and Aravind Sukumaran-Rajam. 2021. cuTS: Scaling subgraph isomorphism on distributed multi-GPU systems using trie based data structure. In SC. ACM, 69:1\u201369:14."},{"key":"e_1_3_4_31_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE48307.2020.00122"},{"key":"e_1_3_4_32_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE48307.2020.00208"},{"key":"e_1_3_4_33_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-021-00687-0"},{"key":"e_1_3_4_34_2","first-page":"721","volume-title":"ICDM","author":"Yan Xifeng","year":"2002","unstructured":"Xifeng Yan and Jiawei Han. 2002. gSpan: Graph-based substructure pattern mining. In ICDM. 721\u2013724."},{"key":"e_1_3_4_35_2","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007607"},{"key":"e_1_3_4_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/3588928"},{"key":"e_1_3_4_37_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-0716-1534-8_8"},{"key":"e_1_3_4_38_2","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687734"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3771994","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3771994","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T11:17:52Z","timestamp":1773227872000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3771994"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,3,6]]},"references-count":37,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,6,30]]}},"alternative-id":["10.1145\/3771994"],"URL":"https:\/\/doi.org\/10.1145\/3771994","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,3,6]]},"assertion":[{"value":"2024-04-16","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-10-06","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-03-06","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}