Algorithms improve clustering accuracy with less memory in streaming data
Adversarially Robust Streaming Algorithms for $(k, z)$-Clustering
Data Structures and Algorithms
Summary
Clustering is a way to group similar points in space, but it can be hard to do accurately when data arrives in a stream and might be influenced by tricky or changing inputs. This paper presents new algorithms that find almost the best groupings for two common types of clustering, called k-Median and k-Means, while using much less computer memory than before. The authors also introduce new tools that help reduce data complexity and keep results reliable even if the input changes in adversarial ways. These improvements make streaming clustering more practical and robust in real-world conditions.
What this means in practice
- •For data engineers: Process streaming location data with memory-efficient methods that maintain accurate k-Median and k-Means clustering despite changing or adversarial inputs.
- •For database system developers: Implement robust streaming query engines that handle clustering queries accurately with low space usage and resistance to adaptive input changes.
Authors
Chengzhi Guo, Shaofeng H. C. Jiang, Robert Krauthgamer, David P. Woodruff, Shenghao Xie, Samson Zhou
Abstract
We design adversarially robust algorithms for dynamic geometric streams that $(1 + ε)$-approximate $k$-Median and $k$-Means in Euclidean space $\mathbb{R}^d$, using $\tilde{O}(kd \mathrm{poly}(ε^{-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.