← 研踪 PaperTrailarXiv:2604.11656 · v2
Scalable Exact Hierarchical Agglomerative Clustering via Sparse Geographic Distance Graphs
首次提交 2026-04-14 00:08
版本更新 2026-11-03 20:49
雷达观测 2026-11-04 23:39
摘要
Exact hierarchical agglomerative clustering (HAC) of large spatial datasets is limited in practice by the $\mathcal{O}(n^2)$ time and memory required for the full pairwise distance matrix. We present GSHAC (Geographically Sparse Hierarchical Agglomerative Clustering), a system that makes exact HAC feasible at scales of millions of geographic features on a commodity workstation. GSHAC replaces the distance matrix with a sparse geographic distance graph containing only pairs within a user-specified geodesic bound $h_{\max}$, constructed in $\mathcal{O}(n \cdot k)$ time via spatial indexing, where $k$ is the mean number of neighbors within $h_{\max}$. Connected components of this graph define independent subproblems, and we prove that the resulting assignments are exact for all standard linkage methods at any cut height $h \le h_{\max}$. For single linkage, an MST-based path keeps memory at $\mathcal{O}(n_k + m_k)$ per component. Applied to a global mining inventory ($n = 261{,}073$), the system completes in 12 s (109 MiB peak HAC memory) versus $\approx 545$ GiB for the dense baseline. On a 2-million-point GeoNames sample, all tested thresholds completed in under 3 minutes with peak memory under 3 GiB. We provide a scikit-learn-compatible implementation for direct integration into GIS workflows.
作者备注：11 pages, 4 figures
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v2 · 2026-11-03 20:49 · 最新观测版本
Scalable Exact Hierarchical Agglomerative Clustering via Sparse Geographic Distance Graphs
Exact hierarchical agglomerative clustering (HAC) of large spatial datasets is limited in practice by the $\mathcal{O}(n^2)$ time and memory required for the full pairwise distance matrix. We present GSHAC (Geographically Sparse Hierarchical Agglomerative Clustering), a system that makes exact HAC feasible at scales of millions of geographic features on a commodity workstation. GSHAC replaces the distance matrix with a sparse geographic distance graph containing only pairs within a user-specified geodesic bound $h_{\max}$, constructed in $\mathcal{O}(n \cdot k)$ time via spatial indexing, where $k$ is the mean number of neighbors within $h_{\max}$. Connected components of this graph define independent subproblems, and we prove that the resulting assignments are exact for all standard linkage methods at any cut height $h \le h_{\max}$. For single linkage, an MST-based path keeps memory at $\mathcal{O}(n_k + m_k)$ per component. Applied to a global mining inventory ($n = 261{,}073$), the system completes in 12 s (109 MiB peak HAC memory) versus $\approx 545$ GiB for the dense baseline. On a 2-million-point GeoNames sample, all tested thresholds completed in under 3 minutes with peak memory under 3 GiB. We provide a scikit-learn-compatible implementation for direct integration into GIS workflows.
查看此版本解读 →查看此版本原文 ↗