DBSCAN++: Towards fast and scalable density clustering

Abstract

DBSCAN is a classical density-based clustering procedure with tremendous practical relevance. However, DBSCAN implicitly needs to compute the empirical density for each sample point, leading to a quadratic worst-case time complexity, which is too slow on large datasets. We propose DBSCAN++, a simple modification of DBSCAN which only requires computing the densities for a chosen subset of points. We show empirically that, compared to traditional DBSCAN, DBSCAN++ can provide not only competitive performance but also added robustness in the bandwidth hyperparameter while taking a fraction of the runtime. We also present statistical consistency guarantees showing the trade-off between computational cost and estimation rates. Surprisingly, up to a certain point, we can enjoy the same estimation rates while lowering computational cost, showing that DBSCAN++ is a sub-quadratic algorithm that attains minimax optimal rates for level-set estimation, a quality that may be of independent interest.

Cited by in corpus (9)

• Faster DBSCAN via subsampled similarity queries
• Towards Metric DBSCAN: Exact, Approximate, and Streaming Algorithms
• Theoretically-Efficient and Practical Parallel DBSCAN
• Mapper Interactive: A Scalable, Extendable, and Interactive Toolbox for the Visual Exploration of High-Dimensional Data
• DBSCAN: Optimal Rates For Density Based Clustering
• MeanShift++: Extremely Fast Mode-Seeking With Applications to Segmentation and Object Tracking
• Cooperation and Federation in Distributed Radar Point Cloud Processing
• An Algorithmic Introduction to Clustering
• On Metric DBSCAN with Low Doubling Dimension