Streaming algorithms for computing coresets and $k$-median clustering in the Hamming space

Abstract

Clustering is one of the most fundamental tools in data analysis, allowing large datasets to be summarized by a small number of representative points. Given a metric space $(\mathcal{X},d)$ and a set $S$ of $n$ points in this space, the continuous $k$-median clustering problem asks to find a set $C$ of $k$ points that minimizes the objective function ${\sum }_{s\in S}d(s,C)$. When $\mathcal{X}={\Sigma }^{\ell }$ is the set of strings of length $\ell$ and $d$ is the Hamming distance, the continuous $k$-median clustering problem is known to be W[1]-hard when parameterized by $k$. In this work, we present the first $(1+\epsilon )$-approximation algorithm for this problem with FPT runtime $2^{\mathrm{poly}({\epsilon }^{-1},k)}\cdot n\ell \mathrm{polylog}n$. An additional feature of the algorithm is that it can be implemented in streaming, requiring only ${\tilde{O}}_{\epsilon }(\ell k+k^2)$ space. As an auxiliary tool of independent interest, we show the first streaming algorithm for computing an $\epsilon$-coreset for continuous $k$-median clustering under the Hamming

Accepted to WAOA 2026