Differentially Private Clustering in Data Streams

Alessandro Epasto, Tamalika Mukherjee, Peilin Zhong
Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, PMLR 300:1360-1368, 2026.

Abstract

Clustering tasks such as $k$-means and $k$-median are central in unsupervised learning, and streaming algorithms for these tasks are widely used to handle large or evolving datasets. When applied in sensitive domains, however, such algorithms must also provide rigorous privacy guarantees. In this work, we provide the first differentially private (DP) algorithms for $k$-means and $k$-median clustering of $d$-dimensional Euclidean data points over a stream of length at most $T$, using space that is sublinear in $T$, in the continual release setting where the algorithm is required to output a clustering at every timestep. We achieve (1) an $O(1)$-multiplicative approximation with $O(k^{1.5} poly(d, \log T))$ space and $poly(k,d,\log T)$ additive error, or (2) a $(1+\gamma)$-multiplicative approximation with $O_\gamma(poly(k, 2^{O_\gamma(d)}, \log T))$ space for any $\gamma>0$, with additive error $poly(k, 2^{O_\gamma(d)}, \log T)$. Our main technical contribution is a DP clustering framework for data streams that only requires an offline DP coreset or clustering algorithm as a blackbox.

Cite this Paper

BibTeX
@InProceedings{pmlr-v300-epasto26a, title = { Differentially Private Clustering in Data Streams }, author = {Epasto, Alessandro and Mukherjee, Tamalika and Zhong, Peilin}, booktitle = {Proceedings of The 29th International Conference on Artificial Intelligence and Statistics}, pages = {1360--1368}, year = {2026}, editor = {Khan, Emtiyaz and Li, Yingzhen and Solin, Arno and Ramdas, Aaditya}, volume = {300}, series = {Proceedings of Machine Learning Research}, month = {02--05 May}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v300/main/assets/epasto26a/epasto26a.pdf}, url = {https://proceedings.mlr.press/v300/epasto26a.html}, abstract = { Clustering tasks such as $k$-means and $k$-median are central in unsupervised learning, and streaming algorithms for these tasks are widely used to handle large or evolving datasets. When applied in sensitive domains, however, such algorithms must also provide rigorous privacy guarantees. In this work, we provide the first differentially private (DP) algorithms for $k$-means and $k$-median clustering of $d$-dimensional Euclidean data points over a stream of length at most $T$, using space that is sublinear in $T$, in the continual release setting where the algorithm is required to output a clustering at every timestep. We achieve (1) an $O(1)$-multiplicative approximation with $O(k^{1.5} poly(d, \log T))$ space and $poly(k,d,\log T)$ additive error, or (2) a $(1+\gamma)$-multiplicative approximation with $O_\gamma(poly(k, 2^{O_\gamma(d)}, \log T))$ space for any $\gamma>0$, with additive error $poly(k, 2^{O_\gamma(d)}, \log T)$. Our main technical contribution is a DP clustering framework for data streams that only requires an offline DP coreset or clustering algorithm as a blackbox. } }
Endnote
%0 Conference Paper %T Differentially Private Clustering in Data Streams %A Alessandro Epasto %A Tamalika Mukherjee %A Peilin Zhong %B Proceedings of The 29th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2026 %E Emtiyaz Khan %E Yingzhen Li %E Arno Solin %E Aaditya Ramdas %F pmlr-v300-epasto26a %I PMLR %P 1360--1368 %U https://proceedings.mlr.press/v300/epasto26a.html %V 300 %X Clustering tasks such as $k$-means and $k$-median are central in unsupervised learning, and streaming algorithms for these tasks are widely used to handle large or evolving datasets. When applied in sensitive domains, however, such algorithms must also provide rigorous privacy guarantees. In this work, we provide the first differentially private (DP) algorithms for $k$-means and $k$-median clustering of $d$-dimensional Euclidean data points over a stream of length at most $T$, using space that is sublinear in $T$, in the continual release setting where the algorithm is required to output a clustering at every timestep. We achieve (1) an $O(1)$-multiplicative approximation with $O(k^{1.5} poly(d, \log T))$ space and $poly(k,d,\log T)$ additive error, or (2) a $(1+\gamma)$-multiplicative approximation with $O_\gamma(poly(k, 2^{O_\gamma(d)}, \log T))$ space for any $\gamma>0$, with additive error $poly(k, 2^{O_\gamma(d)}, \log T)$. Our main technical contribution is a DP clustering framework for data streams that only requires an offline DP coreset or clustering algorithm as a blackbox.
APA
Epasto, A., Mukherjee, T. & Zhong, P.. (2026). Differentially Private Clustering in Data Streams . Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 300:1360-1368 Available from https://proceedings.mlr.press/v300/epasto26a.html.

Related Material