# Faster DB-scan and HDB-scan in Low-Dimensional Euclidean Spaces

Source: [Faster DB-scan and HDB-scan in Low-Dimensional Euclidean Spaces](<https://www.sota2.com/research/paper/68fa63301e209131ce9fd2ec>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2025-10-25T20:35:17.063Z

Authors: Mark de Berg, Ade Gunawan, Marcel Roeloffzen

Published: 2017-02-28T02:18:54.000Z

## 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 $\\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(n\\log n)$ 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.

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/1702.08607>)

[PDF](<https://arxiv.org/pdf/1702.08607.pdf>)