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.