# Density Level Set Estimation on Manifolds with DBSCAN

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Mar 2017.

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

- [ContCommRTD: A Distributed Content-based Misinformation-aware Community Detection System for Real-Time Disaster Reporting](https://mlsanity.com/paper/2301.12984/) (2023)
- [Block-Diagonal Guided DBSCAN Clustering](https://mlsanity.com/paper/2404.01341/) (2024)
- [Active Covering](https://mlsanity.com/paper/2106.02552/) (2021)
- [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)
- [Guaranteed Recovery of Unambiguous Clusters](https://mlsanity.com/paper/2501.13093/) (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)

We show that DBSCAN can estimate the connected components of the λ-density level set  x : f(x) ≥ λ given n i.i.d. samples from an unknown density f. We characterize the regularity of the level set boundaries using parameter β > 0 and analyze the estimation error under the Hausdorff metric. When the data lies in ℝD we obtain a rate of widetildeO(n-1/(2β + D)), which matches known lower bounds up to logarithmic factors. When the data lies on an embedded unknown d-dimensional manifold in ℝD, then we obtain a rate of widetildeO(n^-1/(2β + d· max1, β )). Finally, we provide adaptive parameter tuning in order to attain these rates with no a priori knowledge of the intrinsic dimension, density, or β.