Parallel Hierarchical Agglomerative Clustering in Low Dimensions
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916866825388032 |
|---|---|
| author | Bateni, MohammadHossein Dhulipala, Laxman Fletcher, Willem Gowda, Kishen N Hershkowitz, D Ellis Jayaram, Rajesh Łącki, Jakub |
| author_facet | Bateni, MohammadHossein Dhulipala, Laxman Fletcher, Willem Gowda, Kishen N Hershkowitz, D Ellis Jayaram, Rajesh Łącki, Jakub |
| contents | 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$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_20047 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Parallel Hierarchical Agglomerative Clustering in Low Dimensions Bateni, MohammadHossein Dhulipala, Laxman Fletcher, Willem Gowda, Kishen N Hershkowitz, D Ellis Jayaram, Rajesh Łącki, Jakub Data Structures and Algorithms Computational Complexity Distributed, Parallel, and Cluster Computing 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$. |
| title | Parallel Hierarchical Agglomerative Clustering in Low Dimensions |
| topic | Data Structures and Algorithms Computational Complexity Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2507.20047 |