Differentially-Private Sublinear-Time Clustering

2021/12/27 by Jeremiah Blocki, Blocki, Jeremiah, Elena Grigorescu +3
Computer Science · Mathematics · Medicine · #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #HIV, Drug Use, Sexual Risk #Machine Learning (cs.LG) #Privacy-Preserving Technologies in Data #Statistical Methods and Bayesian Inference

paper · pdf · doi:10.48550/arxiv.2112.13751

openalex publication_date 2021/12/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Clustering is an essential primitive in unsupervised machine learning. We bring forth the problem of sublinear-time differentially-private clustering as a natural and well-motivated direction of research. We combine the k-means and k-median sublinear-time results of Mishra et al. (SODA, 2001) and of Czumaj and Sohler (Rand. Struct. and Algorithms, 2007) with recent results on private clustering of Balcan et al. (ICML 2017), Gupta et al. (SODA, 2010) and Ghazi et al. (NeurIPS, 2020) to obtain sublinear-time private k-means and k-median algorithms via subsampling. We also investigate the privacy benefits of subsampling for group privacy.

Related

• Differentially Private Clustering in Data Streams
• k-Means SubClustering: A Differentially Private Algorithm with Improved Clustering Quality
• Differential privacy and Sublinear time are incompatible sometimes
• Scalable Differentially Private Clustering via Hierarchically Separated Trees
• Differentially Private Clustering via Maximum Coverage