Differential Privacy for Clustering Under Continual Observation

We consider the problem of clustering privately a dataset in ℝd that undergoes both insertion and deletion of points. Specifically, we give an varepsilon-differentially private clustering mechanism for the k-means objective under continual observation. This is the first approximation algorithm for that problem with an additive error that depends only logarithmically in the number T of updates. The multiplicative error is almost the same as non privately. To do so we show how to perform dimension reduction under continual observation and combine it with a differentially private greedy approximation algorithm for k-means. We also partially extend our results to the k-median problem.