On Metric DBSCAN with Low Doubling Dimension

Hu Ding, Fan Yang

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 partitioning and pruning process: (a) original data, (b) covering with balls of radius r, and (c) pruning range queries using the triangle inequality.

The process involves:

  1. Coarse Partitioning: The dataset is partitioned into balls. Pairwise distances between the centers of these balls are pre-computed.
  2. 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.
  3. 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.

Running time vs. the normalized radius r/Δ for METRIC-1 and METRIC-2, showing optimal performance around 0.1.

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

Abstract

The density based clustering method {\em 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 space 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 be implemented 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},
  title = {{On Metric DBSCAN with Low Doubling Dimension}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.24963/ijcai.2020/426},
}
Figure