Processing math: 100%
Skip to yearly menu bar Skip to main content


Poster

Fair Clustering in the Sliding Window Model

Vincent Cohen-Addad · Shaofeng Jiang · Qiaoyuan Yang · Yubo Zhang · Samson Zhou

Hall 3 + Hall 2B #511
[ ]
Sat 26 Apr midnight PDT — 2:30 a.m. PDT

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 ratio without violating the fairness constraint in 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+ε) factor, there exists a (1+ε)-approximate sliding window algorithm that uses poly(kε1logn) 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.

Live content is unavailable. Log in and register to view live content