{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,27]],"date-time":"2025-10-27T21:07:26Z","timestamp":1761599246780},"reference-count":51,"publisher":"Association for Computing Machinery (ACM)","issue":"9","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2023,5]]},"abstract":"<jats:p>This work considers why-not questions in the context of top-k queries and score-based ranking functions. Following the popular linear scalarization approach for multi-objective optimization, we study rankings based on the weighted sum of multiple scores. A given weight choice may be controversial or perceived as unfair to certain individuals or organizations, triggering the question why some entity of interest has not yet shown up in the top-k. We introduce various notions of such why-not-yet queries and formally define them as satisfiability or optimization problems, whose goal is to propose alternative ranking functions that address the placement of the entities of interest. While some why-not-yet problems have linear constraints, others require quantifiers, disjunction, and negation. We propose several optimizations, ranging from a monotonic-core construction that approximates the complex constraints with a conjunction of linear ones, to various techniques that let the user control the tradeoff between running time and approximation quality. Experiments with real and synthetic data demonstrate the practicality and scalability of our technique, showing its superiority compared to the state of the art (SOA).<\/jats:p>","DOI":"10.14778\/3598581.3598606","type":"journal-article","created":{"date-parts":[[2023,7,10]],"date-time":"2023-07-10T22:19:06Z","timestamp":1689027546000},"page":"2377-2390","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["Why Not Yet: Fixing a Top-k Ranking that is Not Fair to Individuals"],"prefix":"10.14778","volume":"16","author":[{"given":"Zixuan","family":"Chen","sequence":"first","affiliation":[{"name":"Northeastern University, Boston, USA"}]},{"given":"Panagiotis","family":"Manolios","sequence":"additional","affiliation":[{"name":"Northeastern University, Boston, USA"}]},{"given":"Mirek","family":"Riedewald","sequence":"additional","affiliation":[{"name":"Northeastern University, Boston, USA"}]}],"member":"320","published-online":{"date-parts":[[2023,7,10]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms. 1027--1035","author":"Arthur D.","unstructured":"D. Arthur and S. Vassilvitskii . 2007. k-means++: the advantages of careful seeding . In Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms. 1027--1035 . http:\/\/dl.acm.org\/citation.cfm?id=1283383.1283494 D. Arthur and S. Vassilvitskii. 2007. k-means++: the advantages of careful seeding. In Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms. 1027--1035. http:\/\/dl.acm.org\/citation.cfm?id=1283383.1283494"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.14778\/3291264.3291269"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3300079"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5441\/002\/edbt.2014.14"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2001.914855"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.14778\/2904483.2904489"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559901"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2017.51"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2015.7113291"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2016.7498282"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-37487-6_17"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-78800-3_24"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476311.3476331"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457249"},{"key":"e_1_2_1_15_1","volume-title":"Witten","author":"Frank Eibe","year":"2016","unstructured":"Eibe Frank , Mark A. Hall , and Ian H . Witten . 2016 . The WEKA Workbench. Online Appendix for \"Data Mining : Practical Machine Learning Tools and Techniques\", Morgan Kaufmann , Fourth Edition. https:\/\/www.cs.waikato.ac.nz\/ml\/weka\/Witten_et_al_2016_appendix.pdf Eibe Frank, Mark A. Hall, and Ian H. Witten. 2016. The WEKA Workbench. Online Appendix for \"Data Mining: Practical Machine Learning Tools and Techniques\", Morgan Kaufmann, Fourth Edition. https:\/\/www.cs.waikato.ac.nz\/ml\/weka\/Witten_et_al_2016_appendix.pdf"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3526149"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.14778\/2752939.2752943"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3517898"},{"key":"e_1_2_1_19_1","unstructured":"Gurobi Optimization LLC. 2022. Gurobi Optimizer Reference Manual. https:\/\/www.gurobi.com  Gurobi Optimization LLC. 2022. Gurobi Optimizer Reference Manual. https:\/\/www.gurobi.com"},{"key":"e_1_2_1_20_1","volume-title":"Data Mining: Concepts and Techniques","author":"Han J.","year":"2011","unstructured":"J. Han , M. Kamber , and J. Pei . 2011 . Data Mining: Concepts and Techniques ( 3 rd ed.). Morgan Kaufmann . J. Han, M. Kamber, and J. Pei. 2011. Data Mining: Concepts and Techniques (3rd ed.). Morgan Kaufmann.","edition":"3"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2012.8"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2012.158"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920869"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/375663.375690"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453936"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1391729.1391730"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247480.1247483"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-05810-8_27"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389767"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.14778\/3554821.3554852"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3459246"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-016-0443-4"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2017.182"},{"key":"e_1_2_1_34_1","volume-title":"https:\/\/www.basketball-reference.com\/, visited on","author":"Basketball-Reference Sports Reference LLC.","year":"2022","unstructured":"Sports Reference LLC. 2022. Basketball-Reference .com - Basketball Statistics and History. https:\/\/www.basketball-reference.com\/, visited on October 2, 2022 . Sports Reference LLC. 2022. Basketball-Reference.com - Basketball Statistics and History. https:\/\/www.basketball-reference.com\/, visited on October 2, 2022."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.14778\/1880172.1880176"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.14778\/3402755.3402803"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213875"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319866"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.14778\/3554821.3554902"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807172"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2010.5447890"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2011.50"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920890"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465278"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/FSKD.2010.5569416"},{"key":"e_1_2_1_46_1","volume-title":"Proceedings of the 32nd International Conference on Very Large Data Bases, VLDB 2006. 235--246","author":"Xin Dong","year":"2006","unstructured":"Dong Xin , Chen Chen , and Jiawei Han . 2006 . Towards Robust Indexing for Ranked Queries . In Proceedings of the 32nd International Conference on Very Large Data Bases, VLDB 2006. 235--246 . http:\/\/dl.acm.org\/citation.cfm?id=1164149 Dong Xin, Chen Chen, and Jiawei Han. 2006. Towards Robust Indexing for Ranked Queries. In Proceedings of the 32nd International Conference on Very Large Data Bases, VLDB 2006. 235--246. http:\/\/dl.acm.org\/citation.cfm?id=1164149"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2016.2547398"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/3533379"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/3533380"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732951.2732952"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2018.00091"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3598581.3598606","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,7,19]],"date-time":"2023-07-19T22:58:50Z","timestamp":1689807530000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3598581.3598606"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5]]},"references-count":51,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2023,5]]}},"alternative-id":["10.14778\/3598581.3598606"],"URL":"https:\/\/doi.org\/10.14778\/3598581.3598606","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2023,5]]},"assertion":[{"value":"2023-07-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}