When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2017.25
URN: urn:nbn:de:0030-drops-82102
URL: http://drops.dagstuhl.de/opus/volltexte/2017/8210/
 Go to the corresponding LIPIcs Volume Portal

### Faster DBScan and HDBScan in Low-Dimensional Euclidean Spaces

 pdf-format:

### Abstract

We present a new algorithm for the widely used density-based clustering method DBScan. Our algorithm computes the DBScan-clustering in O(n log n) time in R^2, irrespective of the scale parameter \eps, but assuming the second parameter MinPts is set to a fixed constant, as is the case in practice. We also present an O(n log n) randomized algorithm for HDBScan in the plane---HDBScans 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.

### BibTeX - Entry

```@InProceedings{deberg_et_al:LIPIcs:2017:8210,
author =	{Mark de Berg and Ade Gunawan and Marcel Roeloffzen},
title =	{{Faster DBScan and HDBScan in Low-Dimensional Euclidean Spaces}},
booktitle =	{28th International Symposium on Algorithms and Computation (ISAAC 2017)},
pages =	{25:1--25:13},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-054-5},
ISSN =	{1868-8969},
year =	{2017},
volume =	{92},
editor =	{Yoshio Okamoto and Takeshi Tokuyama},
publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},