On Metric DBSCAN with Low Doubling Dimension

Hu Ding, Fan Yang, Mingyue Wang

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:

Overview of the METRIC algorithm steps: (a) input data points, (b) coarse partitioning via randomized k-center clustering, and (c) pruned range queries for core point identification.
  1. 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.
  2. 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.
  3. 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.
  4. 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

Abstract

The density based clustering method Density-Based Spatial Clustering of Applications with Noise (DBSCAN) is a popular method for outlier recognition and has received tremendous attention from many different areas. A major issue of the original DBSCAN is that the time complexity could be as large as quadratic. Most of existing DBSCAN algorithms focus on developing efficient index structures to speed up the procedure in low-dimensional Euclidean space. However, the research of DBSCAN in high-dimensional Euclidean space or general metric spaces is still quite limited, to the best of our knowledge. In this paper, we consider the metric DBSCAN problem under the assumption that the inliers (excluding the outliers) have a low doubling dimension. We apply a novel randomized k-center clustering idea to reduce the complexity of range query, which is the most time consuming step in the whole DBSCAN procedure. Our proposed algorithms do not need to build any complicated data structures and are easy to implement in practice. The experimental results show that our algorithms can significantly outperform the existing DBSCAN algorithms in terms of running time.
BibTeX
@inproceedings{ding2020metric,
  author = {Hu Ding and Fan Yang and Mingyue Wang},
  title = {{On Metric DBSCAN with Low Doubling Dimension}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.24963/ijcai.2020/426},
}
Figure