{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,19]],"date-time":"2026-03-19T22:47:26Z","timestamp":1773960446066,"version":"3.50.1"},"reference-count":45,"publisher":"Association for Computing Machinery (ACM)","issue":"2","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2022,10]]},"abstract":"<jats:p>\n            Consider an edge-weighted graph, and a number of properties of interests (PoIs). Each vertex has a probability of exhibiting each PoI. The joint probability that a set of vertices exhibits a PoI is the probability that this set contains at least one vertex that exhibits this PoI. The\n            <jats:italic>probabilistic group Steiner tree<\/jats:italic>\n            problem is to find a tree such that (i) for each PoI, the joint probability that the set of vertices in this tree exhibits this PoI is no smaller than a threshold value,\n            <jats:italic>e.g.<\/jats:italic>\n            , 0.97; and (ii) the total weight of edges in this tree is the minimum. Solving this problem is useful for mining various graphs with uncertain vertex properties, but is NP-hard. The existing work focuses on certain cases, and cannot perform this task. To meet this challenge, we propose 3 approximation algorithms for solving the above problem. Let |\u0393| be the number of PoIs, and \u03be be an upper bound of the number of vertices for satisfying the threshold value of exhibiting each PoI. Algorithms 1 and 2 have tight approximation guarantees proportional to |\u0393| and \u03be, and exponential time complexities with respect to \u03be and |\u0393|, respectively. In comparison, Algorithm 3 has a looser approximation guarantee proportional to, and a polynomial time complexity with respect to, both |\u0393| and \u03be. Experiments on real and large datasets show that the proposed algorithms considerably outperform the state-of-the-art related work for finding probabilistic group Steiner trees in various cases.\n          <\/jats:p>","DOI":"10.14778\/3565816.3565834","type":"journal-article","created":{"date-parts":[[2022,11,24]],"date-time":"2022-11-24T00:35:16Z","timestamp":1669250116000},"page":"343-355","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Approximating probabilistic group steiner trees in graphs"],"prefix":"10.14778","volume":"16","author":[{"given":"Shuang","family":"Yang","sequence":"first","affiliation":[{"name":"Renmin University of China"}]},{"given":"Yahui","family":"Sun","sequence":"additional","affiliation":[{"name":"Renmin University of China"}]},{"given":"Jiesong","family":"Liu","sequence":"additional","affiliation":[{"name":"Renmin University of China"}]},{"given":"Xiaokui","family":"Xiao","sequence":"additional","affiliation":[{"name":"National University of Singapore"}]},{"given":"Rong-Hua","family":"Li","sequence":"additional","affiliation":[{"name":"Beijing Institute of Technology"}]},{"given":"Zhewei","family":"Wei","sequence":"additional","affiliation":[{"name":"Renmin University of China"}]}],"member":"320","published-online":{"date-parts":[[2022,11,23]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"2022. AMiner. https:\/\/www.aminer.org.  2022. AMiner. https:\/\/www.aminer.org."},{"key":"e_1_2_1_2_1","unstructured":"2022. AMiner: Citation Network Dataset. https:\/\/www.aminer.cn\/citation.  2022. AMiner: Citation Network Dataset. https:\/\/www.aminer.cn\/citation."},{"key":"e_1_2_1_3_1","unstructured":"2022. GroupLens. https:\/\/grouplens.org.  2022. GroupLens. https:\/\/grouplens.org."},{"key":"e_1_2_1_4_1","unstructured":"2022. Microsoft Academic Graph. https:\/\/www.microsoft.com\/en-us\/research\/project\/microsoft-academic-graph.  2022. Microsoft Academic Graph. https:\/\/www.microsoft.com\/en-us\/research\/project\/microsoft-academic-graph."},{"key":"e_1_2_1_5_1","unstructured":"2022. Stanford Network Analysis Project. http:\/\/snap.stanford.edu.  2022. Stanford Network Analysis Project. http:\/\/snap.stanford.edu."},{"key":"e_1_2_1_6_1","unstructured":"2022. Supplement. https:\/\/github.com\/rucdatascience\/PGST\/blob\/main\/Supplement.pdf.  2022. Supplement. https:\/\/github.com\/rucdatascience\/PGST\/blob\/main\/Supplement.pdf."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465315"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1557019.1557039"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11192-020-03414-8"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276719"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2012.228"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702403098"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2007.367929"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.14778\/2556549.2556562"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-2217(02)00707-5"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btq105"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1096"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3132847.3132957"},{"key":"e_1_2_1_19_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_20_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 . 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_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1557019.1557074"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376706"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.196"},{"key":"e_1_2_1_24_1","doi-asserted-by":"crossref","first-page":"957","DOI":"10.1109\/TKDE.2013.67","article-title":"Quasi-SLCA based keyword query processing over probabilistic XML data","volume":"26","author":"Li Jianxin","year":"2013","unstructured":"Jianxin Li , Chengfei Liu , Rui Zhou , and Jeffrey Xu Yu . 2013 . Quasi-SLCA based keyword query processing over probabilistic XML data . IEEE Transactions on Knowledge and Data Engineering 26 , 4 (2013), 957 -- 969 . Jianxin Li, Chengfei Liu, Rui Zhou, and Jeffrey Xu Yu. 2013. Quasi-SLCA based keyword query processing over probabilistic XML data. IEEE Transactions on Knowledge and Data Engineering 26, 4 (2013), 957--969.","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915217"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319877"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389748"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3186728.3164141"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1353343.1353406"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989341"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2014.2365791"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2339530.2339690"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1951365.1951408"},{"key":"e_1_2_1_34_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 . 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_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2007.367907"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2007.367935"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.14778\/3450980.3450982"},{"key":"e_1_2_1_38_1","volume-title":"A combination approach to web user profiling. ACM Transactions on Knowledge Discovery from Data 5, 1","author":"Tang Jie","year":"2010","unstructured":"Jie Tang , Limin Yao , Duo Zhang , and Jing Zhang . 2010. A combination approach to web user profiling. ACM Transactions on Knowledge Discovery from Data 5, 1 ( 2010 ), 1--44. Jie Tang, Limin Yao, Duo Zhang, and Jing Zhang. 2010. A combination approach to web user profiling. ACM Transactions on Knowledge Discovery from Data 5, 1 (2010), 1--44."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1272743.1272745"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/TBDATA.2016.2546303"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/512274.512284"},{"key":"e_1_2_1_42_1","volume-title":"Efficient processing of top-k queries in uncertain databases with x-relations","author":"Yi Ke","year":"2008","unstructured":"Ke Yi , Feifei Li , George Kollios , and Divesh Srivastava . 2008. Efficient processing of top-k queries in uncertain databases with x-relations . IEEE transactions on knowledge and data engineering 20, 12 ( 2008 ), 1669--1682. Ke Yi, Feifei Li, George Kollios, and Divesh Srivastava. 2008. Efficient processing of top-k queries in uncertain databases with x-relations. IEEE transactions on knowledge and data engineering 20, 12 (2008), 1669--1682."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.14778\/2311906.2311908"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2012.222"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2010.5447891"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3565816.3565834","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:37:08Z","timestamp":1672220228000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3565816.3565834"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,10]]},"references-count":45,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,10]]}},"alternative-id":["10.14778\/3565816.3565834"],"URL":"https:\/\/doi.org\/10.14778\/3565816.3565834","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2022,10]]},"assertion":[{"value":"2022-11-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}