{"ID":2890244,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2507.20047","arxiv_id":"2507.20047","title":"Parallel Hierarchical Agglomerative Clustering in Low Dimensions","abstract":"Hierarchical Agglomerative Clustering (HAC) is an extensively studied and widely used method for hierarchical clustering in $\\mathbb{R}^k$ based on repeatedly merging the closest pair of clusters according to an input linkage function $d$. Highly parallel (i.e., NC) algorithms are known for $(1+ε)$-approximate HAC (where near-minimum rather than minimum pairs are merged) for certain linkage functions that monotonically increase as merges are performed. However, no such algorithms are known for many important but non-monotone linkage functions such as centroid and Ward's linkage. In this work, we show that a general class of non-monotone linkage functions -- which include centroid and Ward's distance -- admit efficient NC algorithms for $(1+ε)$-approximate HAC in low dimensions. Our algorithms are based on a structural result which may be of independent interest: the height of the hierarchy resulting from any constant-approximate HAC on $n$ points for this class of linkage functions is at most $\\operatorname{poly}(\\log n)$ as long as $k = O(\\log \\log n / \\log \\log \\log n)$. Complementing our upper bounds, we show that NC algorithms for HAC with these linkage functions in \\emph{arbitrary} dimensions are unlikely to exist by showing that HAC is CC-hard when $d$ is centroid distance and $k = n$.","short_abstract":"Hierarchical Agglomerative Clustering (HAC) is an extensively studied and widely used method for hierarchical clustering in $\\mathbb{R}^k$ based on repeatedly merging the closest pair of clusters according to an input linkage function $d$. Highly parallel (i.e., NC) algorithms are known for $(1+ε)$-approximate HAC (whe...","url_abs":"https://arxiv.org/abs/2507.20047","url_pdf":"https://arxiv.org/pdf/2507.20047v1","authors":"[\"MohammadHossein Bateni\",\"Laxman Dhulipala\",\"Willem Fletcher\",\"Kishen N Gowda\",\"D Ellis Hershkowitz\",\"Rajesh Jayaram\",\"Jakub Łącki\"]","published":"2025-07-26T19:52:50Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.CC\",\"cs.DC\"]","methods":"[]","has_code":false}