Online Differentially Private Consistent Clustering

We study differentially private (DP) $k$-means and $k$-median clustering in the online streaming setting. In this model, points arrive sequentially, and at each time step, we need to output a set of $k$ centers that optimizes the clustering objective for all points seen so far. We give a generic reduction that transforms the (sensitive) input stream into a private stream, which is a *semi-coreset* of the input stream. This implies that any (non-private) online clustering algorithm, run as a post-processing step, can achieve good utility for the original clustering objective. Our algorithm matches or improves upon the approximation ratio, space usage, and running time of existing algorithms (Dupr{\'{e}} la Tour, 2024; Epasto et al., 2026). A key aspect of our reduction is that it inherits desirable properties of the underlying non-private clustering algorithm, such as *consistency* (Lattanzi and Vassilvitskii, 2017)---a property not satisfied by previous DP algorithms.