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: 5006
Venue: SIGMOD
Year: 2015
Pagerank: 0.00015001792
Overall Rank: 961 | 93.32%
DOI: 10.1145/2723372.2737792

Incoming Non-self Citations Over Time

Authors

1. Junhao Gan
2. Yufei Tao

Incoming Citations (Sorted by Pagerank)

Showing 17 of 17 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,635	NG-DBSCAN: Scalable Density-Based Clustering for Arbitrary Data	2017	VLDB	8.4045788e-05
3,264	Dynamic Density Based Clustering	2017	SIGMOD	7.3094408e-05
3,295	RP-DBSCAN: A Superfast Parallel DBSCAN Algorithm Based on Random Partitioning	2018	SIGMOD	7.2598552e-05
4,911	Unsupervised Contextual Anomaly Detection for Database Systems	2022	SIGMOD	5.8328593e-05
5,324	Clustering Stream Data by Exploring the Evolution of Density Mountain	2018	VLDB	5.5691645e-05
5,996	A New Sparse Data Clustering Method Based On Frequent Items	2023	SIGMOD	5.2415551e-05
6,125	DenForest: Enabling Fast Deletion in Incremental Density-Based Clustering over Sliding Windows	2022	SIGMOD	5.1987868e-05
7,480	Towards Metric DBSCAN: Exact, Approximate, and Streaming Algorithms	2024	SIGMOD	4.7180617e-05
7,871	ConnectIt: A Framework for Static and Incremental Parallel Graph Connectivity Algorithms	2021	VLDB	4.6308128e-05
8,431	Spade: A Real-Time Fraud Detection Framework on Evolving Graphs	2023	VLDB	4.5154339e-05
9,235	ThriftLLM: On Cost-Effective Selection of Large Language Models for Classification Queries	2025	VLDB	4.3690661e-05
10,379	In-Database Time Series Clustering	2025	SIGMOD	4.1945683e-05
10,470	Approximate DBSCAN under Differential Privacy	2025	SIGMOD	4.1945683e-05
11,045	Ensemble Clustering based on Meta-Learning and Hyperparameter Optimization	2024	VLDB	4.1945683e-05
11,181	Fast Density-Based Clustering: Geometric Approach	2023	SIGMOD	4.1945683e-05
11,335	Faster and Better Solution to Embed Lp Metrics by Tree Metrics	2022	SIGMOD	4.1945683e-05
11,466	Fast Density-Peaks Clustering: Multicore-based Parallelization Approach	2021	SIGMOD	4.1945683e-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
270	OPTICS: Ordering Points To Identify the Clustering Structure	1999	SIGMOD	0.00029505642
1,097	STING : A Statistical Information Grid Approach to Spatial Data Mining	1997	VLDB	0.00014119975
1,718	Swarm: Mining Relaxed Temporal Moving Object Clusters	2010	VLDB	0.00010789285
4,162	Computing Clusters of Correlation Connected Objects	2004	SIGMOD	6.3937203e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
10,971	Settling Time vs. Accuracy Tradeoffs for Clustering Big Data	2024	SIGMOD	4.1945683e-05
11,466	Fast Density-Peaks Clustering: Multicore-based Parallelization Approach	2021	SIGMOD	4.1945683e-05
9,924	On Saving Outliers for Better Clustering over Noisy Data	2021	SIGMOD	4.2544238e-05
1,816	Incremental Clustering for Mining in a Data Warehousing Environment	1998	VLDB	0.0001045313
2,635	NG-DBSCAN: Scalable Density-Based Clustering for Arbitrary Data	2017	VLDB	8.4045788e-05
11,181	Fast Density-Based Clustering: Geometric Approach	2023	SIGMOD	4.1945683e-05
10,470	Approximate DBSCAN under Differential Privacy	2025	SIGMOD	4.1945683e-05
3,264	Dynamic Density Based Clustering	2017	SIGMOD	7.3094408e-05
5,417	Theoretically-Efficient and Practical Parallel DBSCAN	2020	SIGMOD	5.5194222e-05
7,480	Towards Metric DBSCAN: Exact, Approximate, and Streaming Algorithms	2024	SIGMOD	4.7180617e-05