DBSCAN Revisited: Mis-Claim, Un-Fixability, and Approximation

Summary: Revisits DBSCAN, debunking the KDD'96 O(n log n) claim; real worst-case is O(n^2), with a 2D fix yielding O(n log n) and a d≥3 Omega(n^(4/3)) lower bound. Proposes rho-approximate DBSCAN, achieving O(n) expected time in any dimension at bounded inaccuracy, suggesting it as the practical replacement for big data. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: he866b913e3693e01
Venue: SIGMOD
Year: 2015
Pagerank: 0.00012621584
Overall Rank: 992 | 93.36%
DOI: 10.1145/2723372.2737792

Incoming Non-self Citations Over Time

Authors

1. Junhao Gan (Chinese University of Hong Kong)
2. Yufei Tao (Chinese University of Hong Kong)

BibTeX Citation

@inproceedings{gan_sigmod15,
        title = {{DBSCAN Revisited: Mis-Claim, Un-Fixability, and Approximation}},
        author = {Gan, Junhao and Tao, Yufei},
        series = {{SIGMOD} '15},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/2723372.2737792},
        url = {https://dl.acm.org/doi/10.1145/2723372.2737792},
        year = {2015}
}

Incoming Citations (Sorted by Pagerank)

Showing 19 of 19 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,623	NG-DBSCAN: Scalable Density-Based Clustering for Arbitrary Data	2017	VLDB	8.196568e-05
3,070	Dynamic Density Based Clustering	2017	SIGMOD	7.6675081e-05
3,314	RP-DBSCAN: A Superfast Parallel DBSCAN Algorithm Based on Random Partitioning	2018	SIGMOD	7.4156999e-05
5,172	Unsupervised Contextual Anomaly Detection for Database Systems	2022	SIGMOD	6.2318859e-05
5,461	Clustering Stream Data by Exploring the Evolution of Density Mountain	2018	VLDB	6.1045744e-05
5,625	DenForest: Enabling Fast Deletion in Incremental Density-Based Clustering over Sliding Windows	2022	SIGMOD	6.0454405e-05
7,121	A New Sparse Data Clustering Method Based On Frequent Items	2023	SIGMOD	5.580601e-05
7,370	Spade: A Real-Time Fraud Detection Framework on Evolving Graphs	2023	VLDB	5.5258876e-05
7,662	Approximate DBSCAN under Differential Privacy	2025	SIGMOD	5.4565877e-05
7,986	ConnectIt: A Framework for Static and Incremental Parallel Graph Connectivity Algorithms	2021	VLDB	5.3960574e-05
8,263	Towards Metric DBSCAN: Exact, Approximate, and Streaming Algorithms	2024	SIGMOD	5.3502905e-05
8,320	ThriftLLM: On Cost-Effective Selection of Large Language Models for Classification Queries	2025	VLDB	5.3404439e-05
10,489	Approximate DBSCAN via Density-Biased Sampling and Kernel Density Estimation	2026	SIGMOD	4.9605343e-05
10,820	FB*: A Compact Index for Efficient and Exact Density-based Clustering	2026	VLDB	4.9605343e-05
11,178	In-Database Time Series Clustering	2025	SIGMOD	4.9605343e-05
11,639	Ensemble Clustering based on Meta-Learning and Hyperparameter Optimization	2024	VLDB	4.9605343e-05
11,754	Fast Density-Based Clustering: Geometric Approach	2023	SIGMOD	4.9605343e-05
11,893	Faster and Better Solution to Embed Lp Metrics by Tree Metrics	2022	SIGMOD	4.9605343e-05
12,021	Fast Density-Peaks Clustering: Multicore-based Parallelization Approach	2021	SIGMOD	4.9605343e-05

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
300	OPTICS: Ordering Points To Identify the Clustering Structure	1999	SIGMOD	0.00021743411
1,313	STING: A Statistical Information Grid Approach to Spatial Data Mining	1997	VLDB	0.00011058121
1,794	Swarm: Mining Relaxed Temporal Moving Object Clusters	2010	VLDB	9.6147752e-05
5,000	Computing Clusters of Correlation Connected Objects	2004	SIGMOD	6.3080199e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	10,302	On Saving Outliers for Better Clustering over Noisy Data	2021	SIGMOD
2	12,021	Fast Density-Peaks Clustering: Multicore-based Parallelization Approach	2021	SIGMOD
3	1,948	Incremental Clustering for Mining in a Data Warehousing Environment	1998	VLDB
4	2,623	NG-DBSCAN: Scalable Density-Based Clustering for Arbitrary Data	2017	VLDB
5	10,489	Approximate DBSCAN via Density-Biased Sampling and Kernel Density Estimation	2026	SIGMOD
6	11,754	Fast Density-Based Clustering: Geometric Approach	2023	SIGMOD
7	7,662	Approximate DBSCAN under Differential Privacy	2025	SIGMOD
8	3,070	Dynamic Density Based Clustering	2017	SIGMOD
9	5,438	Theoretically-Efficient and Practical Parallel DBSCAN	2020	SIGMOD
10	8,263	Towards Metric DBSCAN: Exact, Approximate, and Streaming Algorithms	2024	SIGMOD