Fair Max-Min Diversity Maximization in Streaming and Sliding-Window Models.

Diversity maximization is a fundamental problem with broad applications in data summarization, web search, and recommender systems. Given a set of elements, the problem asks for a subset of k≪n elements with maximum diversity, as quantified by the dissimilarities among the elements in . In this paper, we study diversity maximization with fairness constraints in streaming and sliding-window models. Specifically, we focus on the max-min diversity maximization problem, which selects a subset that maximizes the minimum distance (dissimilarity) between any pair of distinct elements within it. Assuming that the set is partitioned into disjoint groups by a specific sensitive attribute, e.g., sex or race, ensuring fairness requires that the selected subset contains ki elements from each group i∈[m]. Although diversity maximization has been extensively studied, existing algorithms for fair max-min 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 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.