Scalable Hyperbox Clustering for Geospatial Data
Dymitr Ruta, Ernesto Damiani, Bogdan Gabryś · 2025
Hierarchical clustering has at least quadratic time complexity, limiting its use for large-scale datasets due to costly pairwise distance computations, often unnecessary and not specific to Euclidean metrics. We propose a family of approximate clustering algorithms using hyperboxes to uniformly represent data points and clusters across the numerical input space, targeting near-linear time in low dimensions. This is especially relevant for geo-spatial data analysis, including summarization and predictive feature engineering for supervised learning.We introduce agglomerative (bottom-up) and divisive (top-down) hyperbox clustering, guided by a margin-based threshold for merging or splitting. Variants incorporate simple ℓ∞-norm distances with different execution modes (greedy, online, binary, grid-based). Evaluations on large datasets show strong performance, scalability, and compact summarization, particularly for binary and grid-based approaches. The parallelizable online variant supports real-time processing, well-suited for streaming geospatial data with hyperbox-defined areas of interest.