Faster DBScan and HDBScan in low-dimensional euclidean spaces

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

3 Citations (Scopus)


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.
Original languageEnglish
Title of host publicationISAAC 2017 : 28th International Symposium on Algorithms and Computation, 9-12 December 2017, Phuket, Thailand
EditorsTakeshi Tokuyama, Yoshio Okamoto
Place of PublicationDagstuhl
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Number of pages13
ISBN (Electronic)9783959770545
ISBN (Print)978-3-95977-054-5
Publication statusPublished - 1 Dec 2017
Event28th International Symposium on Algorithms and Computation (ISAAC 2017) - Phuket, Thailand
Duration: 9 Dec 201712 Dec 2017
Conference number: 28

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
ISSN (Print)1868-8969


Conference28th International Symposium on Algorithms and Computation (ISAAC 2017)
Abbreviated titleISAAC 2017
Internet address


  • Density-based clustering
  • Hierarchical clustering

Cite this