2024/05/03 by Abdulrahman Diaa, Diaa, Abdulrahman, Thomas Humphries +3 · 1 citation
Business, Management and Accounting · Computer Science · #Advanced Clustering Algorithms Research #Cryptography and Security (cs.CR) #Customer churn and segmentation #FOS: Computer and information sciences #Machine Learning (cs.LG) #Privacy-Preserving Technologies in Data
paper · pdf · doi:10.48550/arxiv.2405.02437
openalex publication_date 2024/05/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the problem of privacy-preserving k-means clustering in the horizontally federated setting. Existing federated approaches using secure computation suffer from substantial overheads and do not offer output privacy. At the same time, differentially private (DP) k-means algorithms either assume a trusted central curator or significantly degrade utility by adding noise in the local DP model. Naively combining the secure and central DP solutions results in a protocol with impractical overhead. Instead, our work provides enhancements to both the DP and secure computation components, resulting in a design that is faster, more private, and more accurate than previous work. By utilizing the computational DP model, we design a lightweight, secure aggregation-based approach that achieves five orders of magnitude speed-up over state-of-the-art related work. Furthermore, we not only maintain the utility of the state-of-the-art in the central model of DP, but we improve the utility further by designing a new DP clustering mechanism.