Abstract
Density-Based Spatial Clustering of Applications with Noise (DBSCAN) is a cornerstone algorithm for clustering and outlier detection. However, its computational cost often scales quadratically ($O(n^2)$) in high-dimensional or general metric spaces, where traditional spatial indexing fails. This paper introduces a novel approach to exact DBSCAN that leverages the assumption that inlier data possesses a low doubling dimension. By employing a randomized $k$-center clustering strategy for coarse partitioning and triangle inequality pruning, the proposed METRIC-1 and METRIC-2 algorithms achieve significant speedups without complex data structures.
Introduction
DBSCAN identifies clusters as dense regions separated by areas of low density. Its primary bottleneck is the "range query" step: for every point, the algorithm must find all neighbors within a distance $\epsilon$. While R*-trees and similar structures optimize this in low dimensions, they succumb to the "curse of dimensionality" in high-dimensional Euclidean or abstract metric spaces. Consequently, DBSCAN often reverts to exhaustive pairwise comparisons.
Methodology: Index-Free Partitioning
The authors propose two algorithms, METRIC-1 and METRIC-2, which replace hierarchical trees with a flat, coarse partitioning scheme. The core idea is to cover the dataset with balls of radius $r$ using a randomized version of Gonzalez’s $k$-center algorithm.
The process involves:
- Coarse Partitioning: The dataset is partitioned into balls. Pairwise distances between the centers of these balls are pre-computed.
- Triangle Inequality Pruning: During a range query for a point $p$, the algorithm identifies $p$'s nearest center $c_p$. Using the pre-computed distances and the triangle inequality, the algorithm can mathematically exclude entire balls that are too far away, only performing exact distance calculations for points in nearby balls.
- Filtration (METRIC-2): METRIC-2 adds a filtration step to ensure centers are not too close to each other, further optimizing the number of balls to track.
Experimental Results
The algorithms were tested on synthetic datasets (up to 3000 dimensions) and real-world data, including word vectors (NeuroIPS) and handwritten digits (MNIST/USPSHW). Both METRIC-1 and METRIC-2 consistently outperformed standard R*-tree implementations and state-of-the-art grid-based methods.
A key finding was the sensitivity to the partition radius $r$. As shown in the performance analysis, setting $r$ to approximately $0.1$ times the estimated diameter of the dataset provides the best balance between pruning efficiency and partitioning overhead.
Conclusion
By assuming that only the inliers (and not the noise) reside on a low-dimensional manifold, the authors provide a practical and efficient solution for high-dimensional DBSCAN. Their index-free, randomized $k$-center approach is easy to implement and significantly reduces the computational burden of range queries in complex metric spaces.
Summary updated