Faster DBSCAN via subsampled similarity queries

Heinrich Jiang, Jennifer Jang, Jakub Lacki

Density-Based Spatial Clustering of Applications with Noise (DBSCAN) is a clustering staple beloved by data scientists because it can find clusters of arbitrary shapes and automatically identify the number of clusters without requiring it as an input parameter. However, it has a major "scalability wall."

To work, DBSCAN needs to compute an $\epsilon$-neighborhood graph, connecting points within a specified distance $\epsilon$. In the worst case, this is a quadratic $O(n^2)$ operation. While data structures like KD-Trees can help, they struggle in high dimensions due to the "curse of dimensionality" and still require significant memory to store the graph. On modern million-point datasets, standard DBSCAN implementations often crash due to memory exhaustion or take days to finish.

This paper introduces SNG-DBSCAN, a variant that proves you only need to sample a tiny fraction of the neighborhood graph to recover the same clusters, achieving up to 200x speedups and 250x less RAM usage while maintaining theoretical guarantees.

The SNG-DBSCAN Method

The authors propose Subsampled Neighborhood Graph DBSCAN (SNG-DBSCAN). The algorithm is surprisingly simple and avoids complex data structures that require embeddings of the data points themselves.

Algorithm 1: Subsampled Neighborhood Graph DBSCAN

Instead of finding all neighbors for every point, the algorithm samples a fraction $s$ of all possible pairs of points. If a sampled pair is within distance $\epsilon$, an edge is added to the graph. It then performs the standard DBSCAN procedure—finding "core points" (nodes with high degree) and identifying connected components—but on this much sparser, subsampled graph.

The "Secret Sauce": The authors leverage a theoretical result (Karger’s sampling lemma) to show that if the sampling rate $s$ is roughly $\log n/n$, the connected components of the graph are preserved with high probability. This reduces the runtime complexity from $O(n^2)$ to $O(n \log n)$.

Key Insights

  • Connectivity is Robust: You don't need every single edge to keep a cluster together. As long as the "min-cut" of a cluster is large enough, random sampling will likely leave enough edges to keep the cluster connected.
  • Memory is the Real Bottleneck: In many experiments, the baseline DBSCAN didn't just run slowly—it failed to run entirely because it required hundreds of gigabytes of RAM. SNG-DBSCAN keeps memory usage low because the graph it builds is extremely sparse.
  • No Embeddings Required: Unlike KD-Trees or Ball-Trees, SNG-DBSCAN only needs a similarity/distance function. It doesn't care about the underlying geometry, making it compatible with non-Euclidean metrics.
  • Dimension Independence: Because it uses random sampling rather than space-partitioning, it avoids the performance degradation typically seen in high-dimensional spaces.

Key Results

The researchers evaluated the algorithm on a mix of large datasets (~1M points, such as Australian, Still, Watch, Satimage, and Phone) and smaller benchmark datasets.

Comparison of clustering performance, runtime, and memory usage between standard DBSCAN and SNG-DBSCAN.

The empirical results strongly validate the theoretical claims:

  • Massive Speedups: On the "Australian" dataset (1M points, 14 features), SNG-DBSCAN achieved a 200x speedup over scikit-learn’s implementation, dropping runtime from over 6 hours to just 1.5 minutes.
  • Drastic RAM Reduction: On the "Still" dataset, it reduced RAM consumption by 250x (from 419 GB down to 1.6 GB).
  • Competitive Accuracy: Despite looking at as little as 0.1% of the potential edges (a sampling rate of $s=0.001$), the algorithm maintained clustering quality (measured by Adjusted Rand Index and Adjusted Mutual Information) nearly identical to the full DBSCAN.
  • Superiority over Alternatives: SNG-DBSCAN outperformed a recent competitor, DBSCAN++, on 70% of the tested metrics.

Limitations and Future Work

While highly effective for large, high-dimensional datasets, the authors note a few limitations. In very low dimensions with very small $\epsilon$ values, traditional space-partitioning methods (like KD-trees) might still be faster because they can prune the search space more effectively than random sampling.

Additionally, the current method uses uniform sampling. The authors suggest that adaptive sampling—sampling more heavily in sparse regions—could potentially improve results further. Finally, while the paper assumes a single processor for its analysis, the random sampling approach is "embarrassingly parallel," suggesting even greater potential for distributed systems in future implementations.

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