Faster DBScan and HDBscan in low-dimensional Euclidean spaces

DOI10.4230/LIPICS.ISAAC.2017.25MaRDI QIDQ5136243zbMATH OpenOpenAlexFDO

Authors Ade Gunawan, Marcel Roeloffzen, Mark de Berg

Publication date 25 November 2020

Full work available at URL https://arxiv.org/abs/1702.08607

zbMATH Keywords

hierarchical clusteringdensity-based clustering

Mathematics Subject Classification ID

Randomized algorithms (68W20) Analysis of algorithms (68W40) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: We present a new algorithm for the widely used density-based clustering method DBscan. Our algorithm computes the DBscan-clustering in $O(nlogn)$ time in $mathbb{R}^2$, irrespective of the scale parameter $varepsilon$ (and assuming the second parameter MinPts is set to a fixed constant, as is the case in practice). Experiments show that the new algorithm is not only fast in theory, but that a slightly simplified version is competitive in practice and much less sensitive to the choice of $varepsilon$ than the original DBscan algorithm. We also present an $O(nlogn)$ randomized algorithm for HDBscan in the plane---HDBscan 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.

Recommendations

• Faster \textsc{dbscan} and \textsc{hdbscan} in low-dimensional Euclidean spaces
• On the hardness and approximation of Euclidean DBSCAN
• scientific article; zbMATH DE number 1947400
• GEOMETRIC ALGORITHMS FOR DENSITY-BASED DATA CLUSTERING
• scientific article; zbMATH DE number 5896448

Cites work

• An O(n log n) algorithm for the all-nearest-neighbors problem
• Better \(\varepsilon\)-dependencies for offline approximate nearest neighbor search, Euclidean minimum spanning trees, and \(\varepsilon\)-kernels
• Computational geometry. Algorithms and applications.
• Euclidean minimum spanning trees and bichromatic closest pairs
• GEOMETRIC ALGORITHMS FOR DENSITY-BASED DATA CLUSTERING
• Geometric Spanner Networks
• Higher order Delaunay triangulations
• Introduction to algorithms.
• Optimal halfspace range reporting in three dimensions
• Reporting points in halfspaces

Cited in

(8)

• scientific article; zbMATH DE number 5896448 (Why is no real title available?)
• $$\mathtt {IP.LSH.DBSCAN}$$: Integrated Parallel Density-Based Clustering Through Locality-Sensitive Hashing
• scientific article; zbMATH DE number 1947400 (Why is no real title available?)
• Anytime parallel density-based clustering
• Faster \textsc{dbscan} and \textsc{hdbscan} in low-dimensional Euclidean spaces
• DBSCAN: optimal rates for density-based cluster estimation
• On the hardness and approximation of Euclidean DBSCAN
• Density-based clustering in MapReduce with guarantees on parallel time, space, and solution quality

This page was built for publication: Faster DBScan and HDBscan in low-dimensional Euclidean spaces

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5136243)