Optimal Differentially Private Algorithms for k-Means Clustering

Summary: Gives a polynomial-time private k-means algorithm attaining O(φ²) Wasserstein error on sufficiently well-separated data, independent of ε, k, and d, with a matching Ω(φ²) lower bound. Also provides a bounded-d private local-search additive approximation. (summarized by gpt-5.6-luna on Jul 26 2026)

Paper ID: 1756
Venue: PODS
Year: 2018
Pagerank: 6.2688519e-05
Overall Rank: 5,314 | 63.55%
DOI: 10.1145/3196959.3196977

Incoming Non-self Citations Over Time

Authors

1. Zhiyi Huang (University of Hong Kong)
2. Jinyan Liu (University of Hong Kong)

BibTeX Citation

@inproceedings{huang_pods18,
        address = {New York, NY, USA},
        series = {{PODS} '18},
        title = {{Optimal Differentially Private Algorithms for k-Means Clustering}},
        url = {https://dl.acm.org/doi/10.1145/3196959.3196977},
        doi = {10.1145/3196959.3196977},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Huang, Zhiyi and Liu, Jinyan},
        year = {2018}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,353	Differentially Private Vertical Federated Clustering	2023	VLDB	5.9042628e-05
7,500	Approximate DBSCAN under Differential Privacy	2025	SIGMOD	5.6029996e-05
11,143	k-Clustering with Comparison and Distance Oracles	2024	PODS	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 2 of 2 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
510	Practical Privacy: The SuLQ Framework	2005	PODS	0.00017220509
3,693	Locating a Small Cluster Privately	2016	PODS	7.1990589e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	11,184	Settling Time vs. Accuracy Tradeoffs for Clustering Big Data	2024	SIGMOD
2	9,538	Optimal Bounds for Private Minimum Spanning Trees via Input Perturbation	2025	PODS
3	4,366	Solving k-center Clustering (with Outliers) in MapReduce and Streaming, almost as Accurately as Sequentially	2019	VLDB
4	11,144	Improved Approximation Algorithms for Relational Clustering	2024	PODS
5	12,764	k-Means Projective Clustering	2004	PODS
6	3,693	Locating a Small Cluster Privately	2016	PODS
7	11,143	k-Clustering with Comparison and Distance Oracles	2024	PODS
8	2,253	Approximation Algorithms for Clustering Uncertain Data	2008	PODS
9	9,575	Local Search Methods for k-Means with Outliers	2017	VLDB
10	6,353	Differentially Private Vertical Federated Clustering	2023	VLDB