Online Differentially Private Clustering: Private to Non-Private Reduction
Abstract
We study differentially private k-mean/median clustering in the online streaming setting where a point arrive at each time step and we need to output a set of k centers that optimize the k-mean/median objective of all the points so far. We give a generic transformation that turns the sensitive stream into a differentially private stream, which is a semi-coreset of the original stream and allows us to run any (non-private) online clustering algorithm as a post-processing step. Our algorithm is efficient in terms of errors, space and running time compared to existing algorithms (Epasto et al., 2023; Dupr{\'{e}} la Tour, 2024). Furthermore, our reduction allows us to inherit properties of the non-private clustering, such as consistency (Lattanzi and Vassilvitski, 2017), which was not satisfied by previous DP algorithms.
Research Areas
