{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T09:36:12Z","timestamp":1774949772030,"version":"3.50.1"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","issue":"14","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2013,9]]},"abstract":"<jats:p>\n            Keyword search has been popularly used to query graph data. Due to the lack of structure support, a keyword query might generate an excessive number of matches, referred to as \"answer graphs\", that could include different relationships among keywords. An ignored yet important task is to group and summarize answer graphs that share similar structures and contents for better query interpretation and result understanding. This paper studies the summarization problem for the answer graphs induced by a keyword query\n            <jats:italic>Q<\/jats:italic>\n            . (1) A notion of summary graph is proposed to characterize the summarization of answer graphs. Given\n            <jats:italic>Q<\/jats:italic>\n            and a set of answer graphs G, a summary graph preserves the relation of the keywords in\n            <jats:italic>Q<\/jats:italic>\n            by summarizing the paths connecting the keywords nodes in G. (2) A quality metric of summary graphs, called coverage ratio, is developed to measure information loss of summarization. (3) Based on the metric, a set of summarization problems are formulated, which aim to find minimized summary graphs with certain coverage ratio. (a) We show that the complexity of these summarization problems ranges from ptime to NP-complete. (b) We provide exact and heuristic summarization algorithms. (4) Using real-life and synthetic graphs, we experimentally verify the effectiveness and the efficiency of our techniques.\n          <\/jats:p>","DOI":"10.14778\/2556549.2556561","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"1774-1785","source":"Crossref","is-referenced-by-count":29,"title":["Summarizing answer graphs induced by keyword queries"],"prefix":"10.14778","volume":"6","author":[{"given":"Yinghui","family":"Wu","sequence":"first","affiliation":[{"name":"University of California Santa Barbara"}]},{"given":"Shengqi","family":"Yang","sequence":"additional","affiliation":[{"name":"University of California Santa Barbara"}]},{"given":"Mudhakar","family":"Srivatsa","sequence":"additional","affiliation":[{"name":"IBM Research"}]},{"given":"Arun","family":"Iyengar","sequence":"additional","affiliation":[{"name":"IBM Research"}]},{"given":"Xifeng","family":"Yan","sequence":"additional","affiliation":[{"name":"University of California Santa Barbara"}]}],"member":"320","published-online":{"date-parts":[[2013,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-6045-0_9"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/635499.635502"},{"issue":"1","key":"e_1_2_1_3_1","first-page":"3","article-title":"Enhancing search with structure","volume":"33","author":"Chakrabarti S.","year":"2010","unstructured":"S. Chakrabarti, S. Sarawagi, and S. Sudarshan. Enhancing search with structure. IEEE Data Eng. Bull., 33(1):3-24, 2010.","journal-title":"IEEE Data Eng. Bull."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/301250.301257"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559966"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767843"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989420"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.14778\/2078331.2078339"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/2063016.2063030"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/578533"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1027328830731"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.3115\/1117575.1117580"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872762"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247480.1247516"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/795662.796255"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376651"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/1083592.1083652"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/876875.879023"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1516360.1516406"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376706"},{"issue":"1","key":"e_1_2_1_21_1","first-page":"46","article-title":"Query results ready, now what?","volume":"33","author":"Liu Z.","year":"2010","unstructured":"Z. Liu and Y. Chen. Query results ready, now what? IEEE Data Eng. Bull., 33(1):46-53, 2010.","journal-title":"IEEE Data Eng. Bull."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1735886.1735889"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/1978665.1978667"},{"key":"e_1_2_1_24_1","volume-title":"Multivariate analysis","author":"Mardia K. V.","year":"1980","unstructured":"K. V. Mardia, J. T. Kent, and J. M. Bibby. Multivariate analysis. 1980."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/645503.656266"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376661"},{"key":"e_1_2_1_27_1","volume-title":"WWW","author":"Parthasarathy K.","year":"2011","unstructured":"K. Parthasarathy, S. Kumar, and D. Damien. Algorithm for answer graph construction for keyword queries on rdf data. In WWW, 2011."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-00958-7_63"},{"issue":"4","key":"e_1_2_1_29_1","first-page":"379","article-title":"Complexity of decomposing graphs into factors with given diameters or radii","volume":"32","author":"Plesn\u00edk J.","year":"1982","unstructured":"J. Plesn\u00edk. Complexity of decomposing graphs into factors with given diameters or radii. Mathematica Slovaca, 32(4):379-388, 1982.","journal-title":"Mathematica Slovaca"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687642"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/WI-IAT.2011.70"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/IMCSIT.2010.5679746"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376705"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376675"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.119"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","unstructured":"V. V. Vazirani. Approximation Algorithms. Springer 2003.","DOI":"10.5555\/500776"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-6045-0_8"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2010.5447830"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2556549.2556561","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,23]],"date-time":"2024-10-23T22:34:50Z","timestamp":1729722890000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2556549.2556561"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,9]]},"references-count":38,"journal-issue":{"issue":"14","published-print":{"date-parts":[[2013,9]]}},"alternative-id":["10.14778\/2556549.2556561"],"URL":"https:\/\/doi.org\/10.14778\/2556549.2556561","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2013,9]]}}}