DynHAC : Fully Dynamic Approximate Hierarchical Agglomerative Clustering
Shangdi Yu, Laxman Dhulipala, Jakub Łącki, Nikos Parotsidis · Society for Industrial and Applied Mathematics eBooks · 2025
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 [1] 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.