Distributed and Flexible Density-Based Clustering

Abstract

Clustering large datasets becomes difficult when their computational or memory require- ments exceed the capacity of a single machine. This is particularly challenging for density- based clustering, where neighborhood information and global connectivity are needed to identify clusters and noise. FISHDBC provides a scalable approximation of HDBSCAN* by combining HNSW-based neighbor discovery with an approximate minimum spanning tree, but its original design is limited to single-machine execution. This thesis investigates a distributed adaptation of FISHDBC. A sampled global HNSW is used to organize and partition the dataset, while multiple Workers perform local neigh- borhood discovery and graph processing. A central Leader combines the reduced local in- formation, reconstructs approximate global core distances, recomputes mutual-reachability weights, and builds the global minimum spanning tree used for hierarchical clustering. The proposed implementation is evaluated against centralized FISHDBC and HDBSCAN* under both controlled and application-specific workloads. The experiments examine clus- tering agreement, the effects of sampling and replication, runtime scalability, memory usage, and the computational cost of flexible distance functions. The results show that the distributed approach preserves the expected clustering structure in the evaluated con- figurations and improves scalability relative to centralized FISHDBC as the dataset size increases. The evaluation also identifies the centralized Indexer, particularly data routing and graph processing, as the main scalability bottleneck of the current prototype.

Clustering large datasets becomes difficult when their computational or memory require- ments exceed the capacity of a single machine. This is particularly challenging for density- based clustering, where neighborhood information and global connectivity are needed to identify clusters and noise. FISHDBC provides a scalable approximation of HDBSCAN* by combining HNSW-based neighbor discovery with an approximate minimum spanning tree, but its original design is limited to single-machine execution. This thesis investigates a distributed adaptation of FISHDBC. A sampled global HNSW is used to organize and partition the dataset, while multiple Workers perform local neigh- borhood discovery and graph processing. A central Leader combines the reduced local in- formation, reconstructs approximate global core distances, recomputes mutual-reachability weights, and builds the global minimum spanning tree used for hierarchical clustering. The proposed implementation is evaluated against centralized FISHDBC and HDBSCAN* under both controlled and application-specific workloads. The experiments examine clus- tering agreement, the effects of sampling and replication, runtime scalability, memory usage, and the computational cost of flexible distance functions. The results show that the distributed approach preserves the expected clustering structure in the evaluated con- figurations and improves scalability relative to centralized FISHDBC as the dataset size increases. The evaluation also identifies the centralized Indexer, particularly data routing and graph processing, as the main scalability bottleneck of the current prototype.