Fair Max–Min Diversity Maximization in Streaming and Sliding-Window Models
Open Access
Abstract
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 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–min 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 elements from each group . 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 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.
Keywords
Funding Information
- Research Council of Finland (322046, 62202169)
- National Natural Science Foundation of China (322046, 62202169)
This publication has 32 references indexed in Scilit:
- Matroid and Knapsack Center ProblemsAlgorithmica, 2015
- Diverse Set Selection Over Dynamic DataIEEE Transactions on Knowledge and Data Engineering, 2013
- DisC diversityProceedings of the VLDB Endowment, 2012
- Diversifying top-k resultsProceedings of the VLDB Endowment, 2012
- Approximation Algorithms for Dispersion ProblemsJournal of Algorithms, 2001
- Approximation algorithms for maximum dispersionOperations Research Letters, 1997
- Heuristic and Special Case Algorithms for Dispersion ProblemsOperations Research, 1994
- The discrete p-dispersion problemEuropean Journal of Operational Research, 1990
- Improved Bounds for Matroid Partition and Intersection AlgorithmsSIAM Journal on Computing, 1986
- Clustering to minimize the maximum intercluster distanceTheoretical Computer Science, 1985