Abstract
Density-Based Spatial Clustering of Applications with Noise (DBSCAN) is a fundamental algorithm for identifying clusters of arbitrary shapes and filtering noise. However, its $O(n^2)$ time complexity and the "curse of dimensionality" limit its scalability in high-dimensional metric spaces. This paper introduces METRIC-1 and METRIC-2, two algorithms that achieve significant speedups by assuming the dataset's inliers possess a low doubling dimension. By utilizing randomized $k$-center clustering for coarse partitioning, these methods effectively prune the search space, outperforming traditional indexing structures like R*-trees.
Introduction
While DBSCAN is highly effective, its reliance on range queries makes it computationally expensive as dimensionality increases. Traditional spatial indices, such as R-trees or grids, often degrade to linear scans in high-dimensional Euclidean or abstract metric spaces. This research addresses this bottleneck by exploiting the observation that real-world high-dimensional data (e.g., images or text) often lies on a much lower-dimensional manifold. By formalizing this through the concept of doubling dimension, the authors provide a framework for exact DBSCAN that remains efficient even in thousands of dimensions.
Methodology
The core innovation lies in a multi-stage approach to core point identification, which is the primary computational bottleneck of DBSCAN. The authors propose two variants, METRIC-1 and METRIC-2, which follow the pipeline visualized below:
- Low Doubling Dimension Assumption: The algorithm assumes that inliers can be covered by a constant number of balls of half the radius ($2^\rho$), where $\rho$ is the doubling dimension. Crucially, outliers are allowed to be distributed arbitrarily, ensuring robustness.
- Coarse Partitioning: Using a randomized version of Gonzalez’s $k$-center algorithm, the data is quickly partitioned into a set of balls with radius $r$. This acts as a coarse filter to group points.
- Pruned Range Queries: To determine if a point $p$ is a core point, the algorithm restricts its search to points within its own ball, neighboring balls within a distance of $2r + \epsilon$, and a small set of potential outliers. This significantly reduces the number of distance calculations required.
- Filtration (METRIC-2): The second algorithm incorporates a filtration step using a maximal independent set. This ensures that the centers of the coarse balls are sufficiently separated, providing stronger theoretical bounds on the number of neighboring balls that must be inspected.
Experimental Evaluation
The authors evaluated the METRIC algorithms against traditional R*-tree-based DBSCAN and state-of-the-art grid-based methods (GT15) across several high-dimensional datasets:
- Synthetic Data: 20,000 points in 500 to 3,000 dimensions.
- NEURIPS: 11,463 word vectors (5,811 dimensions).
- MNIST & USPSHW: Handwritten digit and letter images (784 and 256 dimensions, respectively).
Key Insights and Results
- Dimensionality Resilience: Unlike traditional methods that slow down drastically as dimensions increase, the METRIC algorithms maintained stable and significantly lower running times. On synthetic datasets, METRIC-2 was orders of magnitude faster than R*-trees.
- Real-World Efficacy: The "low doubling dimension" assumption was validated on MNIST and NEURIPS datasets, where the proposed algorithms consistently outperformed baselines, proving the intrinsic dimensionality of image and text data can be exploited for clustering.
- Parameter Optimization: The choice of the coarse-partitioning radius $r$ is critical. The authors found that setting $r$ to approximately 10% of the dataset's diameter provides an optimal balance between partitioning speed and range query efficiency.
Conclusion
By shifting the focus from global spatial indexing to local density estimation via doubling dimension, this work provides a scalable solution for exact DBSCAN in complex metric spaces. Future work may involve combining this partitioning strategy with approximate DBSCAN methods to achieve even greater performance gains in applications where absolute precision is not required.
Summary updated