More Web Proxy on the site http://driver.im/

research-article

Efficient Approximation Algorithms for the Diameter-Bounded Max-Coverage Group Steiner Tree Problem

Authors:

Gong ChengAuthors Info & Claims

WWW '23: Proceedings of the ACM Web Conference 2023

Pages 199 - 209

https://doi.org/10.1145/3543507.3583257

Published: 30 April 2023 Publication History

Abstract

The Diameter-bounded max-Coverage Group Steiner Tree (DCGST) problem has recently been proposed as an expressive way of formulating keyword-based search and exploration of knowledge graphs. It aims at finding a diameter-bounded tree which covers the most given groups of vertices and has the minimum weight. In contrast to its specialization—the classic Group Steiner Tree (GST) problem which has been extensively studied, the emerging DCGST problem still lacks an efficient algorithm. In this paper, we propose Cba, the first approximation algorithm for the DCGST problem, and we prove its worst-case approximation ratio. Furthermore, we incorporate a best-first search strategy with two pruning methods into PrunedCBA, an improved approximation algorithm. Our extensive experiments on real and synthetic graphs demonstrate the effectiveness and efficiency of PrunedCBA.

References

[1]

[1] Takuya Akiba, Yoichi Iwata, and Yuichi Yoshida. 2013. Fast exact shortest-path distance queries on large networks by pruned landmark labeling. In SIGMOD 2013. 349–360. https://doi.org/10.1145/2463676.2465315

Digital Library

[2]

[2] Kemafor Anyanwu, Angela Maduko, and Amit P. Sheth. 2005. SemRank: ranking complex relationship search results on the semantic web. In WWW 2005. 117–127. https://doi.org/10.1145/1060745.1060766

Digital Library

[3]

[3] Gong Cheng, Shuxin Li, Ke Zhang, and Chengkai Li. 2020. Generating Compact and Relaxable Answers to Keyword Queries over Knowledge Graphs. In ISWC 2020, Part I. 110–127. https://doi.org/10.1007/978-3-030-62419-4_7

Digital Library

[4]

[4] Gong Cheng, Daxin Liu, and Yuzhong Qu. 2016. Efficient Algorithms for Association Finding and Frequent Association Pattern Mining. In ISWC 2016, Part I. 119–134. https://doi.org/10.1007/978-3-319-46523-4_8

Digital Library

[5]

[5] Gong Cheng, Daxin Liu, and Yuzhong Qu. 2021. Fast Algorithms for Semantic Association Search and Pattern Mining. IEEE Trans. Knowl. Data Eng. 33, 4 (2021), 1490–1502. https://doi.org/10.1109/TKDE.2019.2942031

Digital Library

[6]

[6] Gong Cheng, Fei Shao, and Yuzhong Qu. 2017. An Empirical Evaluation of Techniques for Ranking Semantic Associations. IEEE Trans. Knowl. Data Eng. 29, 11 (2017), 2388–2401. https://doi.org/10.1109/TKDE.2017.2735970

Digital Library

[7]

[7] Joel Coffman and Alfred C. Weaver. 2014. An Empirical Performance Evaluation of Relational Keyword Search Techniques. IEEE Trans. Knowl. Data Eng. 26, 1 (2014), 30–42. https://doi.org/10.1109/TKDE.2012.228

Digital Library

[8]

[8] Bolin Ding, Jeffrey Xu Yu, Shan Wang, Lu Qin, Xiao Zhang, and Xuemin Lin. 2007. Finding Top-k Min-Cost Connected Trees in Databases. In ICDE 2007. 836–845. https://doi.org/10.1109/ICDE.2007.367929

[9]

[9] Eran Halperin and Robert Krauthgamer. 2003. Polylogarithmic inapproximability. In STOC 2003. 585–594. https://doi.org/10.1145/780542.780628

Digital Library

[10]

[10] Faegheh Hasibi, Fedor Nikolaev, Chenyan Xiong, Krisztian Balog, Svein Erik Bratsberg, Alexander Kotov, and Jamie Callan. 2017. DBpedia-Entity v2: A Test Collection for Entity Search. In SIGIR 2017. 1265–1268. https://doi.org/10.1145/3077136.3080751

Digital Library

[11]

[11] Aidan Hogan, Eva Blomqvist, Michael Cochez, Claudia d’Amato, Gerard de Melo, Claudio Gutiérrez, Sabrina Kirrane, José Emilio Labra Gayo, Roberto Navigli, Sebastian Neumaier, Axel-Cyrille Ngonga Ngomo, Axel Polleres, Sabbir M. Rashid, Anisa Rula, Lukas Schmelzeisen, Juan F. Sequeda, Steffen Staab, and Antoine Zimmermann. 2021. Knowledge Graphs. ACM Comput. Surv. 54, 4 (2021), 71:1–71:37. https://doi.org/10.1145/3447772

Digital Library

[12]

