Differential Privacy for Clustering Under Continual Observation
This addresses privacy concerns for clustering in dynamic environments, such as streaming data, but is incremental as it builds on existing private clustering techniques.
The paper tackles the problem of privately clustering a dataset in ℝ^d under continual observation with insertions and deletions, achieving an ε-differentially private mechanism for k-means with additive error logarithmic in the number of updates and multiplicative error nearly matching non-private methods.
We consider the problem of clustering privately a dataset in $\mathbb{R}^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.