{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,23]],"date-time":"2026-01-23T19:07:19Z","timestamp":1769195239822,"version":"3.49.0"},"reference-count":55,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2023,12,8]],"date-time":"2023-12-08T00:00:00Z","timestamp":1701993600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100006374","name":"NSF","doi-asserted-by":"publisher","award":["1942913, 2007935, 1814595, 2118458"],"award-info":[{"award-number":["1942913, 2007935, 1814595, 2118458"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100006374","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["N000141812838, N000142112966"],"award-info":[{"award-number":["N000141812838, N000142112966"]}],"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":[[2023,12,8]]},"abstract":"<jats:p>For datasets exhibiting long tail phenomenon, we identify a fairness concern in existing top-k algorithms, that return a \"fixed\" set of k results for a given query. This causes a handful of popular records (products, items, etc) getting overexposed and always be returned to the user query, whereas, there exists a long tail of niche records that may be equally desirable (have similar utility). To alleviate this, we propose \u03b8-Equiv-top-k-MMSP inside existing top-k algorithms - instead of returning a fixed top-k set, it generates all (or many) top-k sets that are equivalent in utility and creates a probability distribution over those sets. The end user will be returned one of these sets during the query time proportional to its associated probability, such that, after many draws from many end users, each record will have as equal exposure as possible (governed by uniform selection probability). \u03b8-Equiv-top-k-MMSP is formalized with two sub-problems. (a) \u03b8-Equiv-top-k-Sets to produce a set S of sets, each set has k records, where the sets are equivalent in utility with the top-k set; (b) MaxMinFair to produce a probability distribution over S, that is, PDF(S), such that the records in S have uniform selection probability. We formally study the hardness of \u03b8-Equiv-top-k-MMSP. We present multiple algorithmic results - (a) An exact solution for \u03b8-Equiv-top-k-Sets, and MaxMinFair. (b) We design highly scalable algorithms that solve \u03b8-Equiv-top-k-Sets through a random walk and is backed by probability theory, as well as a greedy solution designed for MaxMinFair. (c) We finally present an adaptive random walk based algorithm that solves \u03b8-Equiv-top-k-Sets and MaxMinFair at the same time. We empirically study how \u03b8-Equiv-top-k-MMSP can alleviate a equitable exposure concerns that group fairness suffers from. We run extensive experiments using 6 datasets and design intuitive baseline algorithms that corroborate our theoretical analysis.<\/jats:p>","DOI":"10.1145\/3626727","type":"journal-article","created":{"date-parts":[[2023,12,12]],"date-time":"2023-12-12T14:01:21Z","timestamp":1702389681000},"page":"1-24","source":"Crossref","is-referenced-by-count":4,"title":["Equitable Top-k Results for Long Tail Data"],"prefix":"10.1145","volume":"1","author":[{"ORCID":"https:\/\/orcid.org\/0009-0006-7560-9197","authenticated-orcid":false,"given":"Md Mouinul","family":"Islam","sequence":"first","affiliation":[{"name":"New Jersey Institute of Technology, Newark, NJ, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8208-7562","authenticated-orcid":false,"given":"Mahsa","family":"Asadi","sequence":"additional","affiliation":[{"name":"New Jersey Institute of Technology, Newark, NJ, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3475-8138","authenticated-orcid":false,"given":"Senjuti","family":"Basu Roy","sequence":"additional","affiliation":[{"name":"New Jersey Institute of Technology, Newark, NJ, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,12,12]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488388.2488390"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2462356.2462401"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3375395.3387667"},{"key":"e_1_2_2_4_1","unstructured":"Airbnb. 2023. Dataset. http:\/\/insideairbnb.com\/get-the-data"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.22230\/cjc.2008v33n1a1946"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3300079"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3471485.3471496"},{"key":"e_1_2_2_8_1","volume-title":"The 41st international acm sigir conference on research & development in information retrieval. 405--414.","author":"Biega Asia J","unstructured":"Asia J Biega, Krishna P Gummadi, and Gerhard Weikum. 2018. Equity of attention: Amortizing individual fairness in rankings. In The 41st international acm sigir conference on research & development in information retrieval. 405--414."},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3351095.3372864"},{"key":"e_1_2_2_10_1","volume-title":"Diversified spatial keyword search on RDF data. The VLDB Journal","author":"Cai Zhi","year":"2020","unstructured":"Zhi Cai, Georgios Kalamatianos, Georgios J Fakas, Nikos Mamoulis, and Dimitris Papadias. 2020. Diversified spatial keyword search on RDF data. The VLDB Journal (2020), 1--19."},{"key":"e_1_2_2_11_1","volume-title":"Unsupervised Time Series Outlier Detection with Diversity-Driven Convolutional Ensembles--Extended Version. arXiv preprint arXiv:2111.11108","author":"Campos David","year":"2021","unstructured":"David Campos, Tung Kieu, Chenjuan Guo, Feiteng Huang, Kai Zheng, Bin Yang, and Christian S Jensen. 2021. Unsupervised Time Series Outlier Detection with Diversity-Driven Convolutional Ensembles--Extended Version. arXiv preprint arXiv:2111.11108 (2021)."},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/290941.291025"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066220"},{"key":"e_1_2_2_14_1","unstructured":"Codes and data. 2024. https:\/\/anonymous.4open.science\/r\/FairSelectionInsideTopk-2F4F\/README.md."},{"key":"e_1_2_2_15_1","volume-title":"Sortition: Thoery and Practice.","author":"Delannoi Gil","year":"2016","unstructured":"Gil Delannoi and Oliver Dowlen. 2016. Sortition: Thoery and Practice. Vol. 3. Andrews UK Limited."},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2090236.2090255"},{"key":"e_1_2_2_17_1","volume-title":"Lecture notes on fair division. arXiv preprint arXiv:1806.04234","author":"Endriss Ulle","year":"2018","unstructured":"Ulle Endriss. 2018. Lecture notes on fair division. arXiv preprint arXiv:1806.04234 (2018)."},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3442381.3450046"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00026-6"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3308558.3313680"},{"key":"e_1_2_2_21_1","volume-title":"Fair algorithms for selecting citizens' assemblies. Nature 596, 7873","author":"Flanigan Bailey","year":"2021","unstructured":"Bailey Flanigan, Paul G\u00f6lz, Anupam Gupta, Brett Hennig, and Ariel D Procaccia. 2021. Fair algorithms for selecting citizens' assemblies. Nature 596, 7873 (2021), 548--552."},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3461702.3462621"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3433949"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1080\/09296179508590051"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3447548.3467349"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3292500.3330691"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/777943.777945"},{"key":"e_1_2_2_28_1","unstructured":"Jiawei Han Jian Pei and Hanghang Tong. 2022. Data mining: concepts and techniques. Morgan kaufmann."},{"key":"e_1_2_2_29_1","unstructured":"IMDB. 2023. Dataset. https:\/\/www.kaggle.com\/datasets\/isaactaylorofficial\/imdb-10000-most-voted-feature-films-041118"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3384689"},{"key":"e_1_2_2_31_1","unstructured":"Kaggle. [n. d.]. Top-1000 IMDB Movies. https:\/\/www.kaggle.com\/datasets\/harshitshankhdhar\/imdb-dataset-of-top-1000-movies-and-tv-shows."},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407855"},{"key":"e_1_2_2_33_1","doi-asserted-by":"crossref","unstructured":"Chang Li Haoyun Feng and Maarten de Rijke. 2020. Cascading Hybrid Bandits: Online Learning to Rank for Relevance and Diversity. In RecSys 2020: The ACM Conference on Recommender Systems. ACM 33--42.","DOI":"10.1145\/3383313.3412245"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3442381.3449866"},{"key":"e_1_2_2_35_1","volume-title":"International Conference on Machine Learning. PMLR, 6586--6596","author":"Mahabadi Sepideh","year":"2020","unstructured":"Sepideh Mahabadi and Ali Vakilian. 2020. Individual fairness for k-clustering. In International Conference on Machine Learning. PMLR, 6586--6596."},{"key":"e_1_2_2_36_1","unstructured":"Makeblobs. 2023. Dataset. https:\/\/scikit-learn.org\/stable\/modules\/generated\/sklearn.datasets.make_blobs.html"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/263661.263677"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3366423.3380196"},{"key":"e_1_2_2_39_1","volume-title":"Fairness in rankings and recommendations: an overview. The VLDB Journal","author":"Pitoura Evaggelia","year":"2021","unstructured":"Evaggelia Pitoura, Kostas Stefanidis, and Georgia Koutrika. 2021. Fairness in rankings and recommendations: an overview. The VLDB Journal (2021), 1--28."},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3186549.3186553"},{"key":"e_1_2_2_41_1","volume-title":"Jeffrey Xu Yu, and Lijun Chang","author":"Qin Lu","year":"2012","unstructured":"Lu Qin, Jeffrey Xu Yu, and Lijun Chang. 2012. Diversifying top-k results. arXiv preprint arXiv:1208.0076 (2012)."},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772770"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3422648.3422657"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3220088"},{"key":"e_1_2_2_45_1","volume-title":"voting, and democratic equality. Critical review of international social and political philosophy 19, 3","author":"Stone Peter","year":"2016","unstructured":"Peter Stone. 2016. Sortition, voting, and democratic equality. Critical review of international social and political philosophy 19, 3 (2016), 339--356."},{"key":"e_1_2_2_46_1","volume-title":"Daan Odijk, and Maarten de Rijke.","author":"Vrijenhoek Sanne","year":"2022","unstructured":"Sanne Vrijenhoek, Gabriel B\u00e9n\u00e9dict, Mateo Gutierrez Granada, Daan Odijk, and Maarten de Rijke. 2022. RADio -- Rank-Aware Divergence Metrics to Measure Normative Diversity in News Recommendation. In RecSys 2022: The ACM Conference on Recommender Systems. ACM."},{"key":"e_1_2_2_47_1","volume-title":"Diversified and scalable service recommendation with accuracy guarantee","author":"Wang Lina","year":"2020","unstructured":"Lina Wang, Xuyun Zhang, Tian Wang, Shaohua Wan, Gautam Srivastava, Shaoning Pang, and Lianyong Qi. 2020. Diversified and scalable service recommendation with accuracy guarantee. IEEE Transactions on Computational Social Systems (2020)."},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3517865"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/1014052.1014091"},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/3085504.3085526"},{"key":"e_1_2_2_51_1","unstructured":"Yelp. 2023. Dataset. https:\/\/www.yelp.com\/dataset\/documentation\/main"},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/3038912.3052660"},{"key":"e_1_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/3132847.3132938"},{"key":"e_1_2_2_54_1","volume-title":"International conference on machine learning. PMLR, 325--333","author":"Zemel Rich","year":"2013","unstructured":"Rich Zemel, Yu Wu, Kevin Swersky, Toni Pitassi, and Cynthia Dwork. 2013. Learning fair representations. In International conference on machine learning. PMLR, 325--333."},{"key":"e_1_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3452787"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3626727","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3626727","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T13:01:25Z","timestamp":1755867685000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3626727"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12,8]]},"references-count":55,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,12,8]]}},"alternative-id":["10.1145\/3626727"],"URL":"https:\/\/doi.org\/10.1145\/3626727","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,12,8]]}}}