Lehr- und Forschungseinheit für Datenbanksysteme

Breadcrumb Navigation


Accepted paper at ICDM 2022

Density-Based Clustering for Highly Varying Density



Walid Durani, Dominik Mautz, Claudia Plant, Christian Böhm



The 22nd IEEE International Conference on Data Mining (ICDM 2022),
28 November–01 December 2022, FL, USA


A major challenge in cluster analysis is the discovery of clusters with widely varying sizes, densities, and shapes. Most clustering algorithms lack the ability to detect heterogeneous clusters that differ greatly in all three properties simultaneously. In this work, we propose the Density Clustering for Highly varying Density algorithm (DBHD). DBHD uses a novel approach that considers local density information and introduces two new conditions to distinguish between different types of data points. Based on this and the adaptively computed density information, DBHD can detect the clusters described above and is robust to noise. Moreover, DBHD has intuitive and robust parameters. In extensive experiments, we show that our technique is much more effective in detecting clusters of different shapes, sizes, and densities than well-known (DBSCAN or OPTICS) and recently proposed algorithms such as DPC, SNN-DPC, or LSDBC.