# DBSCAN++: Towards fast and scalable density clustering

arXiv: https://arxiv.org/abs/1810.13105 · HTML: https://mlsanity.com/paper/1810.13105/

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 Oct 2018.

## Built on by (most cited first, 20 of 20)

- [MeanShift++: Extremely Fast Mode-Seeking With Applications to Segmentation and Object Tracking](https://mlsanity.com/paper/2104.00303/) (2021)
- [Automatic Controllable Colorization via Imagination](https://mlsanity.com/paper/2404.05661/) (2024)
- [Fast and explainable clustering based on sorting](https://mlsanity.com/paper/2202.01456/) (2022)
- [Fast Density Estimation for Density-based Clustering Methods](https://mlsanity.com/paper/2109.11383/) (2021)
- [GridShift: A Faster Mode-seeking Algorithm for Image Segmentation and Object Tracking](https://mlsanity.com/paper/2206.02200/) (2022)
- [GBHT: Gradient Boosting Histogram Transform for Density Estimation](https://mlsanity.com/paper/2106.05738/) (2021)
- [Simple, Scalable and Effective Clustering via One-Dimensional Projections](https://mlsanity.com/paper/2310.16752/) (2023)
- [UniForCE: The Unimodality Forest Method for Clustering and Estimation of the Number of Clusters](https://mlsanity.com/paper/2312.11323/) (2023)
- [Learned Accelerator Framework for Angular-Distance-Based High-Dimensional DBSCAN](https://mlsanity.com/paper/2302.03136/) (2023)
- [SDC-HSDD-NDSA: Structure Detecting Cluster by Hierarchical Secondary Directed Differential with Normalized Density and Self-Adaption](https://mlsanity.com/paper/2307.00677/) (2023)
- [Symbolic Density Estimation: A Decompositional Approach](https://mlsanity.com/paper/2603.27955/) (2026)
- [Bagged k-Distance for Mode-Based Clustering Using the Probability of Localized Level Sets](https://mlsanity.com/paper/2210.09786/) (2022)
- [Scalable Density-based Clustering with Random Projections](https://mlsanity.com/paper/2402.15679/) (2024)
- [Cooperation and Federation in Distributed Radar Point Cloud Processing](https://mlsanity.com/paper/2405.01995/) (2024)
- [Model-free Estimation of Latent Structure via Multiscale Nonparametric Maximum Likelihood](https://mlsanity.com/paper/2410.22248/) (2024)
- [Guaranteed Recovery of Unambiguous Clusters](https://mlsanity.com/paper/2501.13093/) (2025)
- [Almost Linear Time Consistent Mode Estimation and Quick Shift Clustering](https://mlsanity.com/paper/2503.07995/) (2025)
- [Dynamic DBSCAN with Euler Tour Sequences](https://mlsanity.com/paper/2503.08246/) (2025)
- [Scalable Varied-Density Clustering via Graph Propagation](https://mlsanity.com/paper/2508.02989/) (2025)
- [Towards Robust and Scalable Density-based Clustering via Graph Propagation](https://mlsanity.com/paper/2605.00390/) (2026)

## Abstract (arXiv)

DBSCAN is a classical density-based clustering procedure with tremendous practical relevance. However, DBSCAN implicitly needs to compute the empirical density for each sample point, leading to a quadratic worst-case time complexity, which is too slow on large datasets. We propose DBSCAN++, a simple modification of DBSCAN which only requires computing the densities for a chosen subset of points. We show empirically that, compared to traditional DBSCAN, DBSCAN++ can provide not only competitive performance but also added robustness in the bandwidth hyperparameter while taking a fraction of the runtime. We also present statistical consistency guarantees showing the trade-off between computational cost and estimation rates. Surprisingly, up to a certain point, we can enjoy the same estimation rates while lowering computational cost, showing that DBSCAN++ is a sub-quadratic algorithm that attains minimax optimal rates for level-set estimation, a quality that may be of independent interest.