DynHAC: Fully Dynamic Approximate Hierarchical Agglomerative Clustering
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866929674976755712 |
|---|---|
| author | Yu, Shangdi Dhulipala, Laxman Łącki, Jakub Parotsidis, Nikos |
| author_facet | Yu, Shangdi Dhulipala, Laxman Łącki, Jakub Parotsidis, Nikos |
| contents | We consider the problem of maintaining a hierarchical agglomerative clustering (HAC) in the dynamic setting, when the input is subject to point insertions and deletions. We introduce DynHAC - the first dynamic HAC algorithm for the popular average-linkage version of the problem which can maintain a 1+εapproximate solution. Our approach leverages recent structural results on (1+ε)-approximate HAC to carefully identify the part of the clustering dendrogram that needs to be updated in order to produce a solution that is consistent with what a full recomputation from scratch would have output.
We evaluate DynHAC on a number of real-world graphs. We show that DynHAC can handle each update up to 423x faster than what it would take to recompute the clustering from scratch. At the same time it achieves up to 0.21 higher NMI score than the state-of-the-art dynamic hierarchical clustering algorithms, which do not provably approximate HAC. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_07745 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | DynHAC: Fully Dynamic Approximate Hierarchical Agglomerative Clustering Yu, Shangdi Dhulipala, Laxman Łącki, Jakub Parotsidis, Nikos Data Structures and Algorithms We consider the problem of maintaining a hierarchical agglomerative clustering (HAC) in the dynamic setting, when the input is subject to point insertions and deletions. We introduce DynHAC - the first dynamic HAC algorithm for the popular average-linkage version of the problem which can maintain a 1+εapproximate solution. Our approach leverages recent structural results on (1+ε)-approximate HAC to carefully identify the part of the clustering dendrogram that needs to be updated in order to produce a solution that is consistent with what a full recomputation from scratch would have output. We evaluate DynHAC on a number of real-world graphs. We show that DynHAC can handle each update up to 423x faster than what it would take to recompute the clustering from scratch. At the same time it achieves up to 0.21 higher NMI score than the state-of-the-art dynamic hierarchical clustering algorithms, which do not provably approximate HAC. |
| title | DynHAC: Fully Dynamic Approximate Hierarchical Agglomerative Clustering |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2501.07745 |