{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,13]],"date-time":"2026-06-13T04:58:25Z","timestamp":1781326705927,"version":"3.54.1"},"reference-count":66,"publisher":"Association for Computing Machinery (ACM)","issue":"6","funder":[{"DOI":"10.13039\/501100012166","name":"National Key R&D Program of China","doi-asserted-by":"crossref","award":["2023YFB4503600"],"award-info":[{"award-number":["2023YFB4503600"]}],"id":[{"id":"10.13039\/501100012166","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["62202472, U2241211, 62427808 and U24A20255"],"award-info":[{"award-number":["62202472, U2241211, 62427808 and U24A20255"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2025,12,4]]},"abstract":"<jats:p>Given an edge-weighted graph and a set of potentially overlapping vertex groups, a group Steiner tree (GST) is a minimum weight tree that includes at least one vertex in each group. Finding GSTs serves as a classical approach to keyword search in relational databases. Existing studies use CPUs to find optimal GSTs in a serial way, and remain slow in some cases. No prior work has applied GPUs to meet this challenge. To fill this gap, first, we propose a parallel-friendly GST solution framework, by breaking the traditional bottom-up dynamic programming order. Second, since a direct execution of this framework on GPUs faces a severe workload imbalance problem, we develop a GST-customized load balancing approach. Specifically, we employ kernel fusion and global memory coalescing techniques to efficiently utilize different parallel granularities to match divergent tree construction workloads. Third, since existing pruning methods cannot be directly applied to a parallel scheme, we modify feasible pruning procedures to reduce the computation burden, and rigorously prove the solution correctness. Furthermore, inspired by recent applications, we present a novel dynamic programming algorithm for finding optimal diameter-bounded GSTs on GPUs. Experiments on various real datasets show that the proposed techniques achieve a speedup of 48-2390\u00d7 over state-of-the-art methods, and can handle some large weighted graphs where existing solutions are too slow to be applied, and thus could greatly improve the user experience in related applications.<\/jats:p>","DOI":"10.1145\/3769792","type":"journal-article","created":{"date-parts":[[2025,12,6]],"date-time":"2025-12-06T04:32:13Z","timestamp":1764995533000},"page":"1-27","source":"Crossref","is-referenced-by-count":0,"title":["Fast Optimal Group Steiner Tree Search using GPUs"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0009-0004-0157-4070","authenticated-orcid":false,"given":"Jiayu","family":"Li","sequence":"first","affiliation":[{"name":"Renmin University of China, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3730-8538","authenticated-orcid":false,"given":"Yahui","family":"Sun","sequence":"additional","affiliation":[{"name":"Renmin University of China, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-5869-1353","authenticated-orcid":false,"given":"Bojing","family":"Ma","sequence":"additional","affiliation":[{"name":"Renmin University of China, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-3605-0683","authenticated-orcid":false,"given":"Libang","family":"Chen","sequence":"additional","affiliation":[{"name":"Renmin University of China, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-8481-6646","authenticated-orcid":false,"given":"Mengxi","family":"Hu","sequence":"additional","affiliation":[{"name":"Renmin University of China, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1983-7321","authenticated-orcid":false,"given":"Feng","family":"Zhang","sequence":"additional","affiliation":[{"name":"Renmin University of China, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8658-6599","authenticated-orcid":false,"given":"Rong-Hua","family":"Li","sequence":"additional","affiliation":[{"name":"Beijing Institute of Technology, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,12,5]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"2025. AMiner. https:\/\/www.aminer.org."},{"key":"e_1_2_1_2_1","unstructured":"2025. NVIDIA AMPERE GA102 GPU architecture. https:\/\/www.nvidia.com\/content\/PDF\/nvidia-ampere-ga-102-gpuarchitecture-whitepaper-v2.pdf."},{"key":"e_1_2_1_3_1","unstructured":"2025. Our codes and datasets. https:\/\/github.com\/toziki\/GPU4GST-sigmod."},{"key":"e_1_2_1_4_1","unstructured":"2025. Pushshift Reddit API Documentation. https:\/\/github.com\/pushshift\/api."},{"key":"e_1_2_1_5_1","unstructured":"2025. Stanford Network Analysis Project. http:\/\/snap.stanford.edu."},{"key":"e_1_2_1_6_1","unstructured":"2025. Tuning CUDA Applications for Volta. https:\/\/docs.nvidia.com\/cuda\/volta-tuning-guide."},{"key":"e_1_2_1_7_1","volume-title":"St\u00e9phane Horel, Ioana Manolescu, and Youssr Youssef.","author":"Anadiotis Angelos-Christos","year":"2021","unstructured":"Angelos-Christos Anadiotis, Oana Balalau, Th\u00e9o Bouganim, Francesco Chimienti, Helena Galhardas, Mhd Yamen Haddad, St\u00e9phane Horel, Ioana Manolescu, and Youssr Youssef. 2021. Empowering investigative journalism with graph-based heterogeneous data management. Bulletin of the IEEE Computer Society Technical Committee on Data Engineering (2021)."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE55515.2023.00200"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2011.59"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2002.994756"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/CGO51591.2021.9370321"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.47"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2012.228"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2014.45"},{"key":"e_1_2_1_15_1","volume-title":"A note on two problems in connexion with graphs. Numerische mathematik 1, 1","author":"Dijkstra Edsger W","year":"1959","unstructured":"Edsger W Dijkstra. 1959. A note on two problems in connexion with graphs. Numerische mathematik 1, 1 (1959), 269-271."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2007.367929"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2015.06.008"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230010302"},{"key":"e_1_2_1_19_1","volume-title":"Send-and-split method for minimum-concave-cost network flows. Mathematics of operations research 12, 4","author":"Erickson Ranel E","year":"1987","unstructured":"Ranel E Erickson, Clyde L Monma, and Arthur F Veinott Jr. 1987. Send-and-split method for minimum-concave-cost network flows. Mathematics of operations research 12, 4 (1987), 634-664."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPSW55747.2022.00140"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btq105"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/28869.28874"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1096"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/HPEC.2019.8916216"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389699"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3508352.3549434"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/43.875285"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1002\/1097-0037(200101)37:1<8::AID-NET2>3.0.CO;2-R"},{"key":"e_1_2_1_29_1","volume-title":"Computer architecture: a quantitative approach","author":"Hennessy John L","unstructured":"John L Hennessy and David A Patterson. 2011. Computer architecture: a quantitative approach. Elsevier."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3452815"},{"key":"e_1_2_1_31_1","volume-title":"International Workshop on Graph-Theoretic Concepts in Computer Science. Springer, 109-118","author":"Ihler Edmund","year":"1990","unstructured":"Edmund Ihler. 1990. Bounds on the quality of approximate solutions to the group Steiner problem. In International Workshop on Graph-Theoretic Concepts in Computer Science. Springer, 109-118."},{"key":"e_1_2_1_32_1","unstructured":"Bj\u00f6rn Karlsson. 2005. Beyond the C standard library: an introduction to boost. Pearson Education."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.5555\/1413957.1413966"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1557019.1557074"},{"key":"e_1_2_1_35_1","volume-title":"Efficient behavior of small-world networks. Physical review letters 87, 19","author":"Latora Vito","year":"2001","unstructured":"Vito Latora and Massimo Marchiori. 2001. Efficient behavior of small-world networks. Physical review letters 87, 19 (2001), 198701."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.196"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915217"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/s41019-020-00142-0"},{"key":"e_1_2_1_39_1","first-page":"271","article-title":"Keyword search algorithm of large graph based on GPU (in Chinese)","volume":"56","author":"Lin He Xiang","year":"2022","unstructured":"He Xiang Lin, Lian Peng Qiao, Ye Yuan, and Guo Ren Wang. 2022. Keyword search algorithm of large graph based on GPU (in Chinese). Journal of Zhejiang University 56, 2 (2022), 271-279.","journal-title":"Journal of Zhejiang University"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2807591.2807594"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2339530.2339690"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.22369\/issn.2153-4136\/8\/1\/4"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-27122-4_31"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10766-021-00723-0"},{"key":"e_1_2_1_45_1","volume-title":"GPU accelerated rectilinear Steiner tree construction. Master's thesis","author":"\u00d6zcan Din\u00e7er","unstructured":"Din\u00e7er \u00d6zcan. 2015. GPU accelerated rectilinear Steiner tree construction. Master's thesis. Middle East Technical University."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230110110"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPSW.2016.108"},{"key":"e_1_2_1_48_1","volume-title":"International Workshop on Graph-theoretic Concepts in Computer Science. Springer, 196-210","author":"Reich Gabriele","year":"1989","unstructured":"Gabriele Reich and Peter Widmayer. 1989. Beyond Steiner's problem: A VLSI oriented generalization. In International Workshop on Graph-theoretic Concepts in Computer Science. Springer, 196-210."},{"key":"e_1_2_1_49_1","unstructured":"G Reich and P Widmayer. 1991. Approximate minimum spanning trees for vertex classes. Technical Report. Technical Report Inst. fur Informatik Freiburg Univ."},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319871"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457279"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/3366423.3380110"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPSW.2010.5470817"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.14778\/3450980.3450982"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1109\/IC3.2017.8284293"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1109\/SC.2014.21"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/3437801.3441605"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1109\/TBDATA.2016.2546303"},{"key":"e_1_2_1_59_1","volume-title":"Small worlds: the dynamics of networks between order and randomness","author":"Watts Duncan J","unstructured":"Duncan J Watts. 1999. Small worlds: the dynamics of networks between order and randomness. Princeton university press."},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.14778\/3551793.3551806"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.14778\/3565816.3565834"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE48307.2020.00112"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-020-00636-3"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/3543507.3583257"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/3605731.3605746"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1109\/HPCA53966.2022.00064"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3769792","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,13]],"date-time":"2026-06-13T04:45:19Z","timestamp":1781325919000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3769792"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,12,4]]},"references-count":66,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2025,12,4]]}},"alternative-id":["10.1145\/3769792"],"URL":"https:\/\/doi.org\/10.1145\/3769792","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,12,4]]}}}