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: hce11876d1b53e316
Venue: PODS
Year: 2018
Pagerank: 6.1254857e-05
Overall Rank: 5,443 | 63.42%
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,473	Differentially Private Vertical Federated Clustering	2023	VLDB	5.7713471e-05
7,648	Approximate DBSCAN under Differential Privacy	2025	SIGMOD	5.4746904e-05
11,497	k-Clustering with Comparison and Distance Oracles	2024	PODS	4.9769913e-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
520	Practical Privacy: The SuLQ Framework	2005	PODS	0.00016931295
3,767	Locating a Small Cluster Privately	2016	PODS	7.0344148e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	11,533	Settling Time vs. Accuracy Tradeoffs for Clustering Big Data	2024	SIGMOD
2	9,726	Optimal Bounds for Private Minimum Spanning Trees via Input Perturbation	2025	PODS
3	4,462	Solving k-center Clustering (with Outliers) in MapReduce and Streaming, almost as Accurately as Sequentially	2019	VLDB
4	11,498	Improved Approximation Algorithms for Relational Clustering	2024	PODS
5	13,060	k-Means Projective Clustering	2004	PODS
6	3,767	Locating a Small Cluster Privately	2016	PODS
7	11,497	k-Clustering with Comparison and Distance Oracles	2024	PODS
8	2,307	Approximation Algorithms for Clustering Uncertain Data	2008	PODS
9	9,756	Local Search Methods for k-Means with Outliers	2017	VLDB
10	6,473	Differentially Private Vertical Federated Clustering	2023	VLDB