{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,12]],"date-time":"2025-11-12T16:10:35Z","timestamp":1762963835537,"version":"3.45.0"},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","issue":"5","funder":[{"DOI":"10.13039\/501100001821","name":"Vienna Science and Technology Fund","doi-asserted-by":"crossref","award":["10.47379\/ICT2201, 10.47379\/VRG18013, 10.47379\/NXT22018"],"award-info":[{"award-number":["10.47379\/ICT2201, 10.47379\/VRG18013, 10.47379\/NXT22018"]}],"id":[{"id":"10.13039\/501100001821","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100019783","name":"National Agency for Research and Development","doi-asserted-by":"crossref","award":["ICN17_002, 1230935"],"award-info":[{"award-number":["ICN17_002, 1230935"]}],"id":[{"id":"10.13039\/100019783","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2025,11,10]]},"abstract":"<jats:p>When query evaluation produces too many tuples, a new approach in query answering is to retrieve a diverse subset of them. The standard approach for measuring the diversity of a set of tuples is to use a distance function between tuples, which measures the dissimilarity between them, to then aggregate the pairwise distances of the set into a score (e.g., by using sum or min aggregation). However, as we will point out in this work, the resulting diversity measures may display some unintuitive behavior. Moreover, even in very simple settings, finding a maximally diverse subset of the answers of fixed size is, in general, intractable and little is known about approximations apart from some hand-picked distance-aggregator pairs.<\/jats:p>\n                  <jats:p>In this work, we introduce a novel approach for computing the diversity of tuples based on volume instead of distance. We present a framework for defining volume-based diversity functions and provide several examples of these measures applied to relational data. Although query answering of conjunctive queries (CQ) under this setting is intractable in general, we show that one can always compute a (1-1\/e)-approximation for any volume-based diversity function. Furthermore, in terms of combined complexity, we connect the evaluation of CQs under volume-based diversity functions with the ranked enumeration of solutions, finding general conditions under which a (1-1\/e)-approximation can be computed in polynomial time.<\/jats:p>","DOI":"10.1145\/3767717","type":"journal-article","created":{"date-parts":[[2025,11,12]],"date-time":"2025-11-12T15:06:02Z","timestamp":1762959962000},"page":"1-18","source":"Crossref","is-referenced-by-count":0,"title":["Query Answering Under Volume-Based Diversity Functions"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3678-1868","authenticated-orcid":false,"given":"Marcelo","family":"Arenas","sequence":"first","affiliation":[{"name":"Pontificia Universidad Cat\u00f3lica de Chile, Santiago, Chile, IMFD, Santiago, Chile, and RelationalAI, Berkeley, USA"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-7206-2518","authenticated-orcid":false,"given":"Timo Camillo","family":"Merkl","sequence":"additional","affiliation":[{"name":"TU Wien, Vienna, Austria"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1760-122X","authenticated-orcid":false,"given":"Reinhard","family":"Pichler","sequence":"additional","affiliation":[{"name":"TU Wien, Vienna, Austria"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0832-116X","authenticated-orcid":false,"given":"Cristian","family":"Riveros","sequence":"additional","affiliation":[{"name":"Pontificia Universidad Cat\u00f3lica de Chile, Santiago, Chile and IMFD, Santiago, Chile"}]}],"member":"320","published-online":{"date-parts":[[2025,11,12]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3695835"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3695833"},{"key":"e_1_2_1_3_1","volume-title":"Query answering under volume-based diversity functions. CoRR, abs\/2509.11929","author":"Arenas M.","year":"2025","unstructured":"M. Arenas, T. C. Merkl, R. Pichler, and C. Riveros. Query answering under volume-based diversity functions. CoRR, abs\/2509.11929, 2025."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-33143-6"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-74915-8_18"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2021.103644"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 9th Annual ACM Symposium on Theory of Computing","author":"Chandra A. K.","year":"1977","unstructured":"A. K. Chandra and P. M. Merlin. Optimal implementation of conjunctive queries in relational data bases. In J. E. Hopcroft, E. P. Friedman, and M. A. Harrison, editors, Proceedings of the 9th Annual ACM Symposium on Theory of Computing, May 4-6, 1977, Boulder, Colorado, USA, pages 77-90. ACM, 1977."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-002-0083-8"},{"key":"e_1_2_1_9_1","first-page":"21","article-title":"Ranked enumeration of conjunctive query results","author":"Deep S.","year":"2025","unstructured":"S. Deep and P. Koutris. Ranked enumeration of conjunctive query results. Logical Methods in Computer Science, 21, 2025.","journal-title":"Logical Methods in Computer Science"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285059"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2636918"},{"key":"e_1_2_1_12_1","volume-title":"Proceedings, The Twentieth National Conference on Artificial Intelligence and the Seventeenth Innovative Applications of Artificial Intelligence Conference","author":"Hebrard E.","year":"2005","unstructured":"E. Hebrard, B. Hnich, B. O'Sullivan, and T. Walsh. Finding diverse and similar solutions in constraint programming. In M. M. Veloso and S. Kambhampati, editors, Proceedings, The Twentieth National Conference on Artificial Intelligence and the Seventeenth Innovative Applications of Artificial Intelligence Conference, July 9-13, 2005, Pittsburgh, Pennsylvania, USA, pages 372-377. AAAI Press \/ The MIT Press, 2005."},{"key":"e_1_2_1_13_1","first-page":"203","volume-title":"Proceedings of the ACM SIGMOD International Conference on Management of Data","author":"Ilyas I. F.","year":"2004","unstructured":"I. F. Ilyas, R. Shah, W. G. Aref, J. S. Vitter, and A. K. Elmagarmid. Rank-aware query optimization. In G. Weikum, A. C. K\u00f6nig, and S. De\u00dfloch, editors, Proceedings of the ACM SIGMOD International Conference on Management of Data, Paris, France, June 13-18, 2004, pages 203-214. ACM, 2004."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v34i02.5512"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-022-00770-0"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902280"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1713"},{"key":"e_1_2_1_18_1","first-page":"131","volume-title":"Proceedings of the ACM SIGMOD International Conference on Management of Data","author":"Li C.","year":"2005","unstructured":"C. Li, K. C. Chang, I. F. Ilyas, and S. Song. Ranksql: Query algebra and optimization for relational top-k queries. In F. \u00d6zcan, editor, Proceedings of the ACM SIGMOD International Conference on Management of Data, Baltimore, Maryland, USA, June 14-16, 2005, pages 131-142. ACM, 2005."},{"key":"e_1_2_1_19_1","first-page":"1342","volume-title":"Proceedings of the 31st International Conference on Very Large Data Bases","author":"Li C.","year":"2005","unstructured":"C. Li, M. A. Soliman, K. C. Chang, and I. F. Ilyas. Ranksql: Supporting ranking queries in relational database management systems. In K. B\u00f6hm, C. S. Jensen, L. M. Haas, M. L. Kersten, P. Larson, and B. C. Ooi, editors, Proceedings of the 31st International Conference on Very Large Data Bases, Trondheim, Norway, August 30 - September 2, 2005, pages 1342-1345. ACM, 2005."},{"key":"e_1_2_1_20_1","first-page":"1","volume-title":"26th International Conference on Database Theory, ICDT 2023","volume":"255","author":"Merkl T. C.","year":"2023","unstructured":"T. C. Merkl, R. Pichler, and S. Skritek. Diversity of answers to conjunctive queries. In F. Geerts and B. Vandevoort, editors, 26th International Conference on Database Theory, ICDT 2023, March 28-31, 2023, Ioannina, Greece, volume 255 of LIPIcs, pages 10:1-10:19. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 2023."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1111\/1468-0262.00321"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01588971"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-022-00740-6"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2013.01.012"},{"issue":"4","key":"e_1_2_1_25_1","first-page":"57","article-title":"Efficient computation of diverse query results","volume":"32","author":"Vee E.","year":"2009","unstructured":"E. Vee, J. Shanmugasundaram, and S. Amer-Yahia. Efficient computation of diverse query results. IEEE Data Eng. Bull., 32(4):57-64, 2009.","journal-title":"IEEE Data Eng. Bull."},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the 24th International Conference on Data Engineering, ICDE 2008","author":"Vee E.","year":"2008","unstructured":"E. Vee, U. Srivastava, J. Shanmugasundaram, P. Bhat, and S. Amer-Yahia. Efficient computation of diverse query results. In G. Alonso, J. A. Blakeley, and A. L. P. Chen, editors, Proceedings of the 24th International Conference on Data Engineering, ICDE 2008, April 7-12, 2008, Canc\u00fan, Mexico, pages 228-236. IEEE Computer Society, 2008."},{"key":"e_1_2_1_27_1","volume-title":"On diversity. The quarterly journal of economics, 107(2):363-405","author":"Weitzman M. L.","year":"1992","unstructured":"M. L. Weitzman. On diversity. The quarterly journal of economics, 107(2):363-405, 1992."}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3767717","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,12]],"date-time":"2025-11-12T16:08:42Z","timestamp":1762963722000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3767717"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,11,10]]},"references-count":27,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2025,11,10]]}},"alternative-id":["10.1145\/3767717"],"URL":"https:\/\/doi.org\/10.1145\/3767717","relation":{},"ISSN":["2836-6573"],"issn-type":[{"type":"electronic","value":"2836-6573"}],"subject":[],"published":{"date-parts":[[2025,11,10]]}}}