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 language | English |
---|---|
Title of host publication | ISAAC 2017 : 28th International Symposium on Algorithms and Computation, 9-12 December 2017, Phuket, Thailand |
Editors | Takeshi Tokuyama, Yoshio Okamoto |
Place of Publication | Dagstuhl |
Publisher | Schloss Dagstuhl - Leibniz-Zentrum für Informatik |
Number of pages | 13 |
ISBN (Electronic) | 9783959770545 |
ISBN (Print) | 978-3-95977-054-5 |
DOIs | |
Publication status | Published - 1 Dec 2017 |
Event | 28th International Symposium on Algorithms and Computation (ISAAC 2017) - Phuket, Thailand Duration: 9 Dec 2017 → 12 Dec 2017 Conference number: 28 http://aiat.in.th/isaac2017/ |
Publication series
Name | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|
Volume | 92 |
ISSN (Print) | 1868-8969 |
Conference
Conference | 28th International Symposium on Algorithms and Computation (ISAAC 2017) |
---|---|
Abbreviated title | ISAAC 2017 |
Country/Territory | Thailand |
City | Phuket |
Period | 9/12/17 → 12/12/17 |
Internet address |
Keywords
- Density-based clustering
- Hierarchical clustering