{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,12]],"date-time":"2025-11-12T21:13:17Z","timestamp":1762981997841,"version":"3.44.0"},"reference-count":40,"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":[{"DOI":"10.13039\/501100001821","name":"Vienna Science and Technology Fund","doi-asserted-by":"crossref","award":["10.47379\/ICT2201"],"award-info":[{"award-number":["10.47379\/ICT2201"]}],"id":[{"id":"10.13039\/501100001821","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100020884","name":"ANID","doi-asserted-by":"crossref","award":["ICN17002,1230935"],"award-info":[{"award-number":["ICN17002,1230935"]}],"id":[{"id":"10.13039\/501100020884","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,11,4]]},"abstract":"<jats:p>The set of answers to a query may be very large, potentially overwhelming users when presented with the entire set. In such cases, presenting only a small subset of the answers to the user may be preferable. A natural requirement for this subset is that it should be as diverse as possible to reflect the variety of the entire population. To achieve this, the diversity of a subset is measured using a metric that determines how different two solutions are and a diversity function that extends this metric from pairs to sets. In the past, several studies have shown that finding a diverse subset from an explicitly given set is intractable even for simple metrics (like Hamming distance) and simple diversity functions (like summing all pairwise distances). This complexity barrier becomes even more challenging when trying to output a diverse subset from a set that is only implicitly given (such as the query answers for a given query and a database). Until now, tractable cases have been found only for restricted problems and particular diversity functions.<\/jats:p>\n          <jats:p>\n            To overcome these limitations, we focus in this work on the notion of ultrametrics, which have been widely studied and used in many applications. Starting from any ultrametric\n            <jats:italic toggle=\"yes\">d<\/jats:italic>\n            and a diversity function \u03b4 extending\n            <jats:italic toggle=\"yes\">d<\/jats:italic>\n            , we provide sufficient conditions over \u03b4 for having polynomial-time algorithms to construct diverse answers. To the best of our knowledge, these conditions are satisfied by all the diversity functions considered in the literature. Moreover, we complement these results with lower bounds that show specific cases when these conditions are not satisfied and finding diverse subsets becomes intractable. We conclude by applying these results to the evaluation of conjunctive queries, demonstrating efficient algorithms for finding a diverse subset of solutions for acyclic conjunctive queries when the attribute order is used to measure diversity.\n          <\/jats:p>","DOI":"10.1145\/3695833","type":"journal-article","created":{"date-parts":[[2024,11,7]],"date-time":"2024-11-07T17:26:35Z","timestamp":1731000395000},"page":"1-26","source":"Crossref","is-referenced-by-count":2,"title":["Towards Tractability of the Diversity of Query Answers: Ultrametrics to the Rescue"],"prefix":"10.1145","volume":"2","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 &amp; RelationalAI, Santiago, Chile"}]},{"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"}]}],"member":"320","published-online":{"date-parts":[[2024,11,7]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/578775"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/648256.752884"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3477045"},{"key":"e_1_2_1_4_1","volume-title":"Towards tractability of the diversity of query answers: Ultrametrics to the rescue. CoRR, abs\/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. CoRR, abs\/2408.01657, 2024."},{"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","doi-asserted-by":"publisher","DOI":"10.1145\/3578517"},{"key":"e_1_2_1_8_1","first-page":"331","volume-title":"Proceeding of the 33rd International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR 2010","author":"Demidova E.","year":"2010","unstructured":"E. Demidova, P. Fankhauser, X. Zhou, andW. Nejdl. DivQ: diversification for keyword search over structured databases. In F. Crestani, S. Marchand-Maillet, H. Chen, E. N. Efthimiadis, and J. Savoy, editors, Proceeding of the 33rd International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR 2010, Geneva, Switzerland, July 19--23, 2010, pages 331--338. ACM, 2010."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2602136"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068411000548"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898718348"},{"key":"e_1_2_1_12_1","first-page":"381","volume-title":"Proceedings of the 18th International Conference on World Wide Web, WWW 2009","author":"Gollapudi S.","year":"2009","unstructured":"S. Gollapudi and A. Sharma. An axiomatic approach for result diversification. In J. Quemada, G. Le\u00f3n, Y. S. Maarek, and W. Nejdl, editors, Proceedings of the 18th International Conference on World Wide Web, WWW 2009, Madrid, Spain, April 20--24, 2009, pages 381--390. ACM, 2009."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902309"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings, The Twentieth National Conference on Artificial Intelligence and the Seventeenth Innovative Applications of Artificial Intelligence Conference, July 9--13, 2005","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_15_1","first-page":"106","volume-title":"IJCAI 2007, Proceedings of the 20th International Joint Conference on Artificial Intelligence","author":"Hebrard E.","year":"2007","unstructured":"E. Hebrard, B. O'Sullivan, and T. Walsh. Distance constraints in constraint satisfaction. In M. M. Veloso, editor, IJCAI 2007, Proceedings of the 20th International Joint Conference on Artificial Intelligence, Hyderabad, India, January 6--12, 2007, pages 106--111, 2007."},{"key":"e_1_2_1_16_1","volume-title":"Generalized metrics and uniquely determined logic programs. Theor. Comput. Sci., 305(1- :187--219","author":"Hitzler P.","year":"2003","unstructured":"P. Hitzler and A. K. Seda. Generalized metrics and uniquely determined logic programs. Theor. Comput. Sci., 305(1- :187--219, 2003."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v34i02.5512"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-022-00770-0"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1134\/S0081543811070017"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-02-06605-4"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687663"},{"key":"e_1_2_1_22_1","first-page":"1","volume-title":"26th International Conference on Database Theory, ICDT 2023, March 28--31","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_23_1","volume-title":"Diversity of answers to conjunctive queries. CoRR, abs\/2301.08848","author":"Merkl T. C.","year":"2023","unstructured":"T. C. Merkl, R. Pichler, and S. Skritek. Diversity of answers to conjunctive queries. CoRR, abs\/2301.08848, 2023."},{"issue":"3","key":"e_1_2_1_24_1","first-page":"207","article-title":"Ultrametric model of mind, ii: Application to text content analysis. p-Adic Numbers","volume":"4","author":"Murtagh F.","year":"2012","unstructured":"F. Murtagh. Ultrametric model of mind, ii: Application to text content analysis. p-Adic Numbers, Ultrametric Analysis and Applications, 4(3):207--221, 2012.","journal-title":"Ultrametric Analysis and Applications"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-022-00740-6"},{"key":"e_1_2_1_26_1","first-page":"260","volume-title":"Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI","author":"Petit T.","year":"2015","unstructured":"T. Petit and A. C. Trapp. Finding diverse solutions of high quality to constraint optimization problems. In Q. Yang and M. J. Wooldridge, editors, Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI 2015, Buenos Aires, Argentina, July 25--31, 2015, pages 260--267. AAAI Press, 2015."},{"key":"e_1_2_1_27_1","first-page":"881","volume-title":"Proceedings of the 19th International Conference on World Wide Web, WWW 2010","author":"Santos R. L. T.","year":"2010","unstructured":"R. L. T. Santos, C. Macdonald, and I. Ounis. Exploiting query reformulations for web search result diversification. In M. Rappa, P. Jones, J. Freire, and S. Chakrabarti, editors, Proceedings of the 19th International Conference on World Wide Web, WWW 2010, Raleigh, North Carolina, USA, April 26--30, 2010, pages 881--890. ACM, 2010."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1561\/1500000040"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/3032027.3032113"},{"key":"e_1_2_1_30_1","first-page":"1","volume-title":"Handbook of Applied Algorithms: Solving Scientific, Engineering and Practical Problems","author":"Simovici D. A.","year":"2007","unstructured":"D. A. Simovici. Data mining algorithms i: Clustering. In A. Nayak and I. Stojmenovic, editors, Handbook of Applied Algorithms: Solving Scientific, Engineering and Practical Problems, pages 10:1--10:19. Wiley-IEEE Press, 2007."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3534678.3539459"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564715"},{"issue":"4","key":"e_1_2_1_33_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_34_1","volume-title":"Proceedings of the 24th International Conference on Data Engineering, ICDE 2008, April 7--12, 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_35_1","doi-asserted-by":"publisher","DOI":"10.14778\/3402755.3402779"},{"key":"e_1_2_1_36_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."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2024.3382262"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/s40745-015-0040-1"},{"key":"e_1_2_1_39_1","volume-title":"7th International Conference, September 9--11, 1981","author":"Yannakakis M.","year":"1981","unstructured":"M. Yannakakis. Algorithms for acyclic database schemes. In Very Large Data Bases, 7th International Conference, September 9--11, 1981, Cannes, France, Proceedings, pages 82--94. IEEE Computer Society, 1981."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-016-0990-4"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3695833","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3695833","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,23]],"date-time":"2025-08-23T02:35:00Z","timestamp":1755916500000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3695833"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,11,4]]},"references-count":40,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2024,11,4]]}},"alternative-id":["10.1145\/3695833"],"URL":"https:\/\/doi.org\/10.1145\/3695833","relation":{},"ISSN":["2836-6573"],"issn-type":[{"type":"electronic","value":"2836-6573"}],"subject":[],"published":{"date-parts":[[2024,11,4]]}}}