{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,15]],"date-time":"2026-05-15T01:15:33Z","timestamp":1778807733155,"version":"3.51.4"},"reference-count":67,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2024,11,4]],"date-time":"2024-11-04T00:00:00Z","timestamp":1730678400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"US-Israel Binational Science Foundation Grant","award":["2022131"],"award-info":[{"award-number":["2022131"]}]},{"name":"NSF","award":["CCF-2223870, IIS-2402823, IIS-2348919"],"award-info":[{"award-number":["CCF-2223870, IIS-2402823, IIS-2348919"]}]},{"name":"NSERC Discovery Grant"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,11,4]]},"abstract":"<jats:p>\n            Data summarization is a powerful approach to deal with large-scale data analytics, which has wide applications in web search, recommendation systems, approximate query processing, etc. It computes a small, compact summary that preserves vital properties of the original data. In this paper, we study the data summarization problem of conjunctive query results, i.e., computing a k-size subset of a conjunctive query output, for any given k&gt;0, that optimizes a certain objective. More specifically, we are interested in two commonly studied objectives: cohesion, which measures the maximum distance between a tuple in the query result tuples and its closest tuple in the summary (k-center clustering); and diversity, which measures the pairwise distances between the summary items. A simple approach that computes the entire query output and then applies existing algorithms on top of these materialized tuples suffers from high computational complexity because the query output can be large, e.g., for a relational database of N tuples, the number of result tuples can be N\n            <jats:sup>O(1).<\/jats:sup>\n            We propose O(1)-approximation algorithms that compute well-representative summaries of size k in time O(N*k\n            <jats:sup>O(1)<\/jats:sup>\n            ), or even O(N+ k\n            <jats:sup>O(1)<\/jats:sup>\n            ) in some cases, without computing all result tuples. We also propose the first efficient (2+\\eps)-approximation algorithm for the k-center clustering problem over relational data. Our main idea is to formulate a few oracles that enable us to access specific query result tuples with certain properties, to show how these oracles can be implemented efficiently, and to compute desired summaries with few invocations of these oracles.\n          <\/jats:p>","DOI":"10.1145\/3695835","type":"journal-article","created":{"date-parts":[[2024,11,7]],"date-time":"2024-11-07T17:26:35Z","timestamp":1731000395000},"page":"1-27","source":"Crossref","is-referenced-by-count":7,"title":["Computing A Well-Representative Summary of Conjunctive Query Results"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9439-181X","authenticated-orcid":false,"given":"Pankaj K.","family":"Agarwal","sequence":"first","affiliation":[{"name":"Department of Computer Science, Duke University, Durham, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-3798-9578","authenticated-orcid":false,"given":"Aryan","family":"Esmailpour","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Illinois Chicago, Chicago, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7890-665X","authenticated-orcid":false,"given":"Xiao","family":"Hu","sequence":"additional","affiliation":[{"name":"Cheriton School of Computer Science, University of Waterloo, Waterloo, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2114-8886","authenticated-orcid":false,"given":"Stavros","family":"Sintos","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Illinois Chicago, Chicago, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0604-6790","authenticated-orcid":false,"given":"Jun","family":"Yang","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Duke University, Durham, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,11,7]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"https:\/\/db-engines.com\/en\/ranking_categories."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487575.2487636"},{"key":"e_1_2_1_3_1","first-page":"1","volume-title":"Proceedings of the 33rd International Symposium on Computational Geometry","author":"Abrahamsen M.","year":"2017","unstructured":"M. Abrahamsen, M. de Berg, K. Buchin, M. Mehr, and A. D. Mehrabi. Range-clustering queries. In Proceedings of the 33rd International Symposium on Computational Geometry, pages 5:1--5:16, 2017."},{"key":"e_1_2_1_4_1","first-page":"1","volume-title":"Range-clustering queries 25th International Conference on Database Theory","author":"Addanki R.","year":"2022","unstructured":"R. Addanki, A. McGregor, A. Meliou, and Z. Moumoulidou. Improved approximation and scalability for fair max-min diversification. In Range-clustering queries 25th International Conference on Database Theory, pages 7:1--7:21, 2022."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2500128"},{"key":"e_1_2_1_6_1","volume-title":"Robust shape fitting via peeling and grating coresets. Discrete & Computational Geometry, 39(1--3):38--58","author":"Agarwal P. K.","year":"2008","unstructured":"P. K. Agarwal, S. Har-Peled, and H. Yu. Robust shape fitting via peeling and grating coresets. Discrete & Computational Geometry, 39(1--3):38--58, 2008."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(92)90001-9"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/453\/08794"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0110-y"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/B978-044482537-7\/50003-6"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3375395.3387667"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2465351.2465355"},{"key":"e_1_2_1_13_1","volume-title":"Towards tractability of the diversity of query answers: Ultrametrics to the rescue. arXiv preprint arXiv:2408.01657","author":"Arenas M.","year":"2024","unstructured":"M. Arenas, T. C. Merkl, R. Pichler, and C. Riveros. Towards tractability of the diversity of query answers: Ultrametrics to the rescue. arXiv preprint arXiv:2408.01657, 2024."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/110859440"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-74915-8_18"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2402.322389"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-9142-2"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213556.2213580"},{"key":"e_1_2_1_19_1","volume-title":"EPFL","author":"Cevallos A.","year":"2016","unstructured":"A. Cevallos. Approximation algorithms for geometric dispersion. Technical report, EPFL, 2016."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.9"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2018.0982"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/336154.336216"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1242524.1242526"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/304181.304206"},{"key":"e_1_2_1_25_1","first-page":"434","article-title":"Coresets for relational data and the applications","volume":"35","author":"Chen J.","year":"2022","unstructured":"J. Chen, Q. Yang, R. Huang, and H. Ding. Coresets for relational data and the applications. Advances in Neural Information Processing Systems, 35:434--448, 2022.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_2_1_26_1","first-page":"1","volume-title":"Proceedings of the 23rd International Conference on Database Theory","author":"Chen Y.","year":"2020","unstructured":"Y. Chen and K. Yi. Random sampling and size estimation over cyclic joins. In Proceedings of the 23rd International Conference on Database Theory, pages 7:1--7:18, 2020."},{"key":"e_1_2_1_27_1","first-page":"15","volume-title":"Sketch techniques for approximate query processing. Foundations and Trends in Databases","author":"Cormode G.","year":"2011","unstructured":"G. Cormode. Sketch techniques for approximate query processing. Foundations and Trends in Databases. NOW publishers, page 15, 2011."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3080008"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1561\/9781601985170"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1017\/9781108769938"},{"key":"e_1_2_1_31_1","first-page":"2742","volume-title":"Proceedings of the International Conference on Artificial Intelligence and Statistics","author":"Curtin R.","year":"2020","unstructured":"R. Curtin, B. Moseley, H. Ngo, X. Nguyen, D. Olteanu, and M. Schleich. Rk-means: Fast clustering for relational data. In Proceedings of the International Conference on Artificial Intelligence and Statistics, pages 2742--2752, 2020."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.14778\/3510397.3510401"},{"key":"e_1_2_1_33_1","first-page":"1","volume-title":"Proceedings of the 24th International Conference on Database Theory","author":"Deep S.","year":"2021","unstructured":"S. Deep and P. Koutris. Ranked enumeration of conjunctive query results. In Proceedings of the 24th International Conference on Database Theory, pages 5:1--5:19, 2021."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3584372.3588666"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1990-0974513-6"},{"key":"e_1_2_1_36_1","volume-title":"Proceedings of the ACM on Management of Data, 2(5)","author":"Esmailpour A.","year":"2025","unstructured":"A. Esmailpour and S. Sintos. Improved approximation algorithms for relational clustering. Proceedings of the ACM on Management of Data, 2(5), 2025."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2402.322390"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62255"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564746"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/276304.276334"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(85)90224-5"},{"key":"e_1_2_1_42_1","volume-title":"Treewidth and hypertree width. Tractability: Practical Approaches to Hard Problems, 1","author":"Gottlob G.","year":"2014","unstructured":"G. Gottlob, G. Greco, and F. Scarcello. Treewidth and hypertree width. Tractability: Practical Approaches to Hard Problems, 1, 2014."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-016-9801-7"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/2831230"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(97)00034-5"},{"key":"e_1_2_1_46_1","first-page":"1","volume-title":"Proceedings of the 27th International Conference on Database Theory","author":"Hu X.","year":"2024","unstructured":"X. Hu and S. Sintos. Finding smallest witnesses for conjunctive queries. In Proceedings of the 27th International Conference on Database Theory, pages 24:1--24:20, 2024."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1016\/B978-012722442-8\/50011-2"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.5555\/645924.671191"},{"key":"e_1_2_1_49_1","first-page":"4940","volume-title":"Proceedings of the International Conference on Machine Learning","author":"Jones M.","year":"2020","unstructured":"M. Jones, H. Nguyen, and T. Nguyen. Fair k-centers via maximum matching. In Proceedings of the International Conference on Machine Learning, pages 4940--4949, 2020."},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/3584372.3588676"},{"key":"e_1_2_1_51_1","first-page":"3448","volume-title":"International Conference on Machine Learning","author":"Kleindessner M.","year":"2019","unstructured":"M. Kleindessner, P. Awasthi, and J. Morgenstern. Fair k-center clustering for data summarization. In International Conference on Machine Learning, pages 3448--3457. PMLR, 2019."},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/3654940"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457277"},{"key":"e_1_2_1_54_1","first-page":"1","volume-title":"Proceedings of the 26th International Conference on Database Theory","author":"Merkl T. C.","year":"2023","unstructured":"T. C. Merkl, R. Pichler, and S. Skritek. Diversity of answers to conjunctive queries. In Proceedings of the 26th International Conference on Database Theory, pages 10:1--10:19, 2023."},{"key":"e_1_2_1_55_1","first-page":"1","volume-title":"Proceedings of the 48th International Colloquium on Automata, Languages, and Programming","author":"Moseley B.","year":"2021","unstructured":"B. Moseley, K. Pruhs, A. Samadian, and Y. Wang. Relational algorithms for k-means clustering. In Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, pages 97:1--97:21, 2021."},{"key":"e_1_2_1_56_1","first-page":"1","volume-title":"Proceedings of the 24th International Conference on Database Theory","author":"Moumoulidou Z.","year":"2021","unstructured":"Z. Moumoulidou, A. McGregor, and A. Meliou. Diverse data selection under fairness constraints. In Proceedings of the 24th International Conference on Database Theory, pages 13:1--13:25, 2021."},{"key":"e_1_2_1_57_1","first-page":"1","volume-title":"Proceedings of the 34th International Symposium on Computational Geometry","author":"Oh E.","year":"2018","unstructured":"E. Oh and H.-K. Ahn. Approximate range queries for clustering. In Proceedings of the 34th International Symposium on Computational Geometry, pages 62:1--62:14, 2018."},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/2274576.2274607"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.42.2.299"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(89)90166-X"},{"key":"e_1_2_1_61_1","first-page":"724","volume-title":"Annals of Mathematics","author":"Schoenberg I. J.","year":"1935","unstructured":"I. J. Schoenberg. Remarks to Maurice Frechet's article'sur la definition axiomatique d'une classe d'espace distances vectoriellement applicable sur l'espace de hilbert. Annals of Mathematics, pages 724--732, 1935."},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.2307\/1968466"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1938-1501980-0"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1137\/0404048"},{"key":"e_1_2_1_65_1","first-page":"82","volume-title":"Proceedings of the 7th International Conference on Very Large Data Bases","volume":"81","author":"Yannakakis M.","year":"1981","unstructured":"M. Yannakakis. Algorithms for acyclic database schemes. In Proceedings of the 7th International Conference on Very Large Data Bases, volume 81, pages 82--94, 1981."},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3183739"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389717"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3695835","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3695835","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,23]],"date-time":"2025-08-23T02:30:34Z","timestamp":1755916234000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3695835"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,11,4]]},"references-count":67,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2024,11,4]]}},"alternative-id":["10.1145\/3695835"],"URL":"https:\/\/doi.org\/10.1145\/3695835","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,11,4]]}}}