Locating a Small Cluster Privately

Summary: New differentially private algorithm to locate small point clusters, enabling private identification of dense subsets and outlier removal. Relaxes sample-and-aggregate requirements to enable broader conversion of off-the-shelf analyses into differentially private versions. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1690
Venue: PODS
Year: 2016
Pagerank: 7.1990589e-05
Overall Rank: 3,693 | 74.67%
DOI: 10.1145/2902251.2902296

Incoming Non-self Citations Over Time

Authors

1. Kobbi Nissim (Ben Gurion University; Harvard University)
2. Uri Stemmer (Ben Gurion University)
3. Salil Vadhan (Harvard University)

BibTeX Citation

@inproceedings{nissim_pods16,
        address = {New York, NY, USA},
        series = {{PODS} '16},
        title = {{Locating a Small Cluster Privately}},
        url = {https://dl.acm.org/doi/10.1145/2902251.2902296},
        doi = {10.1145/2902251.2902296},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Nissim, Kobbi and Stemmer, Uri and Vadhan, Salil},
        year = {2016}
}

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,314	Optimal Differentially Private Algorithms for k-Means Clustering	2018	PODS	6.2688519e-05
6,353	Differentially Private Vertical Federated Clustering	2023	VLDB	5.9042628e-05
7,831	Differentially Private Hierarchical Heavy Hitters	2024	PODS	5.5357919e-05
9,830	PCOR: Private Contextual Outlier Release via Differentially Private Search	2021	SIGMOD	5.2125702e-05

Outgoing Citations (Sorted by Pagerank)

Showing 1 of 1 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
1,906	GUPT: Privacy Preserving Data Analysis Made Easy	2012	SIGMOD	9.5020196e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	244	On the Design and Quantification of Privacy Preserving Data Mining Algorithms	2001	PODS
2	3,143	Frequency Estimation under Local Differential Privacy	2021	VLDB
3	2,992	Pan-private Algorithms Via Statistics on Sketches	2011	PODS
4	5,555	Practical Differential Privacy via Grouping and Smoothing	2013	VLDB
5	7,500	Approximate DBSCAN under Differential Privacy	2025	SIGMOD
6	9,830	PCOR: Private Contextual Outlier Release via Differentially Private Search	2021	SIGMOD
7	12,537	Distribution-based Microdata Anonymization	2009	VLDB
8	10,313	Differentially Private Explanations for Clusters	2026	SIGMOD
9	5,314	Optimal Differentially Private Algorithms for k-Means Clustering	2018	PODS
10	3,110	Achieving Anonymity via Clustering	2006	PODS