Lehr- und Forschungseinheit für Datenbanksysteme

Breadcrumb Navigation


Accepted paper at SISAP 2020

Angle-Based Clustering



Anna Beer, Dominik Seeholzer, Nanni Schüler, Thomas Seidl


13th International Conference on Similarity Search and Applications (SISAP 2020),
30 September-02 October 2020, Virtual


The amount of data increases steadily, and yet most clustering algorithms perform complex computations for every single data point. Furthermore, Euclidean distance which is used for most of the clustering algorithms is often not the best choice for datasets with arbitrarily shaped clusters or such with high dimensionality. Based on ABOD, we introduce ABC, the first angle-based clustering method. The algorithm first identifies a small part of the data as border points of clusters based on the angle between their neighbors. Those few border points can, with some adjustments, be clustered with well-known clustering algorithms like hierarchical clustering with single linkage or DBSCAN. Residual points can quickly and easily be assigned to the cluster of their nearest border point, so the overall runtime is heavily reduced while the results improve or remain similar.