{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,3]],"date-time":"2026-02-03T22:19:31Z","timestamp":1770157171763,"version":"3.49.0"},"reference-count":61,"publisher":"Association for Computing Machinery (ACM)","issue":"1","funder":[{"name":"Hong Kong RGC Projects","award":["12200424 and C2003-23Y"],"award-info":[{"award-number":["12200424 and C2003-23Y"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2026,3,31]]},"abstract":"<jats:p>\n                    Hierarchical directed acyclic graph (DAG) is an essential model for representing terminologies and their hierarchical relationships, such as Disease Ontology and ImageNet categories. Due to the vast number of terminologies and complex structures in a large DAG, it becomes challenging for humans to effectively analyze and explore the hierarchical relationships they encode. Therefore, summarizing hierarchical DAGs is essential for enhancing the interpretability and visualization of the underlying hierarchy. Beyond visual data exploration, hierarchical DAG summarization also supports a range of applications, such as biomedical ontology analytics, snippet generation for information search, and summarized recommendation. In this article, we address a new problem of finding\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    representative vertices to summarize a hierarchical DAG. To capture diverse summarization and identify important vertices, we design a summary score function that reflects vertices diversity coverage and structure correlation. The studied problem is theoretically proven to be NP-hard. To tackle it efficiently, we propose a greedy algorithm with an approximation guarantee that iteratively adds vertices with significant summary contributions to the answers. To further enhance the answer quality, we introduce a subtree extraction-based method that is proven to achieve higher-quality answers. Additionally, we develop a scalable algorithm,\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\mathsf {k}\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    -\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\mathsf {PCGS}\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    , which employs candidate pruning and DAG compression for large-scale hierarchical DAGs. For the query-dependent problem, we propose an index-based method and several optimization techniques to improve efficiency. Extensive experiments on large real-world datasets demonstrate the effectiveness and efficiency of our proposed algorithms.\n                  <\/jats:p>","DOI":"10.1145\/3769079","type":"journal-article","created":{"date-parts":[[2025,9,20]],"date-time":"2025-09-20T11:00:31Z","timestamp":1758366031000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["From Global to Query-Dependent: Summarization of Large Hierarchical DAGs"],"prefix":"10.1145","volume":"51","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0655-8809","authenticated-orcid":false,"given":"Xuliang","family":"Zhu","sequence":"first","affiliation":[{"name":"Antai College of Economics and Management, Shanghai Jiao Tong University","place":["Shanghai, China"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3650-0301","authenticated-orcid":false,"given":"Xin","family":"Huang","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Hong Kong Baptist University","place":["Hong Kong, Hong Kong"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3123-2184","authenticated-orcid":false,"given":"Kai","family":"Wang","sequence":"additional","affiliation":[{"name":"Antai College of Economics and Management, Shanghai Jiao Tong University","place":["Shanghai, China"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9404-5848","authenticated-orcid":false,"given":"Jianliang","family":"Xu","sequence":"additional","affiliation":[{"name":"Computer Science, HKBU","place":["Hong Kong, Hong Kong"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2396-7225","authenticated-orcid":false,"given":"Xuemin","family":"Lin","sequence":"additional","affiliation":[{"name":"Antai College of Economics and Management, Shanghai Jiao Tong University","place":["Shanghai, China"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2026,1,31]]},"reference":[{"key":"e_1_3_1_2_2","article-title":"Submodular functions and perfect graphs","author":"Abrishami Tara","year":"2024","unstructured":"Tara Abrishami, Maria Chudnovsky, Cemil Dibek, and Kristina Vu\u0161kovi\u0107. 2024. Submodular functions and perfect graphs. Mathematics of Operations Research 50, 1 (2025), 189\u2013208.","journal-title":"Mathematics of Operations Research"},{"key":"e_1_3_1_3_2","doi-asserted-by":"publisher","DOI":"10.5555\/3215270.3215272"},{"key":"e_1_3_1_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/1281192.1281197"},{"key":"e_1_3_1_5_2","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.2022.0164"},{"key":"e_1_3_1_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213941"},{"key":"e_1_3_1_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/3340531.3417449"},{"key":"e_1_3_1_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3517858"},{"key":"e_1_3_1_9_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2016.0809"},{"key":"e_1_3_1_10_2","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.2019.0952"},{"key":"e_1_3_1_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/2487259.2487262"},{"key":"e_1_3_1_12_2","doi-asserted-by":"publisher","DOI":"10.14778\/2824032.2824124"},{"key":"e_1_3_1_13_2","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2009.5206848"},{"key":"e_1_3_1_14_2","first-page":"279","article-title":"SNOMED-CT: The advanced terminology and coding system for eHealth","volume":"121","author":"Donnelly Kevin","year":"2006","unstructured":"Kevin Donnelly. 2006. SNOMED-CT: The advanced terminology and coding system for eHealth. Studies in Health Technology and Informatics 121 (2006), 279.","journal-title":"Studies in Health Technology and Informatics"},{"key":"e_1_3_1_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2737783"},{"key":"e_1_3_1_16_2","doi-asserted-by":"publisher","DOI":"10.14778\/2078331.2078338"},{"key":"e_1_3_1_17_2","doi-asserted-by":"publisher","DOI":"10.14778\/2536258.2536263"},{"key":"e_1_3_1_18_2","article-title":"Submodular functions and optimization","author":"Fujishige Satoru","year":"1991","unstructured":"Satoru Fujishige. 1991. Submodular functions and optimization. Annals of Discrete Mathematics (1991).","journal-title":"Annals of Discrete Mathematics"},{"key":"e_1_3_1_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3526147"},{"key":"e_1_3_1_20_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00103"},{"key":"e_1_3_1_21_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2021.1172"},{"key":"e_1_3_1_22_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0140-6736(20)30183-5"},{"key":"e_1_3_1_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/3132847.3133113"},{"key":"e_1_3_1_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3517854"},{"key":"e_1_3_1_25_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2009.68"},{"key":"e_1_3_1_26_2","doi-asserted-by":"publisher","DOI":"10.3414\/ME13-01-0075"},{"key":"e_1_3_1_27_2","first-page":"635","volume-title":"Proceedings of the AMIA Annual Symposium","author":"Jing Xia","year":"2011","unstructured":"Xia Jing and James J. Cimino. 2011. Graphical methods for reducing, visualizing and analyzing large data sets using hierarchical terminologies. In Proceedings of the AMIA Annual Symposium 2011 (2011), 635."},{"key":"e_1_3_1_28_2","volume-title":"Proceedings of the STACS","author":"Karloff Howard","year":"2011","unstructured":"Howard Karloff, Flip Korn, Konstantin Makarychev, and Yuval Rabani. 2011. On parsimonious explanations for 2-D tree-and linearly-ordered data. In Proceedings of the STACS."},{"key":"e_1_3_1_29_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"e_1_3_1_30_2","doi-asserted-by":"crossref","unstructured":"Alexandra Kim Laks V. S. Lakshmanan and Divesh Srivastava. 2020. Summarizing hierarchical multidimensional data. (2020) 877\u2013888.","DOI":"10.1109\/ICDE48307.2020.00081"},{"key":"e_1_3_1_31_2","doi-asserted-by":"publisher","DOI":"10.14778\/3297753.3297755"},{"key":"e_1_3_1_32_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.07.017"},{"key":"e_1_3_1_33_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE53745.2022.00040"},{"key":"e_1_3_1_34_2","doi-asserted-by":"publisher","DOI":"10.1145\/2661829.2661862"},{"key":"e_1_3_1_35_2","unstructured":"Farzaneh Mahdisoltani Joanna Biega and Fabian M. Suchanek. 2013. Yago3: A knowledge base from multilingual wikipedias. In CIDR."},{"key":"e_1_3_1_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/3539597.3570441"},{"key":"e_1_3_1_37_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2019.1889"},{"key":"e_1_3_1_38_2","doi-asserted-by":"publisher","DOI":"10.14778\/1952376.1952377"},{"key":"e_1_3_1_39_2","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2593668"},{"key":"e_1_3_1_40_2","doi-asserted-by":"publisher","DOI":"10.14778\/2350229.2350233"},{"key":"e_1_3_1_41_2","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2610524"},{"key":"e_1_3_1_42_2","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v29i1.9277"},{"key":"e_1_3_1_43_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICCV.1998.710701"},{"key":"e_1_3_1_44_2","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3183745"},{"key":"e_1_3_1_45_2","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/gkr972"},{"key":"e_1_3_1_46_2","doi-asserted-by":"publisher","DOI":"10.1097\/MCG.0b013e318212ae43"},{"key":"e_1_3_1_47_2","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.2022.0384"},{"key":"e_1_3_1_48_2","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319885"},{"key":"e_1_3_1_49_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-018-1300-0"},{"key":"e_1_3_1_50_2","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376675"},{"issue":"4","key":"e_1_3_1_51_2","first-page":"1590","article-title":"Structured robust submodular maximization: Offline and online algorithms","volume":"33","author":"Torrico Alfredo","year":"2021","unstructured":"Alfredo Torrico, Mohit Singh, Sebastian Pokutta, Nika Haghtalab, Joseph Naor, and Nima Anari. 2021. Structured robust submodular maximization: Offline and online algorithms. INFORMS Journal on Computing 33, 4 (2021), 1590\u20131607.","journal-title":"INFORMS Journal on Computing"},{"key":"e_1_3_1_52_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767846"},{"key":"e_1_3_1_53_2","doi-asserted-by":"publisher","DOI":"10.14778\/3067421.3067428"},{"key":"e_1_3_1_54_2","doi-asserted-by":"publisher","DOI":"10.14778\/3402707.3402728"},{"key":"e_1_3_1_55_2","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915216"},{"key":"e_1_3_1_56_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-015-0408-z"},{"key":"e_1_3_1_57_2","doi-asserted-by":"crossref","unstructured":"Xuan Zhao Xike Xie and Christian S. Jensen. 2025. HIGGS: HIerarchy-guided graph stream summarization. In 2025 IEEE 41st International Conference on Data Engineering (ICDE). IEEE 1470\u20131482.","DOI":"10.1109\/ICDE65448.2025.00114"},{"key":"e_1_3_1_58_2","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1000488107"},{"key":"e_1_3_1_59_2","doi-asserted-by":"publisher","DOI":"10.14778\/3447689.3447694"},{"key":"e_1_3_1_60_2","doi-asserted-by":"publisher","DOI":"10.1145\/3340531.3411899"},{"key":"e_1_3_1_61_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2021.3120722"},{"key":"e_1_3_1_62_2","doi-asserted-by":"publisher","DOI":"10.14778\/3415478.3415522"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3769079","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,1,31]],"date-time":"2026-01-31T12:46:04Z","timestamp":1769863564000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3769079"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,1,31]]},"references-count":61,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,3,31]]}},"alternative-id":["10.1145\/3769079"],"URL":"https:\/\/doi.org\/10.1145\/3769079","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,1,31]]},"assertion":[{"value":"2024-09-30","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-08-25","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-01-31","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}