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: hf97dc3e71efe3e1d
Venue: PODS
Year: 2016
Pagerank: 7.0377464e-05
Overall Rank: 3,765 | 74.69%
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,438	Optimal Differentially Private Algorithms for k-Means Clustering	2018	PODS	6.1283868e-05
6,471	Differentially Private Vertical Federated Clustering	2023	VLDB	5.7740805e-05
7,992	Differentially Private Hierarchical Heavy Hitters	2024	PODS	5.4115836e-05
10,017	PCOR: Private Contextual Outlier Release via Differentially Private Search	2021	SIGMOD	5.0956141e-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,955	GUPT: Privacy Preserving Data Analysis Made Easy	2012	SIGMOD	9.3176117e-05

Semantically Similar Papers

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