Faster DBSCAN via subsampled similarity queries

Heinrich Jiang, Jennifer Jang, Jakub Lacki

Abstract

DBSCAN is a popular density-based clustering algorithm. It computes the $\epsilon$-neighborhood graph of a dataset and uses the connected components of the high-degree nodes to decide the clusters. However, the full neighborhood graph may be too costly to compute with a worst-case complexity of $O(n^2)$. In this paper, we propose a simple variant called SNG-DBSCAN, which clusters based on a subsampled $\epsilon$-neighborhood graph, only requires access to similarity queries for pairs of points and in particular avoids any complex data structures which need the embeddings of the data points themselves. The runtime of the procedure is $O(sn^2)$, where $s$ is the sampling rate. We show under some natural theoretical assumptions that $s \approx \log n/n$ is sufficient for statistical cluster recovery guarantees leading to an $O(n\log n)$ complexity. We provide an extensive experimental analysis showing that on large datasets, one can subsample as little as $0.1\%$ of the neighborhood graph, leading to as much as over 200x speedup and 250x reduction in RAM consumption compared to scikit-learn's implementation of DBSCAN, while still maintaining competitive clustering performance.

Introduction

DBSCAN is a staple in machine learning because it finds clusters of arbitrary shapes without needing to know the number of clusters beforehand. However, it has a major Achilles' heel: scalability. In the worst case, DBSCAN has a quadratic runtime complexity ($O(n^2)$) because it needs to compute the $\epsilon$-neighborhood for every point. While spatial data structures like KD-trees can speed this up in low dimensions, they struggle as dimensionality increases. Furthermore, for massive datasets, the memory required to store the neighborhood graph often exceeds the limits of standard hardware, causing the algorithm to crash. There is a critical need for a version of DBSCAN that can handle millions of points efficiently without sacrificing its non-parametric advantages.

Methodology

The authors propose SNG-DBSCAN (Subsampled Neighborhood Graph DBSCAN). The core innovation is the realization that the full neighborhood graph is not required to identify clusters; a sparse "skeleton" of the graph is often sufficient to preserve the connected components of high-density regions.

Algorithm 1: Subsampled Neighborhood Graph DBSCAN (SNG-DBSCAN)

As detailed in Algorithm 1, for every data point, the algorithm only samples a fraction $s$ of the dataset instead of checking all other points. An edge is added between two points only if they are sampled and their distance is $\le \epsilon$. Like standard DBSCAN, it identifies "core points" (nodes with a degree $\ge$ MinPts) and finds the connected components of these points in the subsampled graph. This reduces the runtime to $O(sn^2)$. The authors prove that a sampling rate of $s \approx \log n / n$ is theoretically sufficient to maintain connectivity, leading to a near-linear $O(n \log n)$ complexity.

Experimental Evaluation

The researchers evaluated SNG-DBSCAN on a mix of large-scale benchmarks (up to 3.2M points) and classic UCI datasets. The evaluation focused on clustering quality (Adjusted Rand Index, ARI; Adjusted Mutual Information, AMI), runtime, and memory consumption.

Performance comparison between standard DBSCAN (Base) and SNG-DBSCAN across various large-scale datasets.

As shown in the results table, SNG-DBSCAN achieves massive efficiency gains. On the "Australian" dataset (1M points), it achieved a 200x speedup, finishing in 1.5 minutes compared to over 6 hours for the standard implementation. On the "Still" dataset, it reduced RAM usage by 250x (from 419 GB down to 1.6 GB). In several cases, scikit-learn’s DBSCAN failed entirely due to memory constraints (exceeding 750GB), while SNG-DBSCAN handled them easily. Importantly, clustering performance remained competitive or even slightly improved. SNG-DBSCAN also outperformed the recent DBSCAN++ variant on 70% of tested metrics.

Discussion and Conclusion

The "aha moment" of this work is that while density estimation requires many samples, maintaining cluster connectivity requires far fewer. By relying on random sampling rather than spatial partitioning, SNG-DBSCAN avoids the "curse of dimensionality" that plagues traditional implementations. While optimized KD-trees may still be faster for moderate-sized, low-dimensional data, SNG-DBSCAN offers a robust, scalable solution for massive high-dimensional datasets. Future work may explore adaptive sampling to further refine performance in borderline density regions.

Summary updated

Abstract

DBSCAN is a popular density-based clustering algorithm. It computes the $\epsilon$-neighborhood graph of a dataset and uses the connected components of the high-degree nodes to decide the clusters. However, the full neighborhood graph may be too costly to compute with a worst-case complexity of $O(n^2)$. In this paper, we propose a simple variant called SNG-DBSCAN, which clusters based on a subsampled $\epsilon$-neighborhood graph, only requires access to similarity queries for pairs of points and in particular avoids any complex data structures which need the embeddings of the data points themselves. The runtime of the procedure is $O(sn^2)$, where $s$ is the sampling rate. We show under some natural theoretical assumptions that $s \approx \log n/n$ is sufficient for statistical cluster recovery guarantees leading to an $O(n\log n)$ complexity. We provide an extensive experimental analysis showing that on large datasets, one can subsample as little as $0.1\%$ of the neighborhood graph, leading to as much as over 200x speedup and 250x reduction in RAM consumption compared to scikit-learn's implementation of DBSCAN, while still maintaining competitive clustering performance.
BibTeX
@inproceedings{jiang2020faster,
  author = {Heinrich Jiang and Jennifer Jang and Jakub Lacki},
  title = {{Faster DBSCAN via subsampled similarity queries}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=RrFmM7BnNdP},
}
Figure