[12] Edmund Ihler. 1991. The Complexity of Approximating the Class Steiner Tree Problem. In WG 1991, Vol. 570. 85–96. https://doi.org/10.1007/3-540-55121-2_8

[13]

[13] Sanjiv Kapoor and Mohammad Sarwat. 2007. Bounded-Diameter Minimum-Cost Graph Problems. Theory Comput. Syst. 41, 4 (2007), 779–794. https://doi.org/10.1007/s00224-006-1305-z

Digital Library

[14]

[14] Rong-Hua Li, Lu Qin, Jeffrey Xu Yu, and Rui Mao. 2016. Efficient and Progressive Group Steiner Tree Search. In SIGMOD 2016. 91–106. https://doi.org/10.1145/2882903.2915217

Digital Library

[15]

[15] Shuxin Li, Zixian Huang, Gong Cheng, Evgeny Kharlamov, and Kalpa Gunaratna. 2020. Enriching Documents with Compact, Representative, Relevant Knowledge Graphs. In IJCAI 2020. 1748–1754. https://doi.org/10.24963/ijcai.2020/242

[16]

[16] Madhav V. Marathe, R. Ravi, Ravi Sundaram, S. S. Ravi, Daniel J. Rosenkrantz, and Harry B. Hunt III. 1998. Bicriteria Network Design Problems. J. Algorithms 28, 1 (1998), 142–171. https://doi.org/10.1006/jagm.1998.0930

Digital Library

[17]

[17] Ali Mashreghi and Alireza Zarei. 2016. When Diameter Matters: Parameterized Approximation Algorithms for Bounded Diameter Minimum Steiner Tree Problem. Theory Comput. Syst. 58, 2 (2016), 287–303. https://doi.org/10.1007/s00224-015-9615-7

Digital Library

[18]

[18] Alexander H. Miller, Adam Fisch, Jesse Dodge, Amir-Hossein Karimi, Antoine Bordes, and Jason Weston. 2016. Key-Value Memory Networks for Directly Reading Documents. In EMNLP 2016. 1400–1409. https://doi.org/10.18653/v1/d16-1147

[19]

[19] Giuseppe Pirrò. 2015. Explaining and Suggesting Relatedness in Knowledge Graphs. In ISWC 2015, Part I. 622–639. https://doi.org/10.1007/978-3-319-25007-6_36

Digital Library

[20]

[20] Yuxuan Shi, Gong Cheng, and Evgeny Kharlamov. 2020. Keyword Search over Knowledge Graphs via Static and Dynamic Hub Labelings. In WWW 2020. 235–245. https://doi.org/10.1145/3366423.3380110

Digital Library

[21]

[21] Yuxuan Shi, Gong Cheng, Trung-Kien Tran, Evgeny Kharlamov, and Yulin Shen. 2021. Efficient Computation of Semantically Cohesive Subgraphs for Keyword-Based Knowledge Graph Exploration. In WWW 2021. 1410–1421. https://doi.org/10.1145/3442381.3449900

Digital Library

[22]

[22] Yuxuan Shi, Gong Cheng, Trung-Kien Tran, Jie Tang, and Evgeny Kharlamov. 2021. Keyword-Based Knowledge Graph Exploration Based on Quadratic Group Steiner Trees. In IJCAI 2021. 1555–1562. https://doi.org/10.24963/ijcai.2021/215

[23]

[23] Christian Sommer. 2014. Shortest-path queries in static networks. ACM Comput. Surv. 46, 4 (2014), 45:1–45:31. https://doi.org/10.1145/2530531

Digital Library

[24]

[24] Yahui Sun, Xiaokui Xiao, Bin Cui, Saman K. Halgamuge, Theodoros Lappas, and Jun Luo. 2021. Finding Group Steiner Trees in Graphs with both Vertex and Edge Weights. Proc. VLDB Endow. 14, 7 (2021), 1137–1149. https://doi.org/10.14778/3450980.3450982

Digital Library

[25]

[25] Xiaxia Wang, Gong Cheng, Tengteng Lin, Jing Xu, Jeff Z. Pan, Evgeny Kharlamov, and Yuzhong Qu. 2021. PCSG: Pattern-Coverage Snippet Generation for RDF Datasets. In ISWC 2021. 3–20. https://doi.org/10.1007/978-3-030-88361-4_1

Digital Library

[26]

[26] Xiaxia Wang, Gong Cheng, Jeff Z. Pan, Evgeny Kharlamov, and Yuzhong Qu. 2023. BANDAR: Benchmarking Snippet Generation Algorithms for (RDF) Dataset Search. IEEE Trans. Knowl. Data Eng. 35, 2 (2023), 1227–1241. https://doi.org/10.1109/TKDE.2021.3095309

[27]

[27] Hrag Yoghourdjian, Shady Elbassuoni, Mohamad Jaber, and Hiba Arnaout. 2017. Top-k Keyword Search over Wikipedia-based RDF Knowledge Graphs. In IC3K 2017, Volume 1. 17–26. https://doi.org/10.5220/0006411400170026

