Adversarially Robust Streaming Algorithms for $(k,z)$-Clustering

Abstract

We design adversarially robust algorithms for dynamic geometric streams that $(1+\epsilon )$-approximate $k$-Median and $k$-Means in Euclidean space ${\mathbb{R}}^d$, using $\tilde{O}(kd\mathrm{poly}({\epsilon }^{-1}))$ space. This result significantly improves a recent $O(d\log n)$-approximation for $k$-Median [Gribelyuk, Lin, Woodruff, Yu, and Zhou, FOCS 2026], and is furthermore the first algorithm whose space is linear in $kd$, even in the oblivious (non-adaptive) setting. We develop several new techniques which may be of independent interest, including a new data-oblivious Euclidean primitive called hierarchical Lipschitz assignment, a robust dimensionality reduction for clustering, and a robust streaming algorithm for inner-product queries.