文章基本信息

标题：Faster DBScan and HDBScan in Low-Dimensional Euclidean Spaces
本地全文：下载
作者：Mark de Berg ; Ade Gunawan ; Marcel Roeloffzen 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：92
页码：25:1-25:13
DOI：10.4230/LIPIcs.ISAAC.2017.25
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Density-based clustering; hierarchical clustering