Faster DBScan and HDBScan in low-dimensional euclidean spaces

M.T. de Berg; A. Ade Gunawan; M.J.M. Roeloffzen

doi:10.4230/LIPIcs.ISAAC.2017.25

Faster DBScan and HDBScan in low-dimensional euclidean spaces

M.T. de Berg
, A. Ade Gunawan
, M.J.M. Roeloffzen

Algorithms

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-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 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	https://doi.org/10.4230/LIPIcs.ISAAC.2017.25
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	http://aiat.in.th/isaac2017/

Keywords

Density-based clustering
Hierarchical clustering

Access to Document

10.4230/LIPIcs.ISAAC.2017.25

Cite this

de Berg, M. T., Ade Gunawan, A., & Roeloffzen, M. J. M. (2017). Faster DBScan and HDBScan in low-dimensional euclidean spaces. In T. Tokuyama, & Y. Okamoto (Eds.), ISAAC 2017 : 28th International Symposium on Algorithms and Computation, 9-12 December 2017, Phuket, Thailand Article 25 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 92). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ISAAC.2017.25

de Berg, M.T. ; Ade Gunawan, A. ; Roeloffzen, M.J.M. / Faster DBScan and HDBScan in low-dimensional euclidean spaces. ISAAC 2017 : 28th International Symposium on Algorithms and Computation, 9-12 December 2017, Phuket, Thailand. editor / Takeshi Tokuyama ; Yoshio Okamoto. Dagstuhl : Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. (Leibniz International Proceedings in Informatics, LIPIcs).

@inproceedings{eb14f03517a147219decb8b264917395,

title = "Faster DBScan and HDBScan in low-dimensional euclidean spaces",

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\textasciicircum{}2, irrespective of the scale parameter \textbackslash{}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. ",

keywords = "Density-based clustering, Hierarchical clustering",

author = "\{de Berg\}, M.T. and \{Ade Gunawan\}, A. and M.J.M. Roeloffzen",

year = "2017",

month = dec,

day = "1",

doi = "10.4230/LIPIcs.ISAAC.2017.25",

language = "English",

isbn = "978-3-95977-054-5",

series = "Leibniz International Proceedings in Informatics, LIPIcs",

publisher = "Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik",

editor = "Takeshi Tokuyama and Yoshio Okamoto",

booktitle = "ISAAC 2017 : 28th International Symposium on Algorithms and Computation, 9-12 December 2017, Phuket, Thailand",

note = "28th International Symposium on Algorithms and Computation (ISAAC 2017), ISAAC 2017 ; Conference date: 09-12-2017 Through 12-12-2017",

url = "http://aiat.in.th/isaac2017/",

}

de Berg, MT, Ade Gunawan, A & Roeloffzen, MJM 2017, Faster DBScan and HDBScan in low-dimensional euclidean spaces. in T Tokuyama & Y Okamoto (eds), ISAAC 2017 : 28th International Symposium on Algorithms and Computation, 9-12 December 2017, Phuket, Thailand., 25, Leibniz International Proceedings in Informatics, LIPIcs, vol. 92, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Dagstuhl, 28th International Symposium on Algorithms and Computation (ISAAC 2017), Phuket, Thailand, 9/12/17. https://doi.org/10.4230/LIPIcs.ISAAC.2017.25

Faster DBScan and HDBScan in low-dimensional euclidean spaces. / de Berg, M.T.; Ade Gunawan, A.; Roeloffzen, M.J.M.
ISAAC 2017 : 28th International Symposium on Algorithms and Computation, 9-12 December 2017, Phuket, Thailand. ed. / Takeshi Tokuyama; Yoshio Okamoto. Dagstuhl: Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. 25 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 92).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Faster DBScan and HDBScan in low-dimensional euclidean spaces

AU - de Berg, M.T.

AU - Ade Gunawan, A.

AU - Roeloffzen, M.J.M.

N1 - Conference code: 28

PY - 2017/12/1

Y1 - 2017/12/1

N2 - 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.

AB - 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.

KW - Density-based clustering

KW - Hierarchical clustering

UR - https://www.scopus.com/pages/publications/85038592915

U2 - 10.4230/LIPIcs.ISAAC.2017.25

DO - 10.4230/LIPIcs.ISAAC.2017.25

M3 - Conference contribution

SN - 978-3-95977-054-5

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - ISAAC 2017 : 28th International Symposium on Algorithms and Computation, 9-12 December 2017, Phuket, Thailand

A2 - Tokuyama, Takeshi

A2 - Okamoto, Yoshio

PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik

CY - Dagstuhl

T2 - 28th International Symposium on Algorithms and Computation (ISAAC 2017)

Y2 - 9 December 2017 through 12 December 2017

ER -

de Berg MT, Ade Gunawan A, Roeloffzen MJM. Faster DBScan and HDBScan in low-dimensional euclidean spaces. In Tokuyama T, Okamoto Y, editors, ISAAC 2017 : 28th International Symposium on Algorithms and Computation, 9-12 December 2017, Phuket, Thailand. Dagstuhl: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. 2017. 25. (Leibniz International Proceedings in Informatics, LIPIcs). doi: 10.4230/LIPIcs.ISAAC.2017.25

Faster DBScan and HDBScan in low-dimensional euclidean spaces

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this