Faster DBScan and HDBScan in low-dimensional euclidean spaces

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

3 Citaten (Scopus)

Samenvatting

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.
Originele taal-2Engels
TitelISAAC 2017 : 28th International Symposium on Algorithms and Computation, 9-12 December 2017, Phuket, Thailand
RedacteurenTakeshi Tokuyama, Yoshio Okamoto
Plaats van productieDagstuhl
UitgeverijSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Aantal pagina's13
ISBN van elektronische versie9783959770545
ISBN van geprinte versie978-3-95977-054-5
DOI's
StatusGepubliceerd - 1 dec 2017
Evenement28th International Symposium on Algorithms and Computation (ISAAC 2017) - Phuket, Thailand
Duur: 9 dec 201712 dec 2017
Congresnummer: 28
http://aiat.in.th/isaac2017/

Publicatie series

NaamLeibniz International Proceedings in Informatics, LIPIcs
Volume92
ISSN van geprinte versie1868-8969

Congres

Congres28th International Symposium on Algorithms and Computation (ISAAC 2017)
Verkorte titelISAAC 2017
Land/RegioThailand
StadPhuket
Periode9/12/1712/12/17
Internet adres

Citeer dit