# Faster DB-scan and HDB-scan in Low-Dimensional Euclidean Spaces

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Feb 2017.

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

- [Fast Parallel Algorithms for Euclidean Minimum Spanning Tree and Hierarchical Spatial Clustering](https://mlsanity.com/paper/2104.01126/) (2021)
- [Scalable Density-based Clustering with Random Projections](https://mlsanity.com/paper/2402.15679/) (2024)
- [SPINEX-Clustering: Similarity-based Predictions with Explainable Neighbors Exploration for Clustering Problems](https://mlsanity.com/paper/2407.07222/) (2024)
- [Scalable Varied-Density Clustering via Graph Propagation](https://mlsanity.com/paper/2508.02989/) (2025)

## Abstract (arXiv)

We present a new algorithm for the widely used density-based clustering method DBscan. Our algorithm computes the DBscan-clustering in O(nlog n) time in ℝ2, irrespective of the scale parameter varepsilon (and assuming the second parameter MinPts is set to a fixed constant, as is the case in practice). Experiments show that the new algorithm is not only fast in theory, but that a slightly simplified version is competitive in practice and much less sensitive to the choice of varepsilon than the original DBscan algorithm. We also present an O(nlog n) randomized algorithm for HDBscan in the plane---HDBscan is a hierarchical version of DBscan introduced recently---and we show how to compute an approximate version of HDBscan in near-linear time in any fixed dimension.