Faster DBScan and HDBScan in low-dimensional Euclidean spaces

Mark de Berg (Corresponding author), Ade Gunawan, Marcel Roeloffzen (Corresponding author)

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

6 Citaten (Scopus)
210 Downloads (Pure)


We present a new algorithm for the widely used density-based clustering method dbscan. For a set of n points in 2 our algorithm computes the dbscan-clustering in O(nlog n) time, irrespective of the scale parameter (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 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.

Originele taal-2Engels
Pagina's (van-tot)21-47
Aantal pagina's27
TijdschriftInternational Journal of Computational Geometry and Applications
Nummer van het tijdschrift1
StatusGepubliceerd - 1 mrt. 2019


Duik in de onderzoeksthema's van 'Faster DBScan and HDBScan in low-dimensional Euclidean spaces'. Samen vormen ze een unieke vingerafdruk.

Citeer dit