Cited By

Wang XCheng GLarson K(2024)A survey on extractive knowledge graph summarizationProceedings of the Thirty-Third International Joint Conference on Artificial Intelligence10.24963/ijcai.2024/916(8290-8298)Online publication date: 3-Aug-2024
https://dl.acm.org/doi/10.24963/ijcai.2024/916
Chen QChen JZhou XCheng GHui Yang GWang HHan SHauff CZuccon GZhang Y(2024)Enhancing Dataset Search with Compact Data SnippetsProceedings of the 47th International ACM SIGIR Conference on Research and Development in Information Retrieval10.1145/3626772.3657837(1093-1103)Online publication date: 10-Jul-2024
https://dl.acm.org/doi/10.1145/3626772.3657837
Wang XCheng GChua TNgo CKa-Wei Lee RKumar RLauw H(2024)A Fast Hop-Biased Approximation Algorithm for the Quadratic Group Steiner Tree ProblemProceedings of the ACM Web Conference 202410.1145/3589334.3645325(312-321)Online publication date: 13-May-2024
https://dl.acm.org/doi/10.1145/3589334.3645325
Show More Cited By

Index Terms

Efficient Approximation Algorithms for the Diameter-Bounded Max-Coverage Group Steiner Tree Problem
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Graph algorithms

Recommendations

A Better Constant-Factor Approximation for Selected-Internal Steiner Minimum Tree

The selected-internal Steiner minimum tree problem is a generalization of original Steiner minimum tree problem. Given a weighted complete graph G=(V,E) with weight function c, and two subsets RźźR⊆V with |RźRź|ź2, selected-internal Steiner minimum tree ...
A Better Constant-Factor Approximation for Selected-Internal Steiner Minimum Tree
Special Issue: Computation and Combinatorial Optimization; Guest Editors: Xiaodong Hu and Jie Wang

The selected-internal Steiner minimum tree problem is a generalization of original Steiner minimum tree problem. Given a weighted complete graph G=(V,E) with weight function c, and two subsets R ^′ ⊊ R⊆V with |R−R ^′|≥2, selected-internal Steiner minimum ...
A PTAS for planar group Steiner tree via spanner bootstrapping and prize collecting
STOC '16: Proceedings of the forty-eighth annual ACM symposium on Theory of Computing

We present the first polynomial-time approximation scheme (PTAS), i.e., (1+ε)-approximation algorithm for any constant ε> 0, for the planar group Steiner tree problem (in which each group lies on a boundary of a face). This result improves on the best ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

WWW '23: Proceedings of the ACM Web Conference 2023

April 2023

4293 pages

ISBN:9781450394161

DOI:10.1145/3543507

Copyright © 2023 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGWEB: ACM Special Interest Group on Hypertext, Hypermedia, and Web

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 30 April 2023

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed limited

Funding Sources

NSFC
CAAI-Huawei MindSpore Open Fund

Conference

WWW '23

Sponsor:

SIGWEB

WWW '23: The ACM Web Conference 2023

April 30 - May 4, 2023

TX, Austin, USA

Acceptance Rates

Overall Acceptance Rate 1,899 of 8,196 submissions, 23%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
217
Total Downloads

Downloads (Last 12 months)62
Downloads (Last 6 weeks)4

Reflects downloads up to 06 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Wang XCheng GLarson K(2024)A survey on extractive knowledge graph summarizationProceedings of the Thirty-Third International Joint Conference on Artificial Intelligence10.24963/ijcai.2024/916(8290-8298)Online publication date: 3-Aug-2024
https://dl.acm.org/doi/10.24963/ijcai.2024/916
Chen QChen JZhou XCheng GHui Yang GWang HHan SHauff CZuccon GZhang Y(2024)Enhancing Dataset Search with Compact Data SnippetsProceedings of the 47th International ACM SIGIR Conference on Research and Development in Information Retrieval10.1145/3626772.3657837(1093-1103)Online publication date: 10-Jul-2024
https://dl.acm.org/doi/10.1145/3626772.3657837
Wang XCheng GChua TNgo CKa-Wei Lee RKumar RLauw H(2024)A Fast Hop-Biased Approximation Algorithm for the Quadratic Group Steiner Tree ProblemProceedings of the ACM Web Conference 202410.1145/3589334.3645325(312-321)Online publication date: 13-May-2024
https://dl.acm.org/doi/10.1145/3589334.3645325
Zhang KChen JHuang ZCheng GFrommholz IHopfgartner FLee MOakes MLalmas MZhang MSantos R(2023)Weight Matters: An Empirical Investigation of Distance Oracles on Knowledge GraphsProceedings of the 32nd ACM International Conference on Information and Knowledge Management10.1145/3583780.3615246(4440-4444)Online publication date: 21-Oct-2023
https://dl.acm.org/doi/10.1145/3583780.3615246

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

HTML Format

View this article in HTML Format.

Media

Figures

Other

Tables

View Table of Contents