Faster DBSCAN via subsampled similarity queries
This work addresses scalability issues for DBSCAN users on large datasets, offering a practical speedup with theoretical guarantees, though it is incremental as it builds on the existing DBSCAN framework.
The paper tackles the high computational cost of DBSCAN by proposing SNG-DBSCAN, a variant that uses a subsampled neighborhood graph, achieving up to 200x speedup and 250x reduction in RAM consumption while maintaining competitive clustering performance.
DBSCAN is a popular density-based clustering algorithm. It computes the $ε$-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 $ε$-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.