TeraHAC: Hierarchical Agglomerative Clustering of Trillion-Edge Graphs
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866916282213859328 |
|---|---|
| author | Dhulipala, Laxman Lee, Jason Łącki, Jakub Mirrokni, Vahab |
| author_facet | Dhulipala, Laxman Lee, Jason Łącki, Jakub Mirrokni, Vahab |
| contents | We introduce TeraHAC, a $(1+ε)$-approximate hierarchical agglomerative clustering (HAC) algorithm which scales to trillion-edge graphs. Our algorithm is based on a new approach to computing $(1+ε)$-approximate HAC, which is a novel combination of the nearest-neighbor chain algorithm and the notion of $(1+ε)$-approximate HAC. Our approach allows us to partition the graph among multiple machines and make significant progress in computing the clustering within each partition before any communication with other partitions is needed.
We evaluate TeraHAC on a number of real-world and synthetic graphs of up to 8 trillion edges. We show that TeraHAC requires over 100x fewer rounds compared to previously known approaches for computing HAC. It is up to 8.3x faster than SCC, the state-of-the-art distributed algorithm for hierarchical clustering, while achieving 1.16x higher quality. In fact, TeraHAC essentially retains the quality of the celebrated HAC algorithm while significantly improving the running time. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2308_03578 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | TeraHAC: Hierarchical Agglomerative Clustering of Trillion-Edge Graphs Dhulipala, Laxman Lee, Jason Łącki, Jakub Mirrokni, Vahab Data Structures and Algorithms Databases Distributed, Parallel, and Cluster Computing Information Retrieval We introduce TeraHAC, a $(1+ε)$-approximate hierarchical agglomerative clustering (HAC) algorithm which scales to trillion-edge graphs. Our algorithm is based on a new approach to computing $(1+ε)$-approximate HAC, which is a novel combination of the nearest-neighbor chain algorithm and the notion of $(1+ε)$-approximate HAC. Our approach allows us to partition the graph among multiple machines and make significant progress in computing the clustering within each partition before any communication with other partitions is needed. We evaluate TeraHAC on a number of real-world and synthetic graphs of up to 8 trillion edges. We show that TeraHAC requires over 100x fewer rounds compared to previously known approaches for computing HAC. It is up to 8.3x faster than SCC, the state-of-the-art distributed algorithm for hierarchical clustering, while achieving 1.16x higher quality. In fact, TeraHAC essentially retains the quality of the celebrated HAC algorithm while significantly improving the running time. |
| title | TeraHAC: Hierarchical Agglomerative Clustering of Trillion-Edge Graphs |
| topic | Data Structures and Algorithms Databases Distributed, Parallel, and Cluster Computing Information Retrieval |
| url | https://arxiv.org/abs/2308.03578 |