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