Pith. sign in

REVIEW 3 major objections 4 minor 61 references

Fully-Dynamic Parallel Algorithms for Single-Linkage Clustering

T0 review · 3 major / 4 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper gives the first fully-dynamic algorithms that maintain a single-linkage dendrogram explicitly, with update costs $O(h)$ for insertions, $O(h \log(1+n/h))$ for deletions, and $O(c \log(1+n/c))$ for output-sensitive insertions…

desk verdict First explicit fully-dynamic SLD maintenance with credible height-bounded bounds, but the output-sensitive section rests on a PWS query that, as written, skips connecting vertices and can return the wrong node. read the letter →

arxiv 2506.18384 v1 pith:ZONHIEQE submitted 2025-06-23 cs.DS cs.DC

Quinten De Man , Laxman Dhulipala , Kishen N Gowda This is my paper · ORCID
classification cs.DScs.DC
keywords single-linkageclusteringhierarchicalagglomerativefully-dynamicalgorithmsdendrogrammaintenancerake-compresstreesoutput-sensitiveparallelminimumspanningforest
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Single-linkage clustering builds a dendrogram—a binary tree recording which clusters merge and at what edge weight—and this paper asks whether that tree can be maintained cheaply when the underlying data changes through edge insertions and deletions. Prior dynamic work maintained only a minimum spanning forest, which answers "are these points in the same cluster at threshold $\tau$" queries but does not explicitly give the dendrogram. The paper claims that the dendrogram can be updated in $O(h)$ time per insertion and $O(h \log(1+n/h))$ per deletion, where $h$ is the height of the dendrogram, and that insertions can be processed in $O(c \log(1+n/c))$ time, where $c$ is the number of parent-pointer changes the update causes. It also gives parallel and batch-parallel versions with polylogarithmic depth and work equal to or near these sequential bounds. Since $h \leq n-1$, this makes every single update asymptotically cheaper than recomputing the dendrogram from scratch, and much cheaper when the dendrogram is shallow.

What carries the argument

The spine of an edge in a dendrogram is the node-to-root path starting at that edge's node, and along any spine edge ranks increase monotonically; merging two dendrograms therefore reduces to merging two sorted spines. The update algorithms maintain the dendrogram together with a rake-compress tree—a dynamic tree built from repeated rounds of contraction, supporting links, cuts, connectivity queries, and path decompositions in $O(\log n)$ time. On top of that base, the paper introduces path weight search (PWS), which returns the maximum-weight node on an increasing-weight path below a threshold, and path median queries, so a merge can jump directly to the next node whose parent pointer changes instead of walking the whole spine. The mechanism that makes the output-sensitive bound work is charging: each PWS query is charged to a distinct parent-pointer change, queries are issued in increasing weight order, and the downward search paths are arranged so that each RC-tree node is visited at most twice, bounding the total by the union of $c$ rootward paths.

What would settle it

Run the output-sensitive insertion on a rake-compress tree representing a path-shaped dendrogram, issue the $c$ path weight search queries in increasing weight order, and count the total number of RC-tree nodes visited; any execution visiting more than $O(c \log(1+n/c))$ nodes would refute the charging claim in Section 4.2. Alternatively, construct a single increasing-weight path whose RC-tree path decomposition contains a cluster weight range that overlaps the threshold without containing it, and check whether the PWS query still returns the correct node in $O(\log n)$ time; a wrong answer or a linear scan would falsify the query implementation.

Watch

Extended reading notes

Core claim

On the paper's own terms, the central discovery is that an update to the underlying forest, even though it can rearrange the whole dendrogram in the worst case, only ever forces changes along two node-to-root paths: the spines of the minimum-rank edges incident to the two endpoints. Reusing the spine-merge primitive from static dendrogram computation makes an insertion a merge of two sorted lists of length at most $h$, and a deletion an unmerge of one spine guided by connectivity queries that decide which side of the cut each node belongs to. The paper then shows that maintaining a rake-compress tree over the dendrogram, together with new path weight search queries, lets an insertion find exactly the parent pointers that must change, achieving $O(c \log(1+n/c))$ time. The same machinery yields parallel updates whose work matches the sequential bounds and whose depth is polylogarithmic, and batch updates that process $k$ insertions or deletions in $O(kh \log(1+n/(kh)))$ work with polylogarithmic depth. These are, to the authors' knowledge, the first explicit dendrogram maintenance algorithms that are asymptotically faster than static recomputation.

