Approximate DBSCAN under Differential Privacy

Summary: Spans-based DP definition for DP-DBSCAN; argues spans aid visualization and classification over labels. Linear-time DP algorithm achieves sandwich quality in constant dimensions with matching lower bounds; includes a pure-DP histogram primitive and validation. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 7265
Venue: SIGMOD
Year: 2025
Pagerank: 5.6029996e-05
Overall Rank: 7,500 | 48.55%
DOI: 10.1145/3725265

Incoming Non-self Citations Over Time

Authors

1. Yuan Qiu (CNRS)
2. Ke Yi (Hong Kong University of Science and Technology)

BibTeX Citation

@inproceedings{qiu_sigmod25,
        title = {{Approximate DBSCAN under Differential Privacy}},
        author = {Qiu, Yuan and Yi, Ke},
        series = {{SIGMOD} '25},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3725265},
        url = {https://dl.acm.org/doi/10.1145/3725265},
        year = {2025}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,164	Optimal Pure Differentially Private Sparse Histograms in Deterministic Linear Time	2026	PODS	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
962	DBSCAN Revisited: Mis-Claim, Un-Fixability, and Approximation	2015	SIGMOD	0.00012936472
1,230	No Free Lunch in Data Privacy	2011	SIGMOD	0.00011572271
3,854	Better Differentially Private Approximate Histograms and Heavy Hitters using the Misra-Gries Sketch	2023	PODS	7.0723123e-05
5,314	Optimal Differentially Private Algorithms for k-Means Clustering	2018	PODS	6.2688519e-05
8,070	Towards Metric DBSCAN: Exact, Approximate, and Streaming Algorithms	2024	SIGMOD	5.4938502e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,992	Pan-private Algorithms Via Statistics on Sketches	2011	PODS
2	10,313	Differentially Private Explanations for Clusters	2026	SIGMOD
3	3,234	RP-DBSCAN: A Superfast Parallel DBSCAN Algorithm Based on Random Partitioning	2018	SIGMOD
4	2,556	NG-DBSCAN: Scalable Density-Based Clustering for Arbitrary Data	2017	VLDB
5	11,387	Fast Density-Based Clustering: Geometric Approach	2023	SIGMOD
6	10,195	Approximate DBSCAN via Density-Biased Sampling and Kernel Density Estimation	2026	SIGMOD
7	3,020	Dynamic Density Based Clustering	2017	SIGMOD
8	5,294	Theoretically-Efficient and Practical Parallel DBSCAN	2020	SIGMOD
9	962	DBSCAN Revisited: Mis-Claim, Un-Fixability, and Approximation	2015	SIGMOD
10	8,070	Towards Metric DBSCAN: Exact, Approximate, and Streaming Algorithms	2024	SIGMOD