{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,15]],"date-time":"2026-09-15T01:09:32Z","timestamp":1789434572246,"version":"build-2803163510"},"reference-count":87,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2025,6,17]]},"abstract":"<jats:p>Subgraph queries are widely used but face significant challenges due to complex patterns such as negative and optional edges. While worst-case optimal joins have proven effective for subgraph queries with regular patterns, no method has been proposed that can process queries involving complex patterns in a single multi-way join. Existing CPU-based and GPU-based methods experience intermediate data explosion when processing complex patterns following regular patterns. In addition, GPU-based methods struggle with issues of wasted GPU memory and redundant computation. In this paper, we propose cuMatch, a GPU-based unified worst-case optimal join processing method for subgraph queries. It avoids intermediate data explosions by processing even complex pattern queries in a single multi-way join. It is also memory-efficient and fast, due to a new partitioning format, scheduling method, and task fusion technique. Extensive experiments demonstrate that cuMatch outperforms state-of-the-art methods by orders of magnitude, without out-of-memory errors.<\/jats:p>","DOI":"10.1145\/3725398","type":"journal-article","created":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T21:23:29Z","timestamp":1750281809000},"page":"1-28","source":"Crossref","is-referenced-by-count":5,"title":["cuMatch: A GPU-based Memory-Efficient Worst-case Optimal Join Processing Method for Subgraph Queries with Complex Patterns"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0009-0008-3927-7935","authenticated-orcid":false,"given":"Sungwoo","family":"Park","sequence":"first","affiliation":[{"name":"Korea Advanced Institute of Science and Technology, Daejeon, Republic of Korea"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0004-9027-0916","authenticated-orcid":false,"given":"Seyeon","family":"Oh","sequence":"additional","affiliation":[{"name":"GraphAI, Daejeon, Republic of Korea"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7852-0853","authenticated-orcid":false,"given":"Min-Soo","family":"Kim","sequence":"additional","affiliation":[{"name":"Korea Advanced Institute of Science and Technology, Daejeon, Republic of Korea"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,6,18]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3129246"},{"key":"e_1_2_2_2_1","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 Low-Memory Dataflows. Proceedings of the VLDB Endowment, Vol. 11, 6 (2018)."},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2021.3073494"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3589312"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2742796"},{"key":"e_1_2_2_6_1","unstructured":"Medha Atre. 2013. A technique for SPARQL OPTIONAL (left-outer-join) queries. CoRR abs\/1304.7 (2013)."},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/110859440"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/11428848_97"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3300086"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915236"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-20081-7_14"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2017.02.007"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2750545"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/800157.805047"},{"key":"e_1_2_2_15_1","unstructured":"NVIDIA Corporation. 2024. RAPIDS. https:\/\/rapids.ai."},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10844-022-00742-4"},{"key":"e_1_2_2_17_1","volume-title":"The Conference on Innovative Data Systems Research.","author":"Feng Xiyang","year":"2023","unstructured":"Xiyang Feng, Guodong Jin, Ziyi Chen, Chang Liu, and Semih Saliho\u011flu. 2023. K\u00d9ZU graph database management system. In The Conference on Innovative Data Systems Research."},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407797"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3183734"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/244810.244812"},{"key":"e_1_2_2_21_1","series-title":"SIAM journal on matrix analysis and applications","volume-title":"Sparse matrices in MATLAB: Design and implementation","author":"Gilbert John R","year":"1992","unstructured":"John R Gilbert, Cleve Moler, and Robert Schreiber. 1992. Sparse matrices in MATLAB: Design and implementation. SIAM journal on matrix analysis and applications, Vol. 13, 1 (1992), 333-356."},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/HPCS48598.2019.9188120"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389699"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.14778\/2733004.2733010"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319880"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487575.2487581"},{"key":"e_1_2_2_27_1","unstructured":"HeavyDB. 2024. HeavyDB. https:\/\/github.com\/heavyai\/heavydb."},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3342195.3387548"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.14778\/3157794.3157799"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3534678.3539096"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588692"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827595287997"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-022-00749-x"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915204"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196915"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772751"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-021-00708-y"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3649329.3656238"},{"key":"e_1_2_2_39_1","unstructured":"Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. http:\/\/snap.stanford.edu\/data."},{"key":"e_1_2_2_40_1","volume-title":"GraphMini: Accelerating Graph Pattern Matching Using Auxiliary Graphs. In 2023 32nd International Conference on Parallel Architectures and Compilation Techniques (PACT). IEEE, 211-224","author":"Liu Juelin","year":"2023","unstructured":"Juelin Liu, Sandeep Polisetty, Hui Guan, and Marco Serafini. 2023. GraphMini: Accelerating Graph Pattern Matching Using Auxiliary Graphs. In 2023 32nd International Conference on Parallel Architectures and Compilation Techniques (PACT). IEEE, 211-224."},{"key":"e_1_2_2_41_1","first-page":"443","volume-title":"2019 USENIX Annual Technical Conference (USENIX ATC 19)","author":"Ma Lingxiao","year":"2019","unstructured":"Lingxiao Ma, Zhi Yang, Youshan Miao, Jilong Xue, Ming Wu, Lidong Zhou, and Yafei Dai. 2019. {NeuGraph}: Parallel deep neural network computation on large graphs. In 2019 USENIX Annual Technical Conference (USENIX ATC 19). 443-458."},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3064176.3064191"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687553.1687618"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3469379.3469383"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3341301.3359633"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3446980"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3461837.3464516"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342643"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4302-3229-2_11"},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3380565"},{"key":"e_1_2_2_51_1","first-page":"29","article-title":"Umbra: A Disk-Based System with In-Memory Performance","volume":"20","author":"Neumann Thomas","year":"2020","unstructured":"Thomas Neumann and Michael J Freitag. 2020. Umbra: A Disk-Based System with In-Memory Performance. In CIDR, Vol. 20. 29.","journal-title":"CIDR"},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/3196959.3196990"},{"key":"e_1_2_2_53_1","unstructured":"Hung Q Ngo Ely Porat Christopher R\u00e9 and Atri Rudra. 2012. Worst-case Optimal Join Algorithms. (2012)."},{"key":"e_1_2_2_54_1","unstructured":"Nvidia. 2024. CUDA programming guide. https:\/\/docs.nvidia.com\/cuda\/cuda-c-programming-guide."},{"key":"e_1_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3064014"},{"key":"e_1_2_2_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/3627535.3638490"},{"key":"e_1_2_2_57_1","doi-asserted-by":"publisher","DOI":"10.14778\/3425879.3425890"},{"key":"e_1_2_2_58_1","doi-asserted-by":"publisher","DOI":"10.14778\/3149193.3149198"},{"key":"e_1_2_2_59_1","doi-asserted-by":"publisher","DOI":"10.14778\/3229863.3229874"},{"key":"e_1_2_2_60_1","doi-asserted-by":"publisher","DOI":"10.1109\/SC.2018.00024"},{"key":"e_1_2_2_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/2815400.2815408"},{"key":"e_1_2_2_62_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-019-00548-x"},{"key":"e_1_2_2_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/3127479.3131625"},{"key":"e_1_2_2_64_1","volume-title":"SC20: International Conference for High Performance Computing, Networking, Storage and Analysis. IEEE, 1-14","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 SC20: International Conference for High Performance Computing, Networking, Storage and Analysis. IEEE, 1-14."},{"key":"e_1_2_2_65_1","doi-asserted-by":"publisher","DOI":"10.1109\/PADSW.2018.8644869"},{"key":"e_1_2_2_66_1","doi-asserted-by":"publisher","DOI":"10.14778\/3425879.3425888"},{"key":"e_1_2_2_67_1","doi-asserted-by":"publisher","DOI":"10.1145\/3589326"},{"key":"e_1_2_2_68_1","doi-asserted-by":"crossref","unstructured":"Zhao Sun Hongzhi Wang Haixun Wang Bin Shao and Jianzhong Li. 2012. Efficient subgraph matching on billion node graphs. arXiv preprint arXiv:1205.6691 (2012).","DOI":"10.14778\/2311906.2311907"},{"key":"e_1_2_2_69_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-18120-2_18"},{"key":"e_1_2_2_70_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01263334"},{"key":"e_1_2_2_71_1","volume-title":"Proc. International Conference on Database Theory.","author":"Veldhuizen Todd L","year":"2014","unstructured":"Todd L Veldhuizen. 2014. Leapfrog triejoin: A simple, worst-case optimal join algorithm. In Proc. International Conference on Database Theory."},{"key":"e_1_2_2_72_1","unstructured":"Leyuan Wang and John D Owens. 2020. Fast gunrock subgraph matching (gsm) on gpus. arXiv preprint arXiv:2003.01527 (2020)."},{"key":"e_1_2_2_73_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3526134"},{"key":"e_1_2_2_74_1","doi-asserted-by":"publisher","DOI":"10.1145\/3589295"},{"key":"e_1_2_2_75_1","unstructured":"Mark Weber Jie Chen Toyotaro Suzumura Aldo Pareja Tengfei Ma Hiroki Kanezashi Tim Kaler Charles E Leiserson and Tao B Schardl. 2018. Scalable graph learning for anti-money laundering: A first look. arXiv preprint arXiv:1812.00076 (2018) 1-7."},{"key":"e_1_2_2_76_1","volume-title":"SC22: International Conference for High Performance Computing, Networking, Storage and Analysis. IEEE, 1-13","author":"Wei Yihua","year":"2022","unstructured":"Yihua Wei and Peng Jiang. 2022. STMatch: accelerating graph pattern matching on GPU with stack-based loop optimizations. In SC22: International Conference for High Performance Computing, Networking, Storage and Analysis. IEEE, 1-13."},{"key":"e_1_2_2_77_1","volume-title":"International Workshop on Accelerating Data Management Systems Using Modern Processor and Storage Architectures","volume":"10","author":"Wu Haicheng","year":"2014","unstructured":"Haicheng Wu, Daniel Zinn, Molham Aref, and Sudhakar Yalamanchili. 2014. Multipredicate join algorithms for accelerating relational graph processing on GPUs. In International Workshop on Accelerating Data Management Systems Using Modern Processor and Storage Architectures, Vol. 10."},{"key":"e_1_2_2_78_1","doi-asserted-by":"publisher","DOI":"10.1145\/3458817.3476214"},{"key":"e_1_2_2_79_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE60146.2024.00244"},{"key":"e_1_2_2_80_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE48307.2020.00112"},{"key":"e_1_2_2_81_1","volume-title":"2024 27th International Conference on Computer Supported Cooperative Work in Design (CSCWD). IEEE, 3110-3115","author":"Zhang Dongyang","year":"2024","unstructured":"Dongyang Zhang, Jianhuan Zhuo, Yile Li, Yinliang Yue, and Weiping Wang. 2024b. R 2 Mine: A Reduced Redundancy Computation Graph Pattern Matching System. In 2024 27th International Conference on Computer Supported Cooperative Work in Design (CSCWD). IEEE, 3110-3115."},{"key":"e_1_2_2_82_1","doi-asserted-by":"publisher","DOI":"10.1145\/1516360.1516384"},{"key":"e_1_2_2_83_1","doi-asserted-by":"publisher","DOI":"10.1145\/3456529.3456548"},{"key":"e_1_2_2_84_1","doi-asserted-by":"publisher","DOI":"10.1145\/3639315"},{"key":"e_1_2_2_85_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2013.10.003"},{"key":"e_1_2_2_86_1","first-page":"375","volume-title":"2015 USENIX Annual Technical Conference (USENIX ATC 15)","author":"Zhu Xiaowei","year":"2015","unstructured":"Xiaowei Zhu, Wentao Han, and Wenguang Chen. 2015. {GridGraph}:{Large-Scale} graph processing on a single machine using 2-level hierarchical partitioning. In 2015 USENIX Annual Technical Conference (USENIX ATC 15). 375-386."},{"key":"e_1_2_2_87_1","doi-asserted-by":"publisher","DOI":"10.1145\/2884045.2884054"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3725398","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T18:54:11Z","timestamp":1774983251000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3725398"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,17]]},"references-count":87,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,6,17]]}},"alternative-id":["10.1145\/3725398"],"URL":"https:\/\/doi.org\/10.1145\/3725398","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,6,17]]}}}