Faster DBScan and HDBScan in low-dimensional euclidean spaces

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

3 Citations (Scopus)

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.
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
DOIs
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
http://aiat.in.th/isaac2017/

Publication series

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

Conference

Conference28th International Symposium on Algorithms and Computation (ISAAC 2017)
Abbreviated titleISAAC 2017
CountryThailand
CityPhuket
Period9/12/1712/12/17
Internet address

Keywords

  • Density-based clustering
  • Hierarchical clustering

Cite this