Coresets for Euclidean Clustering Problems with Concentrated Geo-Privacy

Coresets are compact summaries of datasets such that models trained on a coreset can (provably) approximate those trained on the entire dataset. As such, they have been widely used to scale up clustering problems to massive data. In many real-world scenarios, clustering involves sensitive data, making the release of coresets subject to privacy concerns. Existing differentially private (DP) methods for coreset construction focus predominantly on the centralized model, while extending them to the local model of DP is still largely unexplored. In this paper, we study how to construct coresets for Euclidean clustering problems with concentrated geo-privacy (CGP), a local DP model that quantifies distinguishability based on the distance between data points as defined by a distance function (i.e., the Euclidean distance in our formulation). We first propose an algorithm to build coresets with CGP for the $1$-center problem (a.k.a. minimum enclosing ball, MEB) with a $(1+\gamma )$ relative approximation and an additive error. We then extend the scheme to the $k$-center problem with any $k=O(1)$. Furthermore, we propose constructing approximate coresets with CGP for general $(k,z)$-clustering (of which $k$-median and $k$-means are special cases when $z=1$ and $z=2$, respectively). We implement our algorithms and conduct extensive experiments to demonstrate their effectiveness in practice.