Load-bearing premise

The results would collapse if the new path weight search and path median queries cannot actually be answered in $O(\log n)$ time per query, or if the union of the $c$ search paths in the rake-compress tree contains more than $O(c \log(1+n/c))$ nodes—the paper sketches that implementation in Section 4.1 and asserts the per-node-visit accounting without giving a formal charge.

Editorial extensions

If this is right

  • Every single edge update is asymptotically cheaper than static recomputation: the static optimum is $\Theta(n \log h)$, while insertions cost $O(h)$ and deletions cost $O(h \log(1+n/h))$, and since $h \leq n-1$ the dynamic cost is never larger.
  • For shallow dendrograms of height $O(\log n)$, insertions cost $O(\log n)$ and deletions cost $O(\log^2 n)$, regimes where static recomputation would be wasteful.
  • Combined with an existing fully-dynamic minimum spanning forest algorithm, the routines give an end-to-end fully-dynamic single-linkage clustering pipeline; combined with a batch-dynamic MSF algorithm, they give a batch-parallel pipeline with polylogarithmic depth.
  • Insertions are near-optimal in an output-sensitive sense: the $O(c \log(1+n/c))$ bound is within a logarithmic factor of the $\Omega(c)$ lower bound, and when only a constant number of parent pointers change the update costs $O(\log n)$, matching an amortized lower bound.
  • Because the SLD of a path graph is a Cartesian tree, the algorithms supply worst-case $O(\log n)$ leaf insertions and deletions in Cartesian trees, improving on prior amortized bounds, and enable cluster-report and cluster-size queries that a bare minimum spanning forest cannot answer in low depth.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A symmetric unmerge of the alternating PWS merge likely yields an output-sensitive deletion algorithm; the paper leaves deletions only in the height-bounded $O(h \log(1+n/h))$ form, so this is a natural next step rather than a claim the paper makes.
  • The output-sensitive charging argument depends only on parent-pointer changes and rootward search paths, so if the PWS implementation is validated, the same bound should transfer to any explicit binary-tree representation of a dendrogram, not just forests.
  • A concrete test of the unproven accounting step would be to instrument an RC tree and count node visits under increasing-weight PWS queries on adversarially shaped dendrograms; the "each node visited at most twice" claim should be checked before implementation effort is invested.
  • The Cartesian-tree equivalence suggests an unstated consequence: dynamic SLD maintenance also yields dynamic range-minimum-query structures under point updates, since the Cartesian tree of an array is exactly the SLD of the corresponding path graph.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper studies the fully-dynamic maintenance of single-linkage dendrograms (SLDs) over a dynamic forest. The authors propose an insertion algorithm in O(h) time and a deletion algorithm in O(h log(1+n/h)) time, where h is the dendrogram height; parallel and batch-parallel versions with poly-logarithmic depth; and an output-sensitive insertion algorithm in O(c log(1+n/c)) time, where c is the number of parent-pointer changes. The algorithms are based on the spine-merge technique of Dhulipala et al. and on rake-compress (RC) trees, and the paper also introduces path weight search and path median queries on RC trees. The claimed results, if correct, would be the first explicit SLD maintenance algorithms asymptotically faster than static recomputation, and they are connected to dynamic Cartesian tree maintenance.

Significance. The problem is well motivated and the paper fills a genuine gap between dynamic minimum spanning forest maintenance and explicit dendrogram maintenance. The height-bounded and output-sensitive bounds are natural and, if established, would be significant contributions to dynamic hierarchical clustering and to the toolbox of parallel dynamic tree queries. The paper relies on prior peer-reviewed techniques (spine-merge in [19], RC trees in [2,5,7]) in a non-circular way, and the proposed PWS and path median queries are interesting primitives in their own right. However, the correctness of the output-sensitive bounds rests on a PWS implementation that is internally inconsistent with the paper's own path median accounting, and the batch-deletion correctness argument is asserted rather than proved. These issues affect the central claims, so the current version is not yet publishable as is.

