{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T07:17:32Z","timestamp":1779175052592,"version":"3.51.4"},"reference-count":52,"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:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"CAHSI-Google IRP"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,5,29]]},"abstract":"<jats:p>The task of extracting a diverse subset from a dataset, often referred to as maximum diversification, plays a pivotal role in various real-world applications that have far-reaching consequences. In this work, we delve into the realm of fairness-aware data subset selection, specifically focusing on the problem of selecting a diverse set of size k from a large collection of n data points (FairDiv). The FairDiv problem is well-studied in the data management and theory community. In this work, we develop the first constant approximation algorithm for FairDiv that runs in near-linear time using only linear space. In contrast, all previously known constant approximation algorithms run in super-linear time (with respect to n or k) and use super-linear space. Our approach achieves this efficiency by employing a novel combination of the Multiplicative Weight Update method and advanced geometric data structures to implicitly and approximately solve a linear program. Furthermore, we improve the efficiency of our techniques by constructing a coreset. Using our coreset, we also propose the first efficient streaming algorithm for the FairDiv problem whose efficiency does not depend on the distribution of data points. Empirical evaluation on million-sized datasets demonstrates that our algorithm achieves the best diversity within a minute. All prior techniques are either highly inefficient or do not generate a good solution.<\/jats:p>","DOI":"10.1145\/3654940","type":"journal-article","created":{"date-parts":[[2024,5,30]],"date-time":"2024-05-30T09:44:53Z","timestamp":1717062293000},"page":"1-26","source":"Crossref","is-referenced-by-count":6,"title":["Faster Algorithms for Fair Max-Min Diversification in R\n            <sup>d<\/sup>"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0009-0006-8809-2238","authenticated-orcid":false,"given":"Yash","family":"Kurkure","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Illinois at Chicago, Chicago, Illinois, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-4248-3775","authenticated-orcid":false,"given":"Miles","family":"Shamo","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Illinois at Chicago, Chicago, Illinois, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-6534-6395","authenticated-orcid":false,"given":"Joseph","family":"Wiseman","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Illinois at Chicago, Chicago, Illinois, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2529-4036","authenticated-orcid":false,"given":"Sainyam","family":"Galhotra","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Cornell University, Ithaca, New York, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2114-8886","authenticated-orcid":false,"given":"Stavros","family":"Sintos","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Illinois at Chicago, Chicago, Illinois, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,5,30]]},"reference":[{"key":"e_1_2_2_1_1","unstructured":"https:\/\/github.com\/UIC-DB-Theory\/FairDiversityandClustering."},{"key":"e_1_2_2_2_1","unstructured":"Beer review https:\/\/snap.stanford.edu\/data\/web-BeerAdvocate.html."},{"key":"e_1_2_2_3_1","unstructured":"Courts seek to increase jury diversity https:\/\/eji.org\/report\/race-and-the-jury\/why-representative-juries-arenecessary\/# chapter-2."},{"key":"e_1_2_2_4_1","unstructured":"Courts seek to increase jury diversity https:\/\/www.uscourts.gov\/news\/2019\/05\/09\/courts-seek-increase-jury-diversity."},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487575.2487636"},{"key":"e_1_2_2_6_1","volume-title":"33rd International Symposium on Computational Geometry (SoCG 2017","author":"Abrahamsen M.","year":"2017","unstructured":"M. Abrahamsen, M. de Berg, K. Buchin, M. Mehr, and A. D. Mehrabi. Range-clustering queries. In 33rd International Symposium on Computational Geometry (SoCG 2017). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017."},{"key":"e_1_2_2_7_1","volume-title":"25th International Conference on Database Theory (ICDT 2022","author":"Addanki R.","year":"2022","unstructured":"R. Addanki, A. McGregor, A. Meliou, and Z. Moumoulidou. Improved approximation and scalability for fair max-min diversification. In 25th International Conference on Database Theory (ICDT 2022). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, 2022."},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0110-y"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3375395.3387667"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2012.v008a006"},{"key":"e_1_2_2_11_1","volume-title":"Approximate range searching. Computational Geometry, 17(3--4):135--152","author":"Arya S.","year":"2000","unstructured":"S. Arya and D. M. Mount. Approximate range searching. Computational Geometry, 17(3--4):135--152, 2000."},{"key":"e_1_2_2_12_1","volume-title":"An optimal algorithm for approximate nearest neighbor searching fixed dimensions. Journal of the ACM (JACM), 45(6):891--923","author":"Arya S.","year":"1998","unstructured":"S. Arya, D. M. Mount, N. S. Netanyahu, R. Silverman, and A. Y. Wu. An optimal algorithm for approximate nearest neighbor searching fixed dimensions. Journal of the ACM (JACM), 45(6):891--923, 1998."},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.24432\/C5XW20"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/220279.220296"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1143844.1143857"},{"key":"e_1_2_2_16_1","volume-title":"Max-sum diversification, monotone submodular functions, and dynamic updates. ACM Transactions on Algorithms (TALG), 13(3):1--25","author":"Borodin A.","year":"2017","unstructured":"A. Borodin, A. Jain, H. C. Lee, and Y. Ye. Max-sum diversification, monotone submodular functions, and dynamic updates. ACM Transactions on Algorithms (TALG), 13(3):1--25, 2017."},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213556.2213580"},{"key":"e_1_2_2_18_1","volume-title":"A decomposition of multidimensional point sets with applications to k-nearestneighbors and n-body potential fields. Journal of the ACM (JACM), 42(1):67--90","author":"Callahan P. B.","year":"1995","unstructured":"P. B. Callahan and S. R. Kosaraju. A decomposition of multidimensional point sets with applications to k-nearestneighbors and n-body potential fields. Journal of the ACM (JACM), 42(1):67--90, 1995."},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3159652.3159719"},{"key":"e_1_2_2_20_1","volume-title":"A general coreset-based approach to diversity maximization under matroid constraints. ACM Transactions on Knowledge Discovery from Data (TKDD), 14(5):1--27","author":"Ceccarello M.","year":"2020","unstructured":"M. Ceccarello, A. Pietracaprina, and G. Pucci. A general coreset-based approach to diversity maximization under matroid constraints. ACM Transactions on Knowledge Discovery from Data (TKDD), 14(5):1--27, 2020."},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.9"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258657"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-015-0010-1"},{"key":"e_1_2_2_24_1","first-page":"1877","volume-title":"International Conference on Machine Learning","author":"Chiplunkar A.","year":"2020","unstructured":"A. Chiplunkar, S. Kale, and S. N. Ramamoorthy. How to solve fair k-center in massive data models. In International Conference on Machine Learning, pages 1877--1886. PMLR, 2020."},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62255"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-020-00683-w"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00288933"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/0047-2352(91)90081-6"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1080\/0735648X.2015.1087149"},{"key":"e_1_2_2_30_1","volume-title":"Clustering to minimize the maximum intercluster distance. Theoretical computer science, 38:293--306","author":"Gonzalez T. F.","year":"1985","unstructured":"T. F. Gonzalez. Clustering to minimize the maximum intercluster distance. Theoretical computer science, 38:293--306, 1985."},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1064092.1064117"},{"key":"e_1_2_2_32_1","volume-title":"Net and prune: A linear time algorithm for euclidean distance problems. Journal of the ACM (JACM), 62(6):1--35","author":"Har-Peled S.","year":"2015","unstructured":"S. Har-Peled and B. Raichel. Net and prune: A linear time algorithm for euclidean distance problems. Journal of the ACM (JACM), 62(6):1--35, 2015."},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451058"},{"key":"e_1_2_2_34_1","first-page":"4940","volume-title":"International conference on machine learning","author":"Jones M.","year":"2020","unstructured":"M. Jones, H. Nguyen, and T. Nguyen. Fair k-centers via maximum matching. In International conference on machine learning, pages 4940--4949. PMLR, 2020."},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","unstructured":"M. Kahn. Diabetes. UCI Machine Learning Repository. DOI: https:\/\/doi.org\/10.24432\/C5T59G.","DOI":"10.24432\/C5T59G"},{"key":"e_1_2_2_36_1","first-page":"3448","volume-title":"International Conference on Machine Learning","author":"Kleindessner M.","year":"2019","unstructured":"M. Kleindessner, P. Awasthi, and J. Morgenstern. Fair k-center clustering for data summarization. In International Conference on Machine Learning, pages 3448--3457. PMLR, 2019."},{"key":"e_1_2_2_37_1","volume-title":"Faster algorithms for fair max-min diversification in R?? . https:\/\/arxiv.org\/abs\/2404.04713","author":"Kurkure Y.","year":"2024","unstructured":"Y. Kurkure, M. Shamo, J. Wiseman, S. Galhotra, and S. Sintos. Faster algorithms for fair max-min diversification in R?? . https:\/\/arxiv.org\/abs\/2404.04713, 2024."},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.24432\/C5VP42"},{"key":"e_1_2_2_39_1","volume-title":"ICDT 2021","author":"Moumoulidou Z.","year":"2021","unstructured":"Z. Moumoulidou, A. McGregor, and A. Meliou. Diverse data selection under fairness constraints. ICDT 2021, 2021."},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2002.1019258"},{"key":"e_1_2_2_41_1","volume-title":"Machine learning and and Decision making (AFair- AMLD23)","author":"Nguyen K. D.","year":"2023","unstructured":"K. D. Nguyen, N. Shahbazi, and A. Asudeh. Popsim: An individual-level population simulator for equitable allocation of city resources. Algorithmic Fairness in Artificial intelligence, Machine learning and and Decision making (AFair- AMLD23), 2023."},{"key":"e_1_2_2_42_1","volume-title":"34th International Symposium on Computational Geometry (SoCG 2018","author":"Oh E.","year":"2018","unstructured":"E. Oh and H.-K. Ahn. Approximate range queries for clustering. In 34th International Symposium on Computational Geometry (SoCG 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018."},{"key":"e_1_2_2_43_1","volume-title":"International Conference on Learning Representations","author":"Pope P.","year":"2020","unstructured":"P. Pope, C. Zhu, A. Abdelkader, M. Goldblum, and T. Goldstein. The intrinsic dimension of images and its impact on learning. In International Conference on Learning Representations, 2020."},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.42.2.299"},{"key":"e_1_2_2_45_1","unstructured":"A. Roberts K. Vombatkere and B. Suwal. GitHub - kvombatkere\/CoreSets-algorithms: Python implementation of coreset algorithms for clustering and streaming."},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1137\/0404048"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/2582112.2582139"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE53745.2022.00008"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.3390\/e25071066"},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977653.ch11"},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/3503221.3508429"},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/2350190.2350193"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3654940","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3654940","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,21]],"date-time":"2025-08-21T14:40:02Z","timestamp":1755787202000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3654940"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,29]]},"references-count":52,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,5,29]]}},"alternative-id":["10.1145\/3654940"],"URL":"https:\/\/doi.org\/10.1145\/3654940","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,5,29]]}}}