{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,18]],"date-time":"2026-08-18T01:42:53Z","timestamp":1787017373478,"version":"build-2736575974"},"reference-count":49,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2024,5,29]],"date-time":"2024-05-29T00:00:00Z","timestamp":1716940800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100006374","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["2121\/22"],"award-info":[{"award-number":["2121\/22"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Frankel Center for Computer Science, BGU"},{"DOI":"10.13039\/501100006374","name":"National Science Foundation","doi-asserted-by":"publisher","award":["2326193, 2312930"],"award-info":[{"award-number":["2326193, 2312930"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,5,29]]},"abstract":"<jats:p>Database queries are often used to select and rank items as decision support for many applications. As automated decision-making tools become more prevalent, there is a growing recognition of the need to diversify their outcomes. In this paper, we define and study the problem of modifying the selection conditions of an ORDER BY query so that the result of the modified query closely fits some user-defined notion of diversity while simultaneously maintaining the intent of the original query. We show the hardness of this problem and propose a mixed-integer linear programming (MILP) based solution. We further present optimizations designed to enhance the scalability and applicability of the solution in real-life scenarios. We investigate the performance characteristics of our algorithm and show its efficiency and the usefulness of our optimizations.<\/jats:p>","DOI":"10.1145\/3654969","type":"journal-article","created":{"date-parts":[[2024,5,30]],"date-time":"2024-05-30T09:44:53Z","timestamp":1717062293000},"page":"1-27","source":"Crossref","is-referenced-by-count":5,"title":["Query Refinement for Diverse Top-k Selection"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3888-1491","authenticated-orcid":false,"given":"Felix S.","family":"Campbell","sequence":"first","affiliation":[{"name":"Ben-Gurion University of the Negev, Be'er Sheva, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-7591-1267","authenticated-orcid":false,"given":"Alon","family":"Silberstein","sequence":"additional","affiliation":[{"name":"Ben-Gurion University of the Negev, Be'er Sheva, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1587-0450","authenticated-orcid":false,"given":"Julia","family":"Stoyanovich","sequence":"additional","affiliation":[{"name":"New York University, New York, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0325-7392","authenticated-orcid":false,"given":"Yuval","family":"Moskovitch","sequence":"additional","affiliation":[{"name":"Ben-Gurion University of the Negev, Be'er Sheva, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,5,30]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3300079"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3209581"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2016.7498289"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2658840.2658843"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-017-0483--4"},{"key":"e_1_2_2_6_1","volume-title":"PackageBuilder: From Tuples to Packages. CoRR abs\/1507.00942","author":"Brucato Matteo","year":"2015","unstructured":"Matteo Brucato, Rahul Ramakrishna, Azza Abouzied, and Alexandra Meliou. 2015. PackageBuilder: From Tuples to Packages. CoRR abs\/1507.00942 (2015). arXiv:1507.00942 http:\/\/arxiv.org\/abs\/1507.00942"},{"key":"e_1_2_2_7_1","doi-asserted-by":"crossref","unstructured":"Felix S. Campbell Alon Silberstein Julia Stoyanovich and Yuval Moskovitch. 2024. Query Refinement for Diverse Top-?? Selection (Implementation). https:\/\/github.com\/fsalc\/diverse-top-k","DOI":"10.1145\/3654969"},{"key":"e_1_2_2_8_1","doi-asserted-by":"crossref","unstructured":"Felix S. Campbell Alon Silberstein Julia Stoyanovich and Yuval Moskovitch. 2024. Query Refinement for Diverse Top-?? Selection (Tech Report). arXiv:2403.17786 [cs.DB]","DOI":"10.1145\/3654969"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3351095.3372858"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2018.28"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1002\/nav.3800090303"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.14778\/3598581.3598606"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.317704"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2602136"},{"key":"e_1_2_2_15_1","volume-title":"Caravan: Provisioning for What-If Analysis. In Sixth Biennial Conference on Innovative Data Systems Research, CIDR","author":"Deutch Daniel","year":"2013","unstructured":"Daniel Deutch, Zachary G. Ives, Tova Milo, and Val Tannen. 2013. Caravan: Provisioning for What-If Analysis. In Sixth Biennial Conference on Innovative Data Systems Research, CIDR 2013, Asilomar, CA, USA, January 6--9, 2013, Online Proceedings. www.cidrdb.org. http:\/\/cidrdb.org\/cidr2013\/Papers\/CIDR13_Paper100.pdf"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732279.2732283"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480102412856"},{"key":"e_1_2_2_18_1","doi-asserted-by":"crossref","unstructured":"Sahin Cem Geyik Stuart Ambler and Krishnaram Kenthapadi. 2019. Fairness-Aware Ranking in Search & Recommendation Systems with Application to LinkedIn Talent Search. In SIGKDD. ACM.","DOI":"10.1145\/3292500.3330691"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1526709.1526761"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.14778\/3565816.3565832"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1093\/biomet\/30.1-2.81"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2018.33"},{"key":"e_1_2_2_24_1","unstructured":"Nick Koudas Chen Li Anthony K. H. Tung and Rares Vernica. 2006. Relaxing Join and Selection Queries. In VLDB."},{"key":"e_1_2_2_25_1","volume-title":"Counterfactual Fairness. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017","author":"Kusner Matt J.","year":"2017","unstructured":"Matt J. Kusner, Joshua R. Loftus, Chris Russell, and Ricardo Silva. 2017. Counterfactual Fairness. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4--9, 2017, Long Beach, CA, USA, Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett (Eds.). 4066--4076. https:\/\/proceedings.neurips.cc\/paper\/2017\/hash\/a486cd07e4ac3d270571622f4f316ec5-Abstract.html"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.14778\/3626292.3626295"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.14778\/3611540.3611623"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2307.02860"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213875"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1516360.1516459"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3530800.3534528"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3530800.3534528"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","unstructured":"Yuval Moskovitch Jinyang Li and H. V. Jagadish. 2023. Detection of Groups with Biased Representation in Ranking. CoRR abs\/2301.00719 (2023). https:\/\/doi.org\/10.48550\/arXiv.2301.00719 arXiv:2301.00719","DOI":"10.48550\/arXiv.2301.00719"},{"key":"e_1_2_2_34_1","unstructured":"Ion Muslea and Thomas J Lee. 2005. Online query relaxation via bayesian causal structures discovery. In AAAI. 831--836."},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/DSAA.2016.49"},{"key":"e_1_2_2_36_1","volume-title":"Effectiveness of medical school admissions criteria in predicting residency ranking four years later. Medical education 41, 1","author":"Peskun Christopher","year":"2007","unstructured":"Christopher Peskun, Allan Detsky, and Maureen Shandling. 2007. Effectiveness of medical school admissions criteria in predicting residency ranking four years later. Medical education 41, 1 (2007)."},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3320212"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE53745.2022.00111"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.5441\/002\/edbt.2018.22"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807172"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559902"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3035925"},{"key":"e_1_2_2_44_1","unstructured":"Linda F Wightman. 1998. LSAC National Longitudinal Bar Passage Study. LSAC Research Report Series. (1998)."},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2019\/836"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3085504.3085526"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-019-00658--8"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/3533379"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/3533380"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3654969","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3654969","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,21]],"date-time":"2025-08-21T14:41:26Z","timestamp":1755787286000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3654969"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,29]]},"references-count":49,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,5,29]]}},"alternative-id":["10.1145\/3654969"],"URL":"https:\/\/doi.org\/10.1145\/3654969","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,5,29]]}}}