Fully-Dynamic Parallel Algorithms for Single-Linkage Clustering Conference: 37th ACM Symposium on Parallelism in Algorithms and Architectures; July 28-August 1, 2025; Portland, OR, USA 37th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA ’25), July 28-August 1, 2025, Portland, OR,

Quinten De Man, Laxman Dhulipala, Kishen N Gowda · 2025

Read Fully-Dynamic Parallel Algorithms for Single-Linkage Clustering Conference: 37th ACM Symposium on Parallelism in Algorithms and Architectures; July 28-August 1, 2025; Portland, OR, USA 37th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA ’25), July 28-August 1, 2025, Portland, OR, by Quinten De Man, Laxman Dhulipala, Kishen N Gowda (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-18384.txt.

Introduction

Quinten De Man, Laxman Dhulipala, and Kishen N. Gowda keep a family tree of data clusters up to date as the data changes, in a 2025 paper. Single-linkage clustering joins the two closest groups again and again. The full joining history forms a tree called a dendrogram.

Earlier dynamic work tracked only the cheapest links between points. Nobody could refresh the tree itself faster than rebuilding it. The new methods add an edge in time tied to the tree's height. Deletions cost only a bit more. Parallel versions spread the work across many cores with little waste. Updates can also be charged to how much the tree actually changed.

Catalog record

CREATORQuinten De Man, Laxman Dhulipala, Kishen N Gowda
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE81 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-18384

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Fully-Dynamic Parallel Algorithms for Single-Linkage Clustering Conference: 37th ACM Symposium on Parallelism in Algorithms and Architectures; July 28-August 1, 2025; Portland, OR, USA 37th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA ’25), July 28-August 1, 2025, Portland, OR, USA DOI: 10.1145/3694906.3743315 ISBN: 979-8-4007-1258-6/2025/07 Quinten De Man, Laxman Dhulipala, Kishen N Gowda Abstract . Single-linkage clustering is a popular form of hierarchical agglomerative clustering (HAC) where the distance between two clusters is defined as the minimum distance between any pair of points across the two clusters. In single-linkage HAC, the output is typically the single-linkage dendrogram (SLD), which is the binary tree representing the hierarchy of clusters formed by iteratively contracting the two closest clusters. In the dynamic setting, prior work has only studied maintaining a minimum spanning forest over the data since single-linkage HAC reduces to computing the SLD on the minimum spanning forest of the data. In this paper, we study the problem of maintaining the SLD in the fully-dynamic setting. We assume the input is a dynamic forest F F (representing the minimum spanning forest of the data) which receives a sequence of edge insertions and edge deletions. To our knowledge, no prior work has provided algorithms to update an SLD asymptotically faster than recomputing it from scratch. All of our update algorithms are asymptotically faster than the best known static SLD computation algorithm, which takes O ⁡ ( n ​ log ⁡ h ) O(n\log h) time where h h is the height of the dendrogram ( h ≤ n − 1 h\leq n-1 ). Furthermore, our algorithms are much faster in many cases, such as when h h is low. Our first set of results are an insertion algorithm in O ⁡ ( h ) O(h) time and a deletion algorithm in O ⁡ ( h ​ log ⁡ ( 1 + n / h ) ) O(h\log(1+n/h)) time. Next, we describe parallel and batch-parallel versions of these algorithms which are work-efficient or nearly work-efficient and have poly-logarithmic depth. Finally, we show how to perform insertions near-optimally in O ⁡ ( c ​ log ⁡ ( 1 + n / c ) ) O(c\log(1+n/c)) time, where c c is the number of structural changes in the dendrogram caused by the update, and give a work-efficient parallel version of this algorithm that has polylogarithmic depth. † † cc-license: by 1. Introduction Single-linkage clustering is a popular form of hierarchical agglomerative clustering (HAC), a fundamental clustering algorithm that has been widely used in unsupervised learning and data mining ( Manning et al. 2008 ) . In HAC, clusters are greedily paired together based on a distance (or similarity) measure. For single-linkage clustering, the distance between clusters is determined by the linkage function D(A,B)=\min_{a\in A,b\in B}d(a,b) . The output of HAC is typically a dendrogram , a rooted binary tree where the leaves are clusters containing each original point, and each internal node corresponds to merging a pair of clusters. For single-linkage clustering, this tree is called the single-linkage dendrogram (SLD). Single-linkage dendrograms have been widely used to analyze real-world data in fields ranging from computational biology ( Gasperini et al. 2019 ; Letunic and Bork 2007 ; Yengo et al. 2022 ) , image analysis ( Götz et al. 2018 ; Havel et al. 2019 ; Ouzounis and Soille 2012 ) , and astronomy ( Baron 2019 ; Feigelson and Babu 1998 ) , among many others ( Henry et al. 2005 ; Yim and Ramdeen 2015 ; Manning et al. 2008 ) . Due to its real-world importance and its role as a sub-step in other fundamental clustering algorithms such as HDBSCAN ( Campello et al. 2015 ; Wang et al. 2020 ; Wang et al. 2021a ) , computing the SLD of an input weighted tree has been widely studied by parallel algorithms researchers in recent years, with novel algorithms and implementations being proposed for the shared-memory setting ( Havel et al. 2019 ; Wang et al. 2021a ) , GPUs ( Nolet et al. 2023 ; Sao et al. 2024 ) , and distributed memory settings ( Götz et al. 2018 ; Havel et al. 2019 ) . We also observe that single linkage dendrograms are closely related to Cartesian trees ( Vuillemin 1980 ) , and we formalize the connection in Section 6 of this paper. Traditionally, HAC algorithms have been point-based ( Yu et al. 2021 ) , meaning each pair of points has some distance (or similarity). Taken together, the distances compose a distance matrix. Guided by the observation that this matrix may have many negligible entries in some scenarios, recent studies ( Dhulipala et al. 2021a ; Tseng et al. 2022 ; Dhulipala et al. 2022b ; Yu et al. 2025 ; Bateni et al. 2024 ; Dhulipala et al. 2023 ) have focused on graph-based HAC algorithms. In this setting, the input is a graph which only defines similarities for a subset of the pairs. Due to the rapidly changing nature of modern datasets, it is of significant interest to obtain practical dynamic HAC algorithms that can dynamically maintain a clustering as the underlying data changes. Similar to the static setting, graph-based HAC algorithms are more suitable for fast dynamic algorithms as an insertion or deletion of a point results in a linear number of changes to the similarity matrix in point-based HAC. Indeed, prior studies of HAC in the dynamic setting have focused only on graph-based HAC ( Tseng et al. 2022 ; Yu et al. 2025 ) . For dynamic graph-based HAC, the input is a dynamic graph subject to edge insertions, deletions, or similarity updates. Recently, there has been significant effort to develop parallel batch-dynamic algorithms which process batches of updates or queries for fundamental problems on graphs, ordered sets and maps, and other data structures ( Acar et al. 2019 ; Anderson and Blelloch 2024 ; Anderson and Blelloch 2023 ; Tseng et al. 2022 ; Wang et al. 2021b ; Yesantharao et al. 2021 ; Acar et al. 2020 ; Dhulipala et al. 2020 ; De Man et al. 2024 ; Liu et al. 2022 ; Tseng et al. 2019 ; Dhulipala et al. 2019 ; Dhulipala et al. 2021b ; Dhulipala et al. 2022a ; Men et al. 2025 ) . Compared to sequential dynamic algorithms, such algorithms have the potential to be significantly more applicable in practice as they are not forced to apply the updates or queries one at a time. Motivated by the problem of parallelizing dynamic graph-based single-linkage clustering, Tseng et al. ( Tseng et al. 2022 ) developed a parallel batch-dynamic minimum spanning forest (MSF) algorithm. It is well known that single-linkage clustering can be reduced to computing a minimum spanning tree on the points ( Gower and Ross 1969 ) , or in the case of graph-based HAC, the MSF of the graph. However, the MSF does not directly provide the SLD, and computing the SLD requires non-trivial processing of the MSF. Although dynamically maintaining the MSF of the graph is a crucial step in an end-to-end pipeline for dynamic SLD, Tseng et al. do not maintain the SLD itself. Instead, their algorithm only supports pairwise

Read the complete text