major comments (3)
  1. [Section 4.1, Definition 4.1 and implementation] The PWS query is internally inconsistent with the path median query. The path median query explicitly adds "the number of clusters in the path decomposition plus one" because the vertices connecting consecutive clusters are not part of any cluster path, but the PWS implementation states that the cluster paths are "disjoint and whose union forms the entire path" and treats the cluster weight ranges as an ordered sequence covering the whole path. If the queried weight w falls in the gap occupied by such a connector vertex and that connector has weight less than w, the procedure returns the maximum of the lower cluster range rather than the connector vertex, which is the true predecessor. The output-sensitive spine merge in Section 4.2 uses PWS to identify exactly the node whose parent changes, so a wrong predecessor produces incorrect parent pointers and invalidates the charge of one PWS query per structural change. Consequently, Theorem 1.2 and the sequential part of Theorem 1.4 are not established as written. The query can likely be repaired by including connector vertices as singleton ranges, but that repair must be given explicitly.
  2. [Section 3.3, Batch Deletions] The batch deletion algorithm is asserted correct because "multiple parent changes to any node all result in the same value," but no proof of this confluence property is provided. For two deleted edges on the same root-to-leaf chain, a node's final parent is the first surviving ancestor after skipping both deleted edges; independent concurrent runs of the single-edge Delete procedure on the original dendrogram, each filtering to one side of its own cut, do not obviously compute this value, and the result can depend on the order in which writes to a shared parent pointer are applied. Since Theorem 1.5's batch deletion bound depends on running the single-deletion procedure concurrently for all deleted edges, this is a load-bearing correctness gap that needs either a formal argument or a redesigned batch procedure.
  3. [Section 3.1, Algorithm 2 and Section 4.2] The algorithms assume that the characteristic edges e*_u and e*_v, the minimum-rank edges incident to the relevant endpoints, can be identified without cost, but no data structure is specified for maintaining these values under edge deletions. If the deleted edge was the minimum-rank incident edge of one of its endpoints, the new minimum can be found by scanning the adjacency list in worst-case time proportional to the degree, which can be Theta(n) and would violate the stated O(h) and O(c log(1+n/c)) bounds. The paper should specify how these characteristic edges are maintained under the dynamic updates and account for the maintenance cost in Theorems 1.1 and 1.2. A per-vertex heap would likely suffice, but this needs to be stated.
minor comments (4)
  1. [Section 3.1] The sentence "As h >= log^2 n" is false in general: a full binary dendrogram with n leaves has h >= ceil(log_2 n), not h >= log^2 n. The subsequent asymptotic accounting for the insertion algorithm works with h >= log n, so the inequality should be corrected.
  2. [Section 4.2 and 4.3] There are typos: "PSW queries" in Section 4.2 should read "PWS queries," and "resursion tree" in Section 4.3 should read "recursion tree."
  3. [Section 2.4] The statement that a path decomposition's cluster paths "forms exactly the path between u and v" should be reconciled with the connector-vertex accounting in Definition 4.2; as written, the two passages contradict each other.
  4. [Section 5, proof of Theorem 5.1] The proof should state whether "height h" counts internal nodes or edges on the spine, since the constructed star of h+1 vertices has an internal-node SLD path of h nodes and the merged tree has 2h+1 internal nodes; the lower bound argument is clear either way, but the presentation would benefit from consistent convention.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the dynamic SLD algorithms use prior peer-reviewed building blocks as subroutines, and the output-sensitive bounds are analyzed against independently defined parameters h and c.

full rationale

