DBSCAN

DBSCAN (Density-Based Spatial Clustering of Applications with Noise) is a foundational non-parametric clustering and outlier-detection algorithm in computation and algorithms, spatial data mining, and machine learning, introduced by Martin Ester, Hans-Peter Kriegel, Jörg Sander, and Xiaowei Xu in 1996. Unlike centroid-based methods such as k-means clustering, which partition every point into one of k convex Voronoi diagram cells and require specifying the number of clusters k in advance, DBSCAN defines clusters as maximal density-connected sets of points separated by lower-density background regions.

Because DBSCAN grows clusters transitively through local neighborhood graphs rather than optimizing a global parametric centroid objective, it simultaneously discovers non-convex, elongated, or ring-shaped structures, determines the number of clusters automatically from two local density thresholds, and classifies isolated observations in sparse regions as explicit noise (outliers). In 2014, DBSCAN received the ACM SIGKDD Test of Time Award for its lasting impact across geographic information systems (GIS), astronomical sky surveys, single-cell transcriptomics, and LiDAR point-cloud segmentation.

Let X = {x₁, x₂, …, x_n} be a dataset equipped with a distance metric d(p, q) (such as Euclidean distance, cosine distance, or Levenshtein distance). DBSCAN is governed by two hyperparameters: a neighborhood radius ε > 0 and a minimum point count MinPts ∈ ℕ. For every point p ∈ X, its closed ε-neighborhood is defined as:

N_ε(p) = { q ∈ X : d(p, q) ≤ ε }.

Based on the cardinality |N_ε(p)|, every point in X falls into one of three topological roles:

1. Core point: A point p ∈ X is a core point if its ε-neighborhood contains at least MinPts points (including p itself): |N_ε(p)| ≥ MinPts.
2. Directly density-reachable & Border point: A point q is directly density-reachable from a point p if q ∈ N_ε(p) and p is a core point. A non-core point b (with |N_ε(b)| < MinPts) that lies inside N_ε(p) of at least one core point p is called a border point.
3. Noise (outlier) point: Any point z ∈ X that is neither a core point nor directly density-reachable from any core point is classified as noise.

Density-Reachability vs. Density-Connectivity

A point q is density-reachable from p if there exists a chain of points p₁, p₂, …, p_m with p₁ = p and p_m = q such that each p_i+1 is directly density-reachable from p_i (meaning p₁, …, p_m−1 must all be core points). Because q may be a border point, density-reachability is transitive but asymmetric. To obtain a symmetric relation, two points p and q are defined as density-connected if there exists a core point o ∈ X from which both p and q are density-reachable. A DBSCAN cluster C ⊆ X is then defined as a non-empty subset satisfying both maximality (if p ∈ C and q is density-reachable from p, then q ∈ C) and connectivity (all pairs p, q ∈ C are density-connected).

DBSCAN traverses X via breadth-first search over the core-point neighborhood graph:

1. Iterate through each unvisited point p ∈ X and mark p as visited.
2. Execute a range query to retrieve N_ε(p). If |N_ε(p)| < MinPts, provisionally label p as NOISE (note that p may later be claimed as a border point by an adjacent core point).
3. If |N_ε(p)| ≥ MinPts, create a new cluster C, add p to C, and initialize a seed queue Q ← N_ε(p) \ {p}.
4. While Q is non-empty, pop a point q from Q: if q was previously labeled NOISE, relabel q as a border member of C; if q was unvisited, mark q visited, assign q to C, query N_ε(q), and if |N_ε(q)| ≥ MinPts append all unqueued members of N_ε(q) to Q.

Because DBSCAN performs exactly one ε-range query per point p ∈ X, its total time complexity is n × T_range. Without a spatial index, scanning all n points per query takes O(n²) time. When low-dimensional coordinates (d ≤ 20) are indexed in an R*-tree, k-d tree, ball tree, or Delaunay triangulation neighborhood graph, average-case runtime drops to O(n log n) with O(n) memory.

Choosing MinPts and the k-Distance Knee Plot

Ester et al. and subsequent high-dimensional analyses (Schubert et al., 2017) recommend setting MinPts ≥ d + 1, with MinPts = 2d as a robust default for noisy datasets of dimension d (and MinPts = 4 for 2D spatial data). Once MinPts is fixed, the radius ε is selected by computing the distance d_k(p) from each point p ∈ X to its (MinPts − 1)-th nearest neighbor, sorting these distances in ascending order, and locating the "knee" or "elbow" where the sorted k-distance curve bends sharply upward from compact intra-cluster spacing to sparse background noise.

Border-Point Ambiguity, OPTICS, and HDBSCAN

Restricted to core points and noise points, DBSCAN is deterministic: core points form connected components of the undirected symmetric graph on {p : |N_ε(p)| ≥ MinPts} with edges d(p, q) ≤ ε. Only border points within distance ε of two clusters can change membership depending on iteration order; DBSCAN* (Campello et al., 2013) eliminates this ambiguity by defining only core points as cluster members.

When a dataset contains clusters of varying densities, no single global radius ε resolves dense sub-clusters without splitting sparse clusters into noise. OPTICS (Ankerst et al., 1999) orders points by their core distance and reachability distance across all scales ε, while HDBSCAN (Campello, Moulavi, & Sander, 2013) builds the minimum spanning tree of the mutual reachability distance d_mreach(p, q) = max{core_k(p), core_k(q), d(p, q)} and extracts persistent clusters using a single minimum-cluster-size hyperparameter.

Why does DBSCAN setting MinPts = 2 reduce to single-linkage hierarchical clustering?

When MinPts = 2 (or MinPts = 1), every point with at least one neighbor within distance ε is a core point. The DBSCAN clusters then coincide with the connected components of the ε-neighborhood graph, which matches cutting a single-linkage hierarchical clustering dendrogram at height ε.

How does the curse of dimensionality affect DBSCAN?

In high-dimensional Euclidean spaces (d ≫ 50), pairwise Euclidean distances concentrate around their mean (lim_d→∞ (d_max − d_min)/d_min → 0), flattening density contrast. Applying principal component analysis or UMAP dimensionality reduction, or switching from Euclidean distance to cosine or shared-nearest-neighbor (SNN) similarity, restores density separation.

1. Ester, M., Kriegel, H.-P., Sander, J., & Xu, X. (1996). A density-based algorithm for discovering clusters in large spatial databases with noise. Proceedings of the Second International Conference on Knowledge Discovery and Data Mining (KDD-96), 226–231. https://doi.org/10.5555/3001460.3001507
2. Ankerst, M., Breunig, M. M., Kriegel, H.-P., & Sander, J. (1999). OPTICS: Ordering points to identify the clustering structure. ACM SIGMOD Record, 28(2), 49–60. https://doi.org/10.1145/304181.304187
3. Campello, R. J. G. B., Moulavi, D., & Sander, J. (2013). Density-based clustering based on hierarchical density estimates. Advances in Knowledge Discovery and Data Mining (PAKDD 2013), 160–172. https://doi.org/10.1007/978-3-642-37456-2_14
4. Schubert, E., Sander, J., Ester, M., Kriegel, H. P., & Xu, X. (2017). DBSCAN revisited, revisited: Why and how you should (still) use DBSCAN. ACM Transactions on Database Systems, 42(3), 19:1–19:21. https://doi.org/10.1145/3068335