Faster DBScan and HDBscan in low-dimensional Euclidean spaces

DOI10.4230/LIPICS.ISAAC.2017.25zbMATH Open1457.68282arXiv1702.08607OpenAlexW2592001482MaRDI QIDQ5136243FDOQ5136243

Marcel Roeloffzen, Ade Gunawan, Mark de Berg

Publication date: 25 November 2020

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.

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

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 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)

Cites Work

• Title not available (Why is that?)
• Geometric Spanner Networks
• Title not available (Why is that?)
• Title not available (Why is that?)
• An O(n log n) algorithm for the all-nearest-neighbors problem
• Reporting points in halfspaces
• Higher order Delaunay triangulations
• Euclidean minimum spanning trees and bichromatic closest pairs
• GEOMETRIC ALGORITHMS FOR DENSITY-BASED DATA CLUSTERING
• Better ϵ-Dependencies for Offline Approximate Nearest Neighbor Search, Euclidean Minimum Spanning Trees, and ϵ-Kernels

Cited In (3)

• Title not available (Why is that?)
• $$\mathtt {IP.LSH.DBSCAN}$$: Integrated Parallel Density-Based Clustering Through Locality-Sensitive Hashing
• Title not available (Why is that?)

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)