{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T18:07:26Z","timestamp":1757614046451,"version":"3.44.0"},"reference-count":61,"publisher":"Association for Computing Machinery (ACM)","issue":"11","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2025,7]]},"abstract":"<jats:p>\n            We study the subgraph matching problem, which is to find all subgraph isomorphisms of a given pattern graph\n            <jats:italic toggle=\"yes\">p<\/jats:italic>\n            in a data graph\n            <jats:italic toggle=\"yes\">G.<\/jats:italic>\n            Traditional approaches typically use a backtracking search approach or worst-case optimal join, both of which directly operate on\n            <jats:italic toggle=\"yes\">p.<\/jats:italic>\n            In this paper, we revisit the tree decomposition based approach. For a complex pattern graph\n            <jats:italic toggle=\"yes\">p<\/jats:italic>\n            , we find its optimal tree decomposition\n            <jats:italic toggle=\"yes\">T<\/jats:italic>\n            based on the fractional hypertree width, where a node in\n            <jats:italic toggle=\"yes\">T<\/jats:italic>\n            represents a subgraph of\n            <jats:italic toggle=\"yes\">p<\/jats:italic>\n            , which is also called a bag, and a node in\n            <jats:italic toggle=\"yes\">p<\/jats:italic>\n            may appear in multiple bags in\n            <jats:italic toggle=\"yes\">T.<\/jats:italic>\n            The tree decomposition based approach initially computes and materializes the matches of subgraphs specified by the bags, then treats these matches as new relations and employs an acyclic join to compute the matches of\n            <jats:italic toggle=\"yes\">p<\/jats:italic>\n            itself. However, previous approaches fail to integrate the tree decomposition with effective join attribute orders, and conversely, previous join attribute ordering approaches do not consider the need to share computations in multiple bags. Additionally, the materialization strategies in previous tree decomposition based approaches can lead to high computation costs. In this paper, we propose a new subgraph matching algorithm ASDMatch (Adaptive Shared Decomposition-based matching). We propose a new dynamic programming approach that finds optimal attribute orders for each bag based on a cost model that incorporates the computation sharing. Furthermore, we introduce a new adaptive materialization strategy to reduce the computation cost. We confirmed that our ASDMatch outperforms state-of-the-art algorithms and can process many challenging queries that previous algorithms can not finish within the time limit.\n          <\/jats:p>","DOI":"10.14778\/3749646.3749693","type":"journal-article","created":{"date-parts":[[2025,9,4]],"date-time":"2025-09-04T17:55:06Z","timestamp":1757008506000},"page":"4282-4294","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Subgraph Matching: A New Decomposition Based Approach"],"prefix":"10.14778","volume":"18","author":[{"given":"Qiyan","family":"Li","sequence":"first","affiliation":[{"name":"The Chinese Univ. of Hong Kong, Hong Kong, China"}]},{"given":"Jeffrey Xu","family":"Yu","sequence":"additional","affiliation":[{"name":"The Chinese Univ. of Hong Kong, Hong Kong, China"}]},{"given":"Zongyan","family":"He","sequence":"additional","affiliation":[{"name":"The Chinese Univ. of Hong Kong, Hong Kong, China"}]}],"member":"320","published-online":{"date-parts":[[2025,9,4]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"The online repository and appendix of the paper. https:\/\/github.com\/magic62442\/ASDMatch."},{"key":"e_1_2_1_2_1","first-page":"446","volume-title":"SIGMOD","author":"Aberger C. R.","unstructured":"C. R. Aberger, S. Tu, K. Olukotun, and C. R\u00e9. Emptyheaded: A relational engine for graph processing. In SIGMOD, pages 431\u2013446. ACM, 2016."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3589312"},{"key":"e_1_2_1_4_1","first-page":"1462","volume-title":"SIGMOD","author":"Bhattarai B.","unstructured":"B. Bhattarai, H. Liu, and H. H. Huang. CECI: compact embedding cluster index for scalable subgraph matching. In SIGMOD, pages 1447\u20131462. ACM, 2019."},{"key":"e_1_2_1_5_1","first-page":"1214","volume-title":"SIGMOD","author":"Bi F.","unstructured":"F. Bi, L. Chang, X. Lin, L. Qin, and W. Zhang. Efficient subgraph matching by postponing cartesian products. In SIGMOD, pages 1199\u20131214. ACM, 2016."},{"key":"e_1_2_1_6_1","volume-title":"A subgraph isomorphism algorithm and its application to biochemical data. BMC Bioinform., 14(S-7):S13","author":"Bonnici V.","year":"2013","unstructured":"V. Bonnici, R. Giugno, A. Pulvirenti, D. E. Shasha, and A. Ferro. A subgraph isomorphism algorithm and its application to biochemical data. BMC Bioinform., 14(S-7):S13, 2013."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3654964"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.14778\/3389133.3389137"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.14778\/3598581.3598591"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2004.75"},{"key":"e_1_2_1_11_1","volume-title":"Hyperbench: A benchmark and tool for hypergraphs and empirical findings","author":"Fischl W.","year":"2020","unstructured":"W. Fischl, G. Gottlob, D. M. Longo, and R. Pichler. Hyperbench: A benchmark and tool for hypergraphs and empirical findings, 2020."},{"key":"e_1_2_1_12_1","series-title":"An EATCS Series","volume-title":"Parameterized Complexity Theory. Texts in Theoretical Computer Science","author":"Flum J.","year":"2006","unstructured":"J. Flum and M. Grohe. Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer, 2006."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407797"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902309"},{"key":"e_1_2_1_15_1","first-page":"1162","volume-title":"Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI","author":"Gottlob G.","year":"2020","unstructured":"G. Gottlob, C. Okulmus, and R. Pichler. Fast and parallel decomposition of constraint satisfaction problems. In C. Bessiere, editor, Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI 2020, pages 1155\u20131162. ijcai.org, 2020."},{"key":"e_1_2_1_16_1","volume-title":"Constraint solving via fractional edge covers. ACM Trans. Algorithms, 11(1), aug","author":"Grohe M.","year":"2014","unstructured":"M. Grohe and D. Marx. Constraint solving via fractional edge covers. ACM Trans. Algorithms, 11(1), aug 2014."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2020.3035564"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319880"},{"key":"e_1_2_1_19_1","first-page":"348","volume-title":"SIGMOD","author":"Han W.-S.","year":"2013","unstructured":"W.-S. Han, J. Lee, and J.-H. Lee. Turboiso: Towards Ultrafast and Robust Subgraph Isomorphism Search in Large Graph Databases. In SIGMOD, pages 337\u2013348, 2013."},{"key":"e_1_2_1_20_1","first-page":"418","volume-title":"SIGMOD","author":"He H.","unstructured":"H. He and A. K. Singh. Graphs-at-a-time: query language and access methods for graph databases. In SIGMOD, pages 405\u2013418. ACM, 2008."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.14778\/3704965.3704973"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/3587136.3587144"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE60146.2024.00321"},{"key":"e_1_2_1_24_1","first-page":"233","volume-title":"2012 IEEE 28th International Conference on Data Engineering","author":"Jin C.","unstructured":"C. Jin, S. S. Bhowmick, B. Choi, and S. Zhou. Prague: towards blending practical visual subgraph query formulation and query processing. In 2012 IEEE 28th International Conference on Data Engineering, pages 222\u2013233. IEEE, 2012."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588692"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE51399.2021.00129"},{"key":"e_1_2_1_27_1","first-page":"293","volume-title":"Proceedings of the 20th International Conference on Extending Database Technology, EDBT 2017","author":"Kalinsky O.","year":"2017","unstructured":"O. Kalinsky, Y. Etsion, and B. Kimelfeld. Flexible caching in trie joins. In V. Markl, S. Orlando, B. Mitschang, P. Andritsos, K. Sattler, and S. Bre\u00df, editors, Proceedings of the 20th International Conference on Extending Database Technology, EDBT 2017, Venice, Italy, March 21\u201324, 2017, pages 282\u2013293. OpenProceedings.org, 2017."},{"key":"e_1_2_1_28_1","first-page":"937","volume-title":"SIGMOD","author":"Kim H.","unstructured":"H. Kim, Y. Choi, K. Park, X. Lin, S. Hong, and W. Han. Versatile equivalences: Speeding up subgraph query processing and subgraph matching. In SIGMOD, pages 925\u2013937. ACM, 2021."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-022-00749-x"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-017-0459-4"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.14778\/3021924.3021937"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.14778\/3704965.3704967"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.14778\/3659437.3659451"},{"key":"e_1_2_1_34_1","volume-title":"Proc. ACM Manag. Data, 3(1)","author":"Lu Y.","year":"2025","unstructured":"Y. Lu, Z. Zhang, and W. Zheng. BX: Subgraph matching with batch backtracking search. Proc. ACM Manag. Data, 3(1), Feb. 2025."},{"key":"e_1_2_1_35_1","first-page":"553","volume-title":"31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), STACS 2014, March 5\u20138, 2014","volume":"25","author":"Marx D.","year":"2014","unstructured":"D. Marx and M. Pilipczuk. Everything you always wanted to know about the parameterized complexity of subgraph isomorphism (but were afraid to ask). In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), STACS 2014, March 5\u20138, 2014, Lyon, France, volume 25 of LIPIcs, pages 542\u2013553, 2014."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1561\/1900000090"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342643"},{"issue":"2","key":"e_1_2_1_38_1","first-page":"176","volume":"11","author":"Qiao M.","year":"2017","unstructured":"M. Qiao, H. Zhang, and H. Cheng. Subgraph Matching: On Compression and Computation. Proc. VLDB Endow., 11(2):176\u2013188, 2017.","journal-title":"Subgraph Matching: On Compression and Computation. Proc. VLDB Endow."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.14778\/3229863.3229874"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.14778\/3021924.3021929"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342272"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453899"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.14778\/3654621.3654635"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196902"},{"key":"e_1_2_1_45_1","first-page":"243","volume-title":"ICDE","author":"Sun S.","unstructured":"S. Sun, Y. Che, L. Wang, and Q. Luo. Efficient parallel subgraph enumeration on a single machine. In ICDE, pages 232\u2013243. IEEE, 2019."},{"key":"e_1_2_1_46_1","first-page":"1098","volume-title":"SIGMOD","author":"Sun S.","unstructured":"S. Sun and Q. Luo. In-memory subgraph matching: An in-depth study. In SIGMOD, pages 1083\u20131098. ACM, 2020."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.14778\/3425879.3425888"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/3589326"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11704-020-0360-y"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.14778\/2311906.2311907"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/321921.321925"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/3604437.3604450"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/3589295"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btl038"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-016-0447-0"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588695"},{"key":"e_1_2_1_57_1","first-page":"2062","volume-title":"SIGMOD","author":"Yang Z.","unstructured":"Z. Yang, L. Lai, X. Lin, K. Hao, and W. Zhang. HUGE: an efficient and scalable subgraph enumeration system. In SIGMOD, pages 2049\u20132062. ACM, 2021."},{"key":"e_1_2_1_58_1","volume-title":"7th International Conference, September 9\u201311, 1981","author":"Yannakakis M.","year":"1981","unstructured":"M. Yannakakis. Algorithms for Acyclic Database Schemes. In Very Large Data Bases, 7th International Conference, September 9\u201311, 1981, Cannes, France, Proceedings, pages 82\u201394. IEEE Computer Society, 1981."},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407840"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/3639315"},{"key":"e_1_2_1_61_1","first-page":"340","volume":"3","author":"Zhao P.","year":"2010","unstructured":"P. Zhao and J. Han. On Graph Query Optimization in Large Networks. Proc. VLDB Endow., 3(1\u20132):340\u2013351, 2010.","journal-title":"On Graph Query Optimization in Large Networks. Proc. VLDB Endow."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3749646.3749693","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,5]],"date-time":"2025-09-05T03:28:51Z","timestamp":1757042931000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3749646.3749693"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7]]},"references-count":61,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2025,7]]}},"alternative-id":["10.14778\/3749646.3749693"],"URL":"https:\/\/doi.org\/10.14778\/3749646.3749693","relation":{},"ISSN":["2150-8097"],"issn-type":[{"type":"print","value":"2150-8097"}],"subject":[],"published":{"date-parts":[[2025,7]]},"assertion":[{"value":"2025-09-04","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}