The paper's central claims do not reduce to their inputs. Theorem 1.1's insertion algorithm composes the static SLD-Merge of Dhulipala et al. [19], a peer-reviewed and parameter-free building block used only as a subroutine, and the deletion algorithm uses RC-tree connectivity queries whose costs come from Acar et al. and Anderson et al. [2,5,7]; none of these citations assumes the dynamic-SLD theorem being proved. Theorem 1.2 defines c as the number of parent-pointer changes and analyzes the algorithm by counting exactly the PWS queries and RC-tree pointer updates, so the O(c log(1+n/c)) bound is a genuine output-sensitive analysis rather than a restatement of c. There is no fitted parameter renamed as a prediction, and no uniqueness or ansatz is imported from the authors' prior work. The one notable weakness in the text is in Section 4.1: the PWS implementation appears to treat the ordered cluster-path weight ranges as covering the whole path, while the path median query in the same section says vertices connecting consecutive clusters are not part of any cluster path; if that is correct, the PWS implementation may return the wrong predecessor for weights falling in the gaps. That is a correctness gap in the proof as written, not a circular derivation, and therefore it does not raise the circularity score. The paper is also honest that the PWS implementation is sketched and that the sequential accounting of node visits is asserted rather than fully formalized; these are correctness risks, not instances of self-definition or fitted prediction.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The paper introduces new algorithmic queries (PWS, path median) but no invented physical or mathematical entities. The output size c is defined as the number of parent-pointer changes, not a fitted parameter. All free quantities in the algorithms are derived from the input, so there are no free parameters.

assumptions (5)
  • domain assumption Single-linkage clustering on a weighted graph reduces to single-linkage clustering on the minimum spanning forest of the graph.
    Used throughout to justify that the input can be treated as a dynamic forest rather than a general graph; cited to Gower and Ross [29].
  • domain assumption The static SLD algorithm of Dhulipala et al. [19] computes the SLD in O(n log h) work and O(log^2 n log^2 h) depth, and this work bound is optimal.
    Used as the baseline for comparing update costs and for the spine-merge technique (SLD-Merge) in Section 3.1; [19] shares authors with this paper.
  • domain assumption Rake-compress trees support the operations listed in Table 1 with the stated sequential and batch-parallel costs, including batch connectivity queries in O(k log(1+n/k)) work, and the property that c root-paths contain O(c log(1+n/c)) nodes.
    Invoked in Sections 2.4, 3.2, 3.3, and 4; cited to Anderson and Blelloch [2,5,7].
  • standard math The height h of the SLD is at least log n for a forest with n vertices, so O(log n) costs are subsumed by O(h).
    The SLD is a full binary tree with n leaves, so its height is at least log n. The paper instead states h >= log^2 n in Section 3.1, which is false for balanced dendrograms; the weaker bound suffices for the asymptotic claims.
  • domain assumption Parallel tree contraction on the incidence graph requires O(log k) rounds and O(k) total work.
    Used in the batch insertion algorithm (Section 3.3); cited to Miller and Reif [39] and Anderson [5,7].

how reviews work

0 comments
Cite this review

Pith. "Pith review of Fully-Dynamic Parallel Algorithms for Single-Linkage Clustering." pith.science (2026). https://pith.science/paper/ZONHIEQE

@misc{pith2026250618384,
  author       = {Pith},
  title        = {Pith review of: Fully-Dynamic Parallel Algorithms for Single-Linkage Clustering},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ZONHIEQE}},
  note         = {Machine review of arXiv:2506.18384}
}
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$ (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)$ time where $h$ is the height of the dendrogram ($h \leq n-1$). Furthermore, our algorithms are much faster in many cases, such as when $h$ is low. Our first set of results are an insertion algorithm in $O(h)$ time and a deletion algorithm in $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))$ time, where $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.

Figures

Figures reproduced from arXiv: 2506.18384 by the authors.

