{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T05:54:11Z","timestamp":1777614851779,"version":"3.51.4"},"reference-count":45,"publisher":"MDPI AG","issue":"7","license":[{"start":{"date-parts":[[2023,7,14]],"date-time":"2023-07-14T00:00:00Z","timestamp":1689292800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100002341","name":"Academy of Finland","doi-asserted-by":"publisher","award":["322046"],"award-info":[{"award-number":["322046"]}],"id":[{"id":"10.13039\/501100002341","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002341","name":"Academy of Finland","doi-asserted-by":"publisher","award":["62202169"],"award-info":[{"award-number":["62202169"]}],"id":[{"id":"10.13039\/501100002341","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["322046"],"award-info":[{"award-number":["322046"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["62202169"],"award-info":[{"award-number":["62202169"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>Diversity maximization is a fundamental problem with broad applications in data summarization, web search, and recommender systems. Given a set X of n elements, the problem asks for a subset S of k\u226an elements with maximum diversity, as quantified by the dissimilarities among the elements in S. In this paper, we study diversity maximization with fairness constraints in streaming and sliding-window models. Specifically, we focus on the max\u2013min diversity maximization problem, which selects a subset S that maximizes the minimum distance (dissimilarity) between any pair of distinct elements within it. Assuming that the set X is partitioned into m disjoint groups by a specific sensitive attribute, e.g., sex or race, ensuring fairness requires that the selected subset S contains ki elements from each group i\u2208[m]. Although diversity maximization has been extensively studied, existing algorithms for fair max\u2013min diversity maximization are inefficient for data streams. To address the problem, we first design efficient approximation algorithms for this problem in the (insert-only) streaming model, where data arrive one element at a time, and a solution should be computed based on the elements observed in one pass. Furthermore, we propose approximation algorithms for this problem in the sliding-window model, where only the latest w elements in the stream are considered for computation to capture the recency of the data. Experimental results on real-world and synthetic datasets show that our algorithms provide solutions of comparable quality to the state-of-the-art offline algorithms while running several orders of magnitude faster in the streaming and sliding-window settings.<\/jats:p>","DOI":"10.3390\/e25071066","type":"journal-article","created":{"date-parts":[[2023,7,17]],"date-time":"2023-07-17T00:35:04Z","timestamp":1689554104000},"page":"1066","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Fair Max\u2013Min Diversity Maximization in Streaming and Sliding-Window Models"],"prefix":"10.3390","volume":"25","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7661-3917","authenticated-orcid":false,"given":"Yanhao","family":"Wang","sequence":"first","affiliation":[{"name":"School of Data Science and Engineering, East China Normal University, Shanghai 200062, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Francesco","family":"Fabbri","sequence":"additional","affiliation":[{"name":"Spotify, 08000 Barcelona, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0074-3966","authenticated-orcid":false,"given":"Michael","family":"Mathioudakis","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Helsinki, 00560 Helsinki, Finland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jia","family":"Li","sequence":"additional","affiliation":[{"name":"School of Data Science and Engineering, East China Normal University, Shanghai 200062, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2023,7,14]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1007\/s10115-018-1183-0","article-title":"Data summarization: A survey","volume":"58","author":"Ahmed","year":"2019","journal-title":"Knowl. Inf. Syst."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"1124","DOI":"10.14778\/2350229.2350233","article-title":"Diversifying Top-K Results","volume":"5","author":"Qin","year":"2012","journal-title":"Proc. VLDB Endow."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s10115-016-0990-4","article-title":"A survey of query result diversification","volume":"51","author":"Zheng","year":"2017","journal-title":"Knowl. Inf. Syst."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Gollapudi, S., and Sharma, A. (2009, January 20\u201324). An axiomatic approach for result diversification. Proceedings of the 18th International Conference on World Wide Web, Madrid, Spain.","DOI":"10.1145\/1526709.1526761"},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Rafiei, D., Bharat, K., and Shukla, A. (2010, January 26\u201330). Diversifying web search results. Proceedings of the 19th International Conference on World Wide Web, Raleigh, NC, USA.","DOI":"10.1145\/1772690.1772770"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"154","DOI":"10.1016\/j.knosys.2017.02.009","article-title":"Diversity in recommender systems\u2014A survey","volume":"123","author":"Kunaver","year":"2017","journal-title":"Knowl. Based Syst."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Zadeh, S.A., Ghadiri, M., Mirrokni, V.S., and Zadimoghaddam, M. (2017, January 4\u20139). Scalable Feature Selection via Distributed Diversity Maximization. Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, San Francisco, CA, USA.","DOI":"10.1609\/aaai.v31i1.10926"},{"key":"ref_8","unstructured":"Celis, L.E., Keswani, V., Straszak, D., Deshpande, A., Kathuria, T., and Vishnoi, N.K. (2018, January 10\u201315). Fair and Diverse DPP-Based Data Summarization. Proceedings of the 35th International Conference on Machine Learning, Stockholm, Sweden."},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Borodin, A., Lee, H.C., and Ye, Y. (2012, January 21\u201323). Max-Sum diversification, monotone submodular functions and dynamic updates. Proceedings of the 31st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, Scottsdale, AZ, USA.","DOI":"10.1145\/2213556.2213580"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"13","DOI":"10.14778\/2428536.2428538","article-title":"DisC diversity: Result diversification based on dissimilarity and coverage","volume":"6","author":"Drosou","year":"2012","journal-title":"Proc. VLDB Endow."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Abbassi, Z., Mirrokni, V.S., and Thakur, M. (2013, January 11\u201314). Diversity maximization under matroid constraints. Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Chicago, IL, USA.","DOI":"10.1145\/2487575.2487636"},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Indyk, P., Mahabadi, S., Mahdian, M., and Mirrokni, V.S. (2014, January 15\u201317). Composable core-sets for diversity and coverage maximization. Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, Dallas, TX, USA.","DOI":"10.1145\/2594538.2594560"},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Ceccarello, M., Pietracaprina, A., and Pucci, G. (2018, January 5\u20139). Fast Coreset-based Diversity Maximization under Matroid Constraints. Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining, Marina Del Rey, CA, USA.","DOI":"10.1145\/3159652.3159719"},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Borassi, M., Epasto, A., Lattanzi, S., Vassilvitskii, S., and Zadimoghaddam, M. (2019, January 1\u20133). Better Sliding Window Algorithms to Maximize Subadditive and Diversity Objectives. Proceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, Amsterdam, The Netherlands.","DOI":"10.1145\/3294052.3319701"},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Bauckhage, C., Sifa, R., and Wrobel, S. (2020, January 7\u20139). Adiabatic Quantum Computing for Max-Sum Diversification. Proceedings of the 2020 SIAM International Conference on Data Mining, Cincinnati, OH, USA.","DOI":"10.1137\/1.9781611976236.39"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"469","DOI":"10.14778\/3055540.3055541","article-title":"MapReduce and Streaming Algorithms for Diversity Maximization in Metric Spaces of Bounded Doubling Dimension","volume":"10","author":"Ceccarello","year":"2017","journal-title":"Proc. VLDB Endow."},{"key":"ref_17","unstructured":"Moumoulidou, Z., McGregor, A., and Meliou, A. (2021, January 23\u201326). Diverse Data Selection under Fairness Constraints. Proceedings of the 24th International Conference on Database Theory, Nicosia, Cyprus."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"1102","DOI":"10.1109\/TKDE.2013.44","article-title":"Diverse Set Selection Over Dynamic Data","volume":"26","author":"Drosou","year":"2014","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Zhang, G., and Gionis, A. (2020, January 7\u20139). Maximizing diversity over clustered data. Proceedings of the 2020 SIAM International Conference on Data Mining, Cincinnati, OH, USA.","DOI":"10.1137\/1.9781611976236.73"},{"key":"ref_20","unstructured":"Addanki, R., McGregor, A., Meliou, A., and Moumoulidou, Z. (April, January 29). Improved Approximation and Scalability for Fair Max-Min Diversification. Proceedings of the 25th International Conference on Database Theory, Online."},{"key":"ref_21","unstructured":"Chiplunkar, A., Kale, S., and Ramamoorthy, S.N. (2020, January 13\u201318). How to Solve Fair k-Center in Massive Data Models. Proceedings of the 37th International Conference on Machine Learning, Virtual."},{"key":"ref_22","unstructured":"Jones, M., Nguyen, H., and Nguyen, T. (2020, January 13\u201318). Fair k-Centers via Maximum Matching. Proceedings of the 37th International Conference on Machine Learning, Virtual."},{"key":"ref_23","unstructured":"Kleindessner, M., Awasthi, P., and Morgenstern, J. (2019, January 9\u201315). Fair k-Center Clustering for Data Summarization. Proceedings of the 36th International Conference on Machine Learning, Long Beach, CA, USA."},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Schmidt, M., Schwiegelshohn, C., and Sohler, C. (2019, January 12\u201313). Fair Coresets and Streaming Algorithms for Fair k-means. Proceedings of the 17th International Workshop on Approximation and Online Algorithms, Munich, Germany.","DOI":"10.1007\/978-3-030-39479-0_16"},{"key":"ref_25","first-page":"7587","article-title":"Coresets for Clustering with Fairness Constraints","volume":"32","author":"Huang","year":"2019","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"ref_26","first-page":"13609","article-title":"Fairness in Streaming Submodular Maximization: Algorithms and Hardness","volume":"33","author":"Tardos","year":"2020","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Wang, Y., Fabbri, F., and Mathioudakis, M. (2021, January 19\u201323). Fair and Representative Subset Selection from Data Streams. Proceedings of the Web Conference 2021, Ljubljana, Slovenia.","DOI":"10.1145\/3442381.3449799"},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Wang, Y., Fabbri, F., and Mathioudakis, M. (2022, January 9\u201312). Streaming Algorithms for Diversity Maximization with Fairness Constraints. Proceedings of the 38th IEEE International Conference on Data Engineering, Kuala Lumpur, Malaysia.","DOI":"10.1109\/ICDE53745.2022.00008"},{"key":"ref_29","unstructured":"Cevallos, A., Eisenbrand, F., and Zenklusen, R. (2016, January 14\u201318). Max-Sum Diversity via Convex Programming. Proceedings of the 32nd International Symposium on Computational Geometry, Boston, MA, USA."},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Cevallos, A., Eisenbrand, F., and Zenklusen, R. (2017, January 16\u201319). Local Search for Max-Sum Diversification. Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, Barcelona, Spain.","DOI":"10.1137\/1.9781611974782.9"},{"key":"ref_31","unstructured":"Aghamolaei, S., Farhadi, M., and Zarrabi-Zadeh, H. (2015, January 10\u201312). Diversity Maximization via Composable Coresets. Proceedings of the 27th Canadian Conference on Computational Geometry, Kingston, ON, Canada."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"438","DOI":"10.1006\/jagm.2000.1145","article-title":"Approximation Algorithms for Dispersion Problems","volume":"38","author":"Chandra","year":"2001","journal-title":"J. Algorithms"},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1016\/0377-2217(90)90297-O","article-title":"The discrete p-dispersion problem","volume":"46","author":"Erkut","year":"1990","journal-title":"Eur. J. Oper. Res."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1287\/opre.42.2.299","article-title":"Heuristic and Special Case Algorithms for Dispersion Problems","volume":"42","author":"Ravi","year":"1994","journal-title":"Oper. Res."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1016\/S0167-6377(97)00034-5","article-title":"Approximation algorithms for maximum dispersion","volume":"21","author":"Hassin","year":"1997","journal-title":"Oper. Res. Lett."},{"key":"ref_36","doi-asserted-by":"crossref","unstructured":"Epasto, A., Mahdian, M., Mirrokni, V., and Zhong, P. (2022, January 9\u201312). Improved Sliding Window Algorithms for Clustering and Coverage via Bucketing-Based Sketches. Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, Virtual.","DOI":"10.1137\/1.9781611977073.117"},{"key":"ref_37","first-page":"4098","article-title":"Linear Relaxations for Finding Diverse Elements in Metric Spaces","volume":"29","author":"Bhaskara","year":"2016","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"ref_38","doi-asserted-by":"crossref","unstructured":"Wang, Y., Mathioudakis, M., Li, J., and Fabbri, F. (2023, January 27\u201329). Max-Min Diversification with Fairness Constraints: Exact and Approximation Algorithms. Proceedings of the 2023 SIAM International Conference on Data Mining (SDM), Minneapolis, MI, USA.","DOI":"10.1137\/1.9781611977653.ch11"},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1016\/0304-3975(85)90224-5","article-title":"Clustering to Minimize the Maximum Intercluster Distance","volume":"38","author":"Gonzalez","year":"1985","journal-title":"Theor. Comput. Sci."},{"key":"ref_40","doi-asserted-by":"crossref","unstructured":"Korte, B., and Vygen, J. (2012). Combinatorial Optimization: Theory and Algorithms, Springer.","DOI":"10.1007\/978-3-642-24488-9"},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"948","DOI":"10.1137\/0215066","article-title":"Improved Bounds for Matroid Partition and Intersection Algorithms","volume":"15","author":"Cunningham","year":"1986","journal-title":"SIAM J. Comput."},{"key":"ref_42","doi-asserted-by":"crossref","unstructured":"Chakrabarty, D., Lee, Y.T., Sidford, A., Singla, S., and Wong, S.C. (2019, January 9\u201312). Faster Matroid Intersection. Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, Baltimore, MD, USA.","DOI":"10.1109\/FOCS.2019.00072"},{"key":"ref_43","unstructured":"Nguyen, H.L. (2019). A note on Cunningham\u2019s algorithm for matroid intersection. arXiv."},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1007\/s00453-015-0010-1","article-title":"Matroid and Knapsack Center Problems","volume":"75","author":"Chen","year":"2016","journal-title":"Algorithmica"},{"key":"ref_45","first-page":"993","article-title":"Latent Dirichlet Allocation","volume":"3","author":"Blei","year":"2003","journal-title":"J. Mach. Learn. Res."}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/25\/7\/1066\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T20:12:25Z","timestamp":1760127145000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/25\/7\/1066"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7,14]]},"references-count":45,"journal-issue":{"issue":"7","published-online":{"date-parts":[[2023,7]]}},"alternative-id":["e25071066"],"URL":"https:\/\/doi.org\/10.3390\/e25071066","relation":{},"ISSN":["1099-4300"],"issn-type":[{"value":"1099-4300","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,7,14]]}}}