Fair Clustering in the Sliding Window Model
Preprint
Abstract
We study streaming algorithms for proportionally fair clustering, a notion originally suggested by Chierichetti et. al. (2017), in the sliding window model. We show that although there exist efficient streaming algorithms in the insertion-only model, surprisingly no algorithm can achieve finite multiplicative ratio without violating the fairness constraint in the sliding window. Hence, the problem of fair clustering is a rare separation between the insertion-only streaming model and the sliding window model. On the other hand, we show that if the fairness constraint is relaxed by a multiplicative $(1+\varepsilon)$ factor, there exists a $(1 + \varepsilon)$-approximate sliding window algorithm that uses $\text{poly}(k\varepsilon^{-1}\log n)$ space. This achieves essentially the best parameters (up to degree in the polynomial) provided the aforementioned lower bound. We also implement a number of empirical evaluations on real datasets to complement our theoretical results.
Keywords
All Related Versions
This publication has 8 references indexed in Scilit:
- An Overview of Fairness in ClusteringIEEE Access, 2021
- A new coreset framework for clustering2021
- Fair Colorful k-Center Clustering2020
- A Technique for Obtaining True Approximations for k-Center with Covering Constraints2020
- Fair Coresets and Streaming Algorithms for Fair k-means2020
- On Coresets for k-Median and k-Means Clustering in Metric and Euclidean Spaces and Their ApplicationsSIAM Journal on Computing, 2009
- Maintaining Stream Statistics over Sliding WindowsSIAM Journal on Computing, 2002
- On Randomized One-round Communication Complexitycomputational complexity, 1999