Figure 1
Figure 1. An example of a single-linkage dendrogram for a tree. The left shows the input tree with weighted edges; the edges are merged in order of increasing rank by the sequential algorithm. The middle shows a typical visualization of a dendrogram where the “height” of each edge corresponds to its rank or weight. The right shows the SLD data structure which only stores nodes for edges and parent-pointers. The single-linkage… view at source ↗
Figure 2
Figure 2. An illustration of an edge insertion and an edge deletion in DynSLD. The top of each side shows the input tree and the edge update. The bottom of each side shows the corresponding changes to the dendrogram. The left side depicts the insertion of edge (𝑒, ℎ) (for the sake of brevity we depict both spine merges in one step). The right side depicts its deletion. For insertions, the two characteristic spines are merged … view at source ↗
Figure 3
Figure 3. Depiction of the batch insertion algorithm. On the left, the updates form a tree where the nodes represent separate components of the input forest, and the edges represent edges in the batch of insertions between two components. The algorithm performs multiple rounds of tree contraction, where each individual contraction forms a star pattern. The right shows the process for merging the single-linkage dendrograms for… view at source ↗
Figures from the paper (2 more)
Figure 4
Figure 4. Figure 4: A depiction of the output-sensitive algorithm for merging two spines. The nodes are depicted with their weight rather than the edge they represent. In each step, a blue node uses a PWS query to find the node in the opposite spine which should be its child. The child is…
Figure 5
Figure 5. Figure 5: A depiction of the parallel output-sensitive spine merge algorithm. First the median value (dark green node) in one spine is found. Then, PWS queries are used to find the values 𝑥𝑣 and 𝑦𝑣 (dark orange and dark blue nodes) in the other spine “surrounding” that median va…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

61 extracted references · 56 canonical work pages

  1. [19]

    Gowda, and Yan Gu

    Laxman Dhulipala, Xiaojun Dong, Kishen N. Gowda, and Yan Gu. 2024. Optimal Parallel Algorithms for Dendrogram Computation and Single-Linkage Clustering. InACM Symposium on Parallelism in Algorithms and Architectures (SPAA)

    work page 2024

  2. [1]

    Acar, Daniel Anderson, Guy E

    Umut A. Acar, Daniel Anderson, Guy E. Blelloch, and Laxman Dhulipala. 2019. Parallel Batch-Dynamic Graph Connectivity. InACM Symposium on Parallelism in Algorithms and Architectures (SPAA). ACM

    work page 2019

  3. [2]

    Acar, Daniel Anderson, Guy E

    Umut A. Acar, Daniel Anderson, Guy E. Blelloch, Laxman Dhulipala, and Sam Westrick. 2020. Parallel Batch-Dynamic Trees via Change Propagation. InEuro- pean Symposium on Algorithms (ESA)

    work page 2020

  4. [3]

    Acar, Guy E

    Umut A. Acar, Guy E. Blelloch, Robert Harper, Jorge L. Vittes, and Shan Le- ung Maverick Woo. 2004. Dynamizing static algorithms, with applications to dynamic trees and history independence. InACM-SIAM Symposium on Discrete Algorithms (SODA)

    work page 2004

  5. [4]

    Acar, Guy E

    Umut A. Acar, Guy E. Blelloch, and Jorge L. Vittes. 2005. An Experimental Analysis of Change Propagation in Dynamic Trees. InProceedings of the Seventh Workshop on Algorithm Engineering and Experiments and the Second Workshop on Analytic Algorithmics and Combinatorics (ALENEX /ANALCO)

    work page 2005

  6. [5]

    2023.Parallel Batch-Dynamic Algorithms Dynamic Trees, Graphs, and Self-Adjusting Computation

    Daniel Anderson. 2023.Parallel Batch-Dynamic Algorithms Dynamic Trees, Graphs, and Self-Adjusting Computation. Ph. D. Dissertation. Carnegie Mellon University

    work page 2023

  7. [6]

    Deterministic and Work-Efficient Parallel Batch-Dynamic Trees in Low Span

    Daniel Anderson and Guy E. Blelloch. 2023. Deterministic and Work-Efficient Parallel Batch-Dynamic Trees in Low Span. arXiv:2306.08786 [cs.DS] 14

    work page Pith review arXiv 2023

  8. [7]

    Blelloch

    Daniel Anderson and Guy E. Blelloch. 2024. Deterministic and Low-Span Work- Efficient Parallel Batch-Dynamic Trees. InACM Symposium on Parallelism in Algorithms and Architectures (SPAA)

    work page 2024

Show all 61 references
  1. [8]

    Dalya Baron. 2019. Machine Learning in Astronomy: a practical overview. arXiv:1904.07248 [astro-ph.IM]

    2019 arXiv

  2. [9]

    MohammadHossein Bateni, Laxman Dhulipala, Kishen N Gowda, D Ellis Her- shkowitz, Rajesh Jayaram, and Jakub Lacki. 2024. It’s Hard to HAC Average Linkage!. InIntl. Colloq. on Automata, Languages and Programming (ICALP)

    2024

  3. [10]

    Bender and Martin Farach-Colton

    Michael A. Bender and Martin Farach-Colton. 2000. The LCA problem revisited. InLatin American Symposium on Theoretical Informatics (LATIN)

    2000

  4. [11]

    Iwona Bialynicka-Birula and Roberto Grossi. 2006. Amortized Rigidness in Dynamic Cartesian Trees. InSymposium on Theoretical Aspects of Computer Science (STACS)

    2006

  5. [12]

    Blelloch, Jeremy T

    Guy E. Blelloch, Jeremy T. Fineman, Yan Gu, and Yihan Sun. 2020. Optimal Parallel Algorithms in the Binary-Forking Model. InACM Symposium on Parallelism in Algorithms and Architectures (SPAA)

    2020

  6. [13]

    Ricardo JGB Campello, Davoud Moulavi, Arthur Zimek, and Jörg Sander. 2015. Hierarchical density estimates for data clustering, visualization, and outlier de- tection.ACM Transactions on Knowledge Discovery from Data (TKDD)10, 1 (2015)

    2015

  7. [14]

    Richard Cole. 1988. Parallel Merge Sort.SIAM J. on Computing17, 4 (1988)

    1988

  8. [15]

    Quinten De Man, Laxman Dhulipala, Adam Karczmarz, Jakub Łącki, Julian Shun, and Zhongqi Wang. 2024. Towards Scalable and Practical Batch-Dynamic Con- nectivity.Proceedings of the VLDB Endowment (PVLDB)18, 3 (2024)

    2024

  9. [16]

    Demaine, Gad M

    Erik D. Demaine, Gad M. Landau, and Oren Weimann. 2014. On Cartesian Trees and Range Minimum Queries.Algorithmica68, 3 (2014)

    2014

  10. [17]

    Laxman Dhulipala, Guy E Blelloch, Yan Gu, and Yihan Sun. 2022. Pac-trees: Supporting parallel and compressed purely-functional collections. InProceedings of the 43rd ACM SIGPLAN International Conference on Programming Language Design and Implementation. 108–121

    2022

  11. [18]

    Laxman Dhulipala, Guy E Blelloch, and Julian Shun. 2019. Low-latency graph streaming using compressed purely-functional trees. InACM Conference on Pro- gramming Language Design and Implementation (PLDI)

    2019

  12. [20]

    Laxman Dhulipala, David Durfee, Janardhan Kulkarni, Richard Peng, Saurabh Sawlani, and Xiaorui Sun. 2020. Parallel Batch-Dynamic Graphs: Algorithms and Lower Bounds. InACM-SIAM Symposium on Discrete Algorithms (SODA)

    2020

  13. [21]

    Laxman Dhulipala, David Eisenstat, Jakub Łącki, Vahab Mirrokni, and Jessica Shi. 2021. Hierarchical agglomerative graph clustering in nearly-linear time. In International Conference on Machine Learning (ICML). PMLR

    2021

  14. [22]

    Laxman Dhulipala, David Eisenstat, Jakub Łącki, Vahab Mirrokni, and Jessica Shi

  15. [23]

    Laxman Dhulipala, Jakub Łącki, Jason Lee, and Vahab Mirrokni. 2023. Terahac: Hierarchical agglomerative clustering of trillion-edge graphs.Proceedings of the ACM on Management of Data1, 3 (2023)

    2023

  16. [24]

    Laxman Dhulipala, Quanquan C Liu, Julian Shun, and Shangdi Yu. 2021. Paral- lel batch-dynamic k-clique counting. InACM-SIAM Symposium on Algorithmic Principles of Computer Systems (APOCS)

    2021

  17. [25]

    ED Feigelson and GJ Babu. 1998. Statistical methodology for large astronomical surveys. InSymposium-International Astronomical Union, Vol. 179. Cambridge University Press

    1998

  18. [26]

    Greg N Frederickson. 1985. Data structures for on-line updating of minimum spanning trees, with applications.SIAM J. on Computing14, 4 (1985)

    1985

  19. [27]

    Molly Gasperini, Andrew J Hill, José L McFaline-Figueroa, Beth Martin, Seungsoo Kim, Melissa D Zhang, Dana Jackson, Anh Leith, Jacob Schreiber, William S Noble, et al. 2019. A genome-wide framework for mapping gene regulation via cellular genetic screens.Cell176, 1 (2019)

    2019

  20. [28]

    Markus Götz, Gabriele Cavallaro, Thierry Géraud, Matthias Book, and Morris Riedel. 2018. Parallel computation of component trees on distributed memory machines.IEEE Transactions on Parallel and Distributed Systems29, 11 (2018)

    2018

  21. [29]

    J. C. Gower and G. J. S. Ross. 1969. Minimum Spanning Trees and Single Linkage Cluster Analysis.Journal of the Royal Statistical Society. Series C (Applied Statistics) 18, 1 (1969)

    1969

  22. [30]

    Jiří Havel, François Merciol, and Sébastien Lefèvre. 2019. Efficient tree construc- tion for multiscale image representation and processing.Journal of Real-Time Image Processing16 (2019)

    2019

  23. [31]

    David B Henry, Patrick H Tolan, and Deborah Gorman-Smith. 2005. Cluster analysis in family psychology research.Journal of Family Psychology19, 1 (2005)

    2005

  24. [32]

    Monika Rauch Henzinger and Valerie King. 1995. Randomized dynamic graph algorithms with polylogarithmic time per operation. InACM Symposium on Theory of Computing (STOC)

    1995

  25. [33]

    Jacob Holm, Kristian De Lichtenberg, and Mikkel Thorup. 2001. Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity.J. ACM48, 4 (2001)

    2001

  26. [34]

    1992.An Introduction to Parallel Algorithms

    Joseph JáJá. 1992.An Introduction to Parallel Algorithms. Addison Wesley Long- man Publishing Co., Inc., USA

    1992

  27. [35]

    Ivica Letunic and Peer Bork. 2007. Interactive Tree Of Life (iTOL): an online tool for phylogenetic tree display and annotation.Bioinformatics23, 1 (2007)

    2007

  28. [36]

    Quanquan C Liu, Jessica Shi, Shangdi Yu, Laxman Dhulipala, and Julian Shun

  29. [37]

    2008.Intro- duction to Information Retrieval

    Christopher D Manning, Prabhakar Raghavan, and Hinrich Schütze. 2008.Intro- duction to Information Retrieval. Cambridge University Press

    2008

  30. [38]

    InProceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures

    Parallel batch-dynamic algorithms for k-core decomposition and related graph problems. InProceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures. 191–204

  31. [39]

    Gary L Miller and John H Reif. 1985. Parallel tree contraction and its application. InIEEE Symposium on Foundations of Computer Science (FOCS), Vol. 26

    1985

  32. [40]

    Ziyang Men, Zheqi Shen, Yan Gu, and Yihan Sun. 2025. Parallel kd-tree with Batch Updates.Proceedings of the ACM on Management of Data3, 1 (2025), 1–26

    2025

  33. [41]

    Corey J Nolet, Divye Gala, Alex Fender, Mahesh Doijade, Joe Eaton, Edward Raff, John Zedlewski, Brad Rees, and Tim Oates. 2023. cuSLINK: Single-linkage Agglomerative Clustering on the GPU. InJoint European Conference on Machine Learning and Knowledge Discovery in Databases

    2023

  34. [42]

    Nicholas Monath, Manzil Zaheer, and Andrew McCallum. 2023. Online level-wise hierarchical clustering. InSIGKDD Conference on Knowledge Discovery and Data Mining (KDD)

    2023

  35. [43]

    Mihai Patraşcu and Erik D. Demaine. 2004. Lower bounds for dynamic connec- tivity. InACM Symposium on Theory of Computing (STOC)

    2004

  36. [44]

    Georgios K Ouzounis and Pierre Soille. 2012. The alpha-tree algorithm.JRC Scientific and Policy Report(2012)

    2012

  37. [45]

    Blelloch

    Julian Shun and Guy E. Blelloch. 2014. A Simple Parallel Cartesian Tree Algorithm and Its Application to Parallel Suffix Tree Construction.ACM Transactions on Parallel Computing (TOPC)1, 1 (2014)

    2014

  38. [46]

    Piyush Sao, Andrey Prokopenko, and Damien Lebrun-Grandie. 2024. PANDORA: A Parallel Dendrogram Construction Algorithm for Single Linkage Clustering on GPU. InInternational Conference on Parallel Processing (ICPP)

    2024

  39. [47]

    Thomas Tseng, Laxman Dhulipala, and Guy Blelloch. 2019. Batch-parallel eu- ler tour trees. In2019 Proceedings of the Twenty-First Workshop on Algorithm Engineering and Experiments (ALENEX). SIAM, 92–106

    2019

  40. [48]

    Daniel D Sleator and Robert Endre Tarjan. 1983. A data structure for dynamic trees.J. Computer and System Sciences26, 3 (1983)

    1983

  41. [49]

    Jean Vuillemin. 1980. A unifying look at data structures.Commun. ACM23, 4 (1980)

    1980

  42. [50]

    Tom Tseng, Laxman Dhulipala, and Julian Shun. 2022. Parallel Batch-Dynamic Minimum Spanning Forest and the Efficiency of Dynamic Agglomerative Graph Clustering. InACM Symposium on Parallelism in Algorithms and Architectures (SPAA)

    2022

  43. [51]

    Yiqiu Wang, Shangdi Yu, Yan Gu, and Julian Shun. 2021. Fast Parallel Algorithms for Euclidean Minimum Spanning Tree and Hierarchical Spatial Clustering. In ACM SIGMOD International Conference on Management of Data (SIGMOD)

    2021

  44. [52]

    Yiqiu Wang, Yan Gu, and Julian Shun. 2020. Theoretically-Efficient and Practical Parallel DBSCAN. InACM SIGMOD International Conference on Management of Data (SIGMOD)

    2020

  45. [53]

    Christian Wulff-Nilsen. 2017. Fully-dynamic minimum spanning forest with improved worst-case update time. InACM Symposium on Theory of Computing (STOC)

    2017

  46. [54]

    Yiqiu Wang, Shangdi Yu, Yan Gu, and Julian Shun. 2021. A Parallel Batch-Dynamic Data Structure for the Closest Pair Problem. arXiv:2010.02379 [cs.DS]

    2021 arXiv

  47. [55]

    Loïc Yengo, Sailaja Vedantam, Eirini Marouli, Julia Sidorenko, Eric Bartell, Saori Sakaue, Marielisa Graff, Anders U Eliasen, Yunxuan Jiang, Sridharan Raghavan, et al. 2022. A saturated map of common genetic variants associated with human height.Nature610, 7933 (2022)

    2022

  48. [56]

    Andrew Chi-Chih Yao. 1981. Should Tables Be Sorted?J. ACM28, 3 (1981)

    1981

  49. [57]

    Odilia Yim and Kylee T Ramdeen. 2015. Hierarchical cluster analysis: comparison of three linkage measures and application to psychological data.The quantitative methods for psychology11, 1 (2015)

    2015

  50. [58]

    Rahul Yesantharao, Yiqiu Wang, Laxman Dhulipala, and Julian Shun. 2021. Paral- lel Batch-Dynamic𝑘d-Trees. arXiv:2112.06188 [cs.DS]

    2021 arXiv

  51. [59]

    Shangdi Yu, Yiqiu Wang, Yan Gu, Laxman Dhulipala, and Julian Shun. 2021. ParChain: A Framework for Parallel Hierarchical Agglomerative Clustering using Nearest-Neighbor Chain.Proceedings of the VLDB Endowment (PVLDB)(2021). 15

    2021

  52. [60]

    Shangdi Yu, Laxman Dhulipala, Jakub Łącki, and Nikos Parotsidis. 2025. Dyn- HAC: Fully Dynamic Approximate Hierarchical Agglomerative Clustering. arXiv:2501.07745 [cs.DS]

    2025 arXiv

  53. [2022]

    InNeural Information Processing Systems (NeurIPS)

    Hierarchical Agglomerative Graph Clustering in Poly-Logarithmic Depth. InNeural Information Processing Systems (NeurIPS)

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.