Research map / Learning theory and algorithms / Clustering
Fair Clustering in the Sliding Window Model
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that fair (k,z)-clustering in the sliding window model admits no finite-ratio sublinear-space algorithm, and gives a (1+ε) coreset-based algorithm that relaxes fairness by a (1±ε) factor, with experiments on five real datasets.
Problem
Streaming proportionally fair (k,z)-clustering under the sliding window model, where points must be clustered with fairness constraints on the most recent window using sublinear space.
Approach
A communication-complexity lower bound (Augmented Index) shows linear space is needed for any finite multiplicative approximation to fair clustering in sliding windows; to circumvent it, the authors build online assignment-preserving coresets combined with merge-and-reduce, and allow a (1±ε) relaxation of fairness constraints.
Key results
- Theorem: any sliding-window fair clustering algorithm achieving any finite multiplicative approximation (or additive Δ/2-1 error) must use Ω(n) space.
- Relaxing fairness by (1±ε), the algorithm achieves (1+ε)-approximation with poly(ε^-1 k d log Δ) space times L, via coresets.
- Experiments on five datasets show the coreset approach achieves cost comparable to the full-window benchmark with much less space and better accuracy and running time than Borassi on larger datasets.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Require exact fairness instead of allowing fairness violation | Fair clustering in the sliding window model · Fair (k,z)-clustering, sliding window | space required for a multiplicative approximation: any multiplicative approximation; \Omega(n) space | Hurt |
| Relax fairness constraints to ((1 - ε)α, (1 + ε)β) | Fair clustering in the sliding window model · Fair (k,z)-clustering, sliding window | approximation ratio: 1 + \varepsilon | Helped |
| Use the proposed coreset algorithm instead of Benchmark | Fair k-median in the sliding window model · Five real datasets | space | Helped |
| Use the proposed coreset algorithm instead of Uniform sampling | Fair k-median in the sliding window model · Five real datasets | objective value | Helped |
| Use the proposed coreset algorithm instead of Borassi | Fair k-median in the sliding window model · Five real datasets | accuracy | Helped |
| Use the proposed coreset algorithm instead of Borassi | Fair k-median in the sliding window model · Larger datasets | running time | Helped |
Surprising findings
- No sublinear-space sliding-window algorithm can achieve any finite multiplicative approximation for fair clustering, unlike insertion-only streaming and unconstrained sliding-window clustering.
Limitations
- Exact (1+ε) guarantee requires relaxing fairness constraints by (1±ε); strict fairness is impossible in sublinear space.
- Theoretical algorithm's running time is exponential due to APX-hardness, so practical experiments use a heuristic downstream solver (Fairtree).
- Coreset sizes in experiments are set directly rather than from the worst-case bound.
Experimental setup
Datasets: Adult Bank Diabetes Athlete Census
Benchmarks: Adult Bank Diabetes Athlete Census
Metrics: fair k-median cost running time space
Baselines: Benchmark (full window) Uniform sampling coreset Borassi et al. sliding window clustering
Builds on: Meyerson sketch merge-and-reduce assignment-preserving coresets Fairtree
Closest papers by meaning
- Online Differentially Private Consistent Clustering (NeurIPS 2026 · similarity 0.88)
- Relative Error Fair Clustering in the Weak-Strong Oracle Model (ICML 2025 · similarity 0.88)
- Proportional Fairness in Non-Centroid Clustering (NeurIPS 2024 · similarity 0.88)
- The Fairness-Quality Tradeoff in Clustering (NeurIPS 2024 · similarity 0.87)
- Fair Clustering via Alignment (ICML 2025 · similarity 0.87)
- Relax and Merge: A Simple Yet Effective Framework for Solving Fair $k$-Means and $k$-sparse Wasserstein Barycenter Problems (ICLR 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.