Pith. sign in

REVIEW 2 major objections 5 minor 1 cited by

DynHAC: Fully Dynamic Approximate Hierarchical Agglomerative Clustering

T0 review · 2 major / 5 minor · reviewed 2026-08-10 · deepseek-v4-flash

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

Pith's one-line read The paper claims that DynHAC maintains a $(1+\epsilon)$-approximate average-linkage HAC dendrogram under both insertions and deletions, and that this is the first such guarantee for dynamic HAC.

desk verdict First dynamic (1+ε)-approximate average-linkage HAC algorithm, but the main correctness theorem rests on an unproved M-stability invariant in Lemma C.1. read the letter →

arxiv 2501.07745 v1 pith:XTA7MMT7 submitted 2025-01-13 cs.DS

Shangdi Yu , Laxman Dhulipala , Jakub {L}ącki , Nikos Parotsidis This is my paper · ORCID
classification cs.DS MSC 68W2568W4005C85
keywords hierarchicalagglomerativeclusteringaveragelinkagedynamicgraphalgorithms(1+epsilon)-approximationdendrogramdirtypartitionsnormalizedmutualinformation
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

This paper introduces DynHAC, an algorithm that keeps a hierarchical agglomerative clustering (HAC) dendrogram up to date as points are inserted into or deleted from a similarity graph. The claim is that the maintained dendrogram remains a $(1+\epsilon)$-approximation of what an exact average-linkage HAC would produce, which would let streaming and rapidly changing datasets use HAC without repeatedly recomputing from scratch. DynHAC is presented as the first dynamic average-linkage HAC algorithm with such a guarantee, and the authors report update processing up to 423x faster than static recomputation while keeping cluster quality close to the static baseline and above existing dynamic methods. If the guarantee holds, dynamic HAC stops being a heuristic and becomes a maintainable data structure.

What carries the argument

The load-bearing object is the $(1+\epsilon)$-good merge: a merge of edge $uv$ is good when $\max(w_{\max}(u), w_{\max}(v)) / \min(M(u), M(v), \bar{w}(uv)) \le 1+\epsilon$, where $w_{\max}$ is the largest normalized weight of an incident edge and $M$ is the smallest linkage similarity used in building the cluster. The SubgraphHAC routine performs only good merges inside a partition subgraph, and the earlier partitioned HAC algorithm proved that any dendrogram built from a sequence of good merges is $(1+\epsilon)$-approximate. DynHAC's mechanism is to use a red/blue partition-id scheme to identify exactly those partitions whose good merges could have been invalidated by an update, rerun SubgraphHAC only on those dirty partitions, and leave the rest untouched; correctness then reduces to showing a clean partition contains no stale merge.

What would settle it

Construct a small graph with a red/blue coloring in which a cluster $c$ formed by earlier merges has no red neighbor (so its partition id is $c$, a blue vertex), then insert a high-weight edge from $c$ to a new vertex. The dirty-partition algorithm marks the new partition but, by its condition that an old partition is only marked if it is not blue, does not mark $c$'s partition; computing the good-merge ratio $\max(w_{\max}(u), w_{\max}(v)) / \min(M(u), M(v), \bar{w}(uv))$ for the kept merges that built $c$ after the insertion would settle whether any exceeds $1+\epsilon$.

Watch

Extended reading notes

Core claim

On the paper's own terms, the core discovery is that the sensitivity of HAC to updates can be contained: although a single insertion can change an entire dendrogram in the worst case, one can localize the damage by partitioning the graph into small pieces, running a $(1+\epsilon)$-approximate HAC inside each piece, and re-running only the pieces whose input changed, called dirty partitions. DynHAC maintains the partition at each round, the input graph, the vertex-to-vertex mapping between rounds, and the minimum merge similarity of every cluster; when an update arrives it recomputes dirty partitions from scratch and rewrites only the affected ancestors of the dendrogram. The paper's Theorem C.1 asserts that every merge DynHAC ever makes remains $(1+\epsilon)$-good, so by the good-merge lemma the maintained dendrogram is a $(1+\epsilon)$-approximation under both node insertions and deletions.

Load-bearing premise

The argument relies on the claim that every vertex whose largest incident merge-similarity increases lands in a partition that gets marked dirty and re-clustered; if an old partition is skipped while one of its vertices gains a heavier neighbor, an old good merge can silently become bad and the $(1+\epsilon)$ guarantee no longer follows.

Editorial extensions

If this is right

  • If Theorem C.1 holds, dynamic average-linkage HAC becomes a data-structure problem rather than a periodic batch job: insertions and deletions can be absorbed while preserving a provable approximation bound.
  • The dirty-partition locality bound means the cost of an update is tied to the 4-hop neighborhood of the changed nodes, so updates that are locally contained stay cheap even in large graphs.
  • Experiments indicate quality stays close to static HAC — NMI within about 0.0014 to 0.03 on the tested datasets — and up to 0.21 higher than the leading dynamic baselines, so the theoretical guarantee translates into practice.
  • The approximation parameter trades speed for quality in a controlled way: $\epsilon=0.1$ is up to about 1.93x faster than exact HAC for insertions and $\epsilon=1$ up to about 4.22x for deletions, with only small NMI changes.

Reading between the lines

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

  • The dirty-partition locality suggests a batch-dynamic variant could process many simultaneous insertions and deletions by taking the union of their dirty partitions; the paper does not explore this, but its definitions invite it.
  • If a good-merge condition can be defined for other linkage functions, the same round-and-recompute skeleton might extend beyond average linkage; the paper treats only average linkage.
  • The reported speedups are measured on graphs built from approximate nearest neighbors, so a full streaming deployment would also need to maintain the nearest-neighbor graph dynamically, which the paper leaves to the graph maintenance layer.
  • The paper cites a worst-case lower bound of $n^{\Omega(1)}$ per update for dynamic HAC, so no algorithm can be both fast and exact on all instances; DynHAC's practical wager is that real graphs have localized change, and the 4-hop dirty-partition bound is the formal face of that wager.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 5 minor

Summary. The paper introduces DynHAC, a fully dynamic algorithm for maintaining an average-linkage hierarchical agglomerative clustering (HAC) dendrogram under point insertions and deletions, with a claimed (1+ε)-approximation guarantee. The algorithm builds on the partition-based framework of TeraHAC: in each round it partitions the current contracted graph, reruns SubgraphHAC from scratch on a set of "dirty" partitions, and propagates the resulting newly contracted vertices and edges to the next round. The central theoretical claim (Theorem C.1) is that every merge made by DynHAC is (1+ε)-good, so by Lemma 2.1 the maintained dendrogram is (1+ε)-approximate. The paper also states bounds on the total size of dirty partitions per round (Theorem C.2) and on initialization (Theorem C.3), and reports experiments on MNIST, ALOI, and ILSVRC showing large speedups over static HAC and improved NMI over the dynamic baselines GRINCH and Grove.

Significance. If the correctness proof can be completed, DynHAC would be the first fully dynamic algorithm for average-linkage HAC with a (1+ε) approximation guarantee, a natural and significant contribution given the recent conditional lower bounds for dynamic HAC. The paper is clearly written, builds sensibly on the prior TeraHAC structural results, and includes an experimental study with released code and data, which strengthens the practical relevance. However, the approximation guarantee rests on Lemma C.1, and the current proof of that lemma has a gap in the treatment of the M(v) invariant that is load-bearing for Theorem C.1. The experimental speedups and NMI comparisons are likely unaffected by this gap, but the main theoretical claim is not established as written.

major comments (2)
  1. [Appendix C, Lemma C.1, case (2)] The proof of Lemma C.1 dismisses the case that M(u) decreases with the sentence "Only nodes with the same merge sequence can have the same node id. So M(u) cannot change." This invariant is neither defined nor proved anywhere in the manuscript, and it appears to be false under the algorithm's id-reuse policy. In Section 3 ("Update vertex mapping") and Algorithm 5, a vertex in the current round can be mapped to an already-existing vertex in the next round whose merge history is different: for example, an old vertex u = merge(a,b) can be replaced by a new vertex u = merge(a,c) with M(c) < M(b), while keeping the same id. Such a change need not put u, or any neighbor of u, into DeltaP, so the partition containing u is not marked dirty and a previously good merge involving u can become non-good. The same mechanism can change the size S(u) of a contracted vertex, which can increase wmax(x) for a neighbor x without x appearing in DeltaP, undermining case (1) as well. Since Lemma C.1 is the key step in the proof of Theorem C.1, the (1+ε)-approximation guarantee is not established. The authors should either prove the M-stability and wmax-stability invariants under a precise specification of how vertex ids are assigned and reused, or modify the algorithm (e.g., by giving fresh ids to contracted vertices or by marking partitions dirty whenever any incident M or size value changes).
  2. [Appendix C, Theorem C.2] The proof of Theorem C.2 is too terse to constitute a valid bound. It asserts that an inserted or deleted node x can make at most its 4-hop neighborhood dirty because partition subgraphs span 2-hop neighborhoods, but it does not account for the fact that re-running SubgraphHAC in one partition changes the contracted vertices and their sizes passed to the next round, which can cascade and mark additional partitions dirty in subsequent rounds. A formal inductive argument over rounds is needed to justify the claimed bound, or the statement should be weakened to an empirical observation.
minor comments (5)
  1. [Section 1.1] The word "appendinx" should be "appendix".
  2. [Abstract] The phrase "consistent with what a full recomputation from scratch would have output" is stronger than what is proved; Theorem C.1 only establishes that the maintained dendrogram is (1+ε)-approximate, not that it matches the output of a particular recomputation. Please rephrase.
  3. [Algorithm 2] Line 6 checks "if Vi+1 is empty" before Vi+1 has been computed (it is initialized only in Line 10). The accompanying text suggests the intended condition is about whether the graph in the next round has any vertex, but the pseudocode should be clarified.
  4. [Section 3, Update vertex mapping] The parameter list of Algorithm 5 includes "Ddirty", which is not described in the calling context (Algorithm 2, Line 16). The mismatch should be fixed.
  5. [Section 2, Preliminaries] The contraction operation is described as merging x and y into a new vertex z, but the manuscript never states how the id of z is chosen. Since id stability is used in the correctness proof (Lemma C.1), the id assignment rule should be specified precisely.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the dynamic approximation guarantee is parametric in epsilon and rests on prior published TeraHAC results, not on a redefinition or fitted input.

full rationale

DynHAC's central theorem, Theorem C.1, is derived from Lemma C.1 plus Lemma 2.1, which is quoted from TeraHAC [1] and states that any dendrogram produced by a sequence of (1+epsilon)-good merges is (1+epsilon)-approximate. Although [1] shares two authors with this paper, it is prior published work with its own proofs; the present paper does not redefine the approximation notion in terms of its own output, and no parameter is fitted to force the guarantee, since epsilon is a free input and the analysis holds for any choice. The dirty-partition argument is the genuinely new dynamic content and does not reduce by construction to the static good-merge lemma. The experimental claims (speedups and NMI differences) are measurements against external baselines, not derived predictions. The skeptical concern about Lemma C.1, that node-id reuse could lower M(u) without marking a partition dirty, is a possible proof gap in the soundness argument, not a circularity: even if correct, it would make Theorem C.1 unsupported, but it would not make the theorem equivalent to its own assumptions. Under the hard rules, a missing proof or disputed invariant is a correctness risk, not evidence of a circular derivation.

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

The correctness proof depends on prior results from TeraHAC [1] (by overlapping authors) for the goodness-of-merge framework, and on a new invariant (Lemma C.1) about dirty partitions. The latter is the main fragile assumption. No new physical or conceptual entities are introduced.

free parameters (3)
  • epsilon (approximation parameter) = 0.1 (default), also 1.0 tested
    Chosen by the user; the theoretical guarantee holds for any epsilon. It controls the speed-quality tradeoff and is not fitted to data.
  • threshold t (linkage similarity stopping threshold) = 0.0001 for MNIST, 0.01 for ALOI and ILSVRC_SMALL
    Chosen by the user to truncate the dendrogram; not fitted to the target result. The algorithm maintains the dendrogram only up to this similarity threshold.
  • number of nearest neighbors k for graph construction = 50
    Used to build the sparse similarity graph in experiments; standard choice and not part of the theoretical claim.
assumptions (5)
  • domain assumption Lemma 2.1: Any dendrogram produced by a sequence of (1+epsilon)-good merges is (1+epsilon) approximate.
    Proved in TeraHAC [1], by largely the same authors, and used as the foundation of DynHAC's correctness (Section 2, Lemma 2.1).
  • domain assumption SubgraphHAC (from TeraHAC) runs in O((m+n) log^2 n) and produces (1+epsilon)-good merges.
    Used as a black box in DynHAC (Algorithm 2, lines 12-13). Properties are taken from [1].
  • domain assumption Each round colors vertices red/blue uniformly at random; partitions are based on highest-weight red neighbor.
    The partition scheme affects running time but not correctness (Section 3, Partitioning). It is used to define dirty partitions and Lemma 3.1.
  • domain assumption The threshold t is fixed across updates; the algorithm maintains the dendrogram only up to linkage similarity t.
    Stated in Section 3, Handling an update: 'we assume that t is the same across all updates'. This limits the scope of the maintained dendrogram.
  • ad hoc to paper Lemma C.1: If a partition is not dirty, all (1+epsilon)-good merges within it remain good.
    This is the key invariant of the dynamic update rule; its proof is only sketched and has a gap regarding blue partition representatives (Appendix C).

how reviews work

0 comments
Cite this review

Pith. "Pith review of DynHAC: Fully Dynamic Approximate Hierarchical Agglomerative Clustering." pith.science (2026). https://pith.science/paper/XTA7MMT7

@misc{pith2026250107745,
  author       = {Pith},
  title        = {Pith review of: DynHAC: Fully Dynamic Approximate Hierarchical Agglomerative Clustering},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/XTA7MMT7}},
  note         = {Machine review of arXiv:2501.07745}
}
read the original abstract

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+\epsilon approximate solution. Our approach leverages recent structural results on (1+\epsilon)-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.

Figures

Figures reproduced from arXiv: 2501.07745 by the authors.

Figure 1
Figure 1. Quality of clustering algorithm. B1, . . . , Bi . We use this approach instead of finding the nearest neighbors considering all points to prevent each point loosing too many neighbors during the deletion sequence, i.e. we ensure that each point has many neighbors that are deleted after it. For Static HAC, we use the same construction with 100 batches, and run static HAC on the graph. For GRINCH insertion and deletio… view at source ↗
Figure 2
Figure 2. Running times. thresholds. For Grove, we look at the clustering of all levels, and choose the one with highest NMI. 4.1 Comparing with Baselines Figures 1 and 2 depict the NMI and clustering time of the algorithms. Quality. We show that DynHAC maintains a high quality dendrogram. Figure 1a shows the NMI of the clustering after all insertions. Figure 1b shows the NMI of the algorithms after each update on MNIST. We s… view at source ↗
Figure 3
Figure 3. Update speedup over ϵ = 0 and NMI of the last 1% insertions on data sets with different ϵ values. Deletions are similar. E Performance Analysis Varying ϵ [PITH_FULL_IMAGE:figures/full_fig_p014_3.png] view at source ↗
Figures from the paper (9 more)
Figure 5
Figure 5. Figure 5: Running time and quality on ALOI for static HAC and our [PITH_FULL_IMAGE:figures/full_fig_p015_5.png]
Figure 6
Figure 6. Figure 6: Running time and quality on ILSVRC for static HAC and our [PITH_FULL_IMAGE:figures/full_fig_p015_6.png]
Figure 7
Figure 7. Figure 7: DynHAC Insertion with different ϵ values on MNIST. 15 [PITH_FULL_IMAGE:figures/full_fig_p015_7.png]
Figure 8
Figure 8. Figure 8: DynHAC Deletion with different ϵ values on MNIST. 107000 107200 107400 107600 107800 108000 Num. Points 0.01 0.1 1 10 Clustering Time (s) 107000107200107400107600107800108000 Num. Points 0.878 0.880 0.882 0.884 0.886 NMI 0.0 0.1 1.0 [PITH_FULL_IMAGE:figures/full_fig_p…
Figure 9
Figure 9. Figure 9: DynHAC Insertion with different ϵ values on ALOI. 0 200 400 600 800 1000 Num. Points 0.01 0.1 1 10 Clustering Time (s) 107000 107200 107400 107600 107800 Num. Points 0.882 0.884 0.886 0.888 0.890 NMI 0.0 0.1 1.0 [PITH_FULL_IMAGE:figures/full_fig_p016_9.png]
Figure 10
Figure 10. Figure 10: DynHAC Deletion with different ϵ values on ALOI [PITH_FULL_IMAGE:figures/full_fig_p016_10.png]
Figure 11
Figure 11. Figure 11: DynHAC Insertion with different ϵ values on ILSVRC. 0 100 200 300 400 500 Num. Points 10 0 10 1 Clustering Time (s) 49500 49600 49700 49800 49900 Num. Points 0.884 0.885 0.886 0.887 0.888 NMI 0.0 0.1 1.0 [PITH_FULL_IMAGE:figures/full_fig_p017_11.png]
Figure 12
Figure 12. Figure 12: DynHAC Deletion with different ϵ values on ILSVRC. MNIST ALOI ILSVRC_SMALL 0 1 2 3 4 Speedup over epsilon=0 Insertions 0.0 0.1 1.0 MNIST ALOI ILSVRC_SMALL Dataset 0 1 2 3 4 Speedup over epsilon=0 Deletions MNIST ALOI ILSVRC_SMALL Dataset 0.86 0.88 0.90 0.92 NMI Insert…
Figure 13
Figure 13. Figure 13: Speedup of DynHAC with different epsilon values over ϵ = 0, and the NMI values when using different epsilon values. 17 [PITH_FULL_IMAGE:figures/full_fig_p017_13.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Parallel Hierarchical Agglomerative Clustering in Low Dimensions

    cs.DS 2025-07 conditional novelty 8.0 of 10

    Centroid and Ward's hierarchical agglomerative clustering admit polylogarithmic-depth parallel algorithms in low dimensions via a new proof that their dendrograms are shallow.

Reference graph

Works this paper leans on

62 extracted references · 59 canonical work pages · cited by 1 Pith paper

  1. [1]

    Terahac: Hierarchical agglomerative clustering of trillion-edge graphs,

    L. Dhulipala, J. Łącki, J. Lee, and V. Mirrokni, “Terahac: Hierarchical agglomerative clustering of trillion-edge graphs,” SIGMOD, 2023

    work page 2023

  2. [2]

    C. D. Manning, P. Raghavan, and H. Schütze, Introduction to Information Retrieval. Cambridge University Press, 2008

    work page 2008

  3. [3]

    A survey of clustering data mining techniques,

    P. Berkhin, “A survey of clustering data mining techniques,” in Grouping Multidimensional Data. Springer, 2006

    work page 2006

  4. [4]

    C. C. Aggarwal and C. K. Reddy, Eds., Data Clustering: Algorithms and Applications. CRCPress, 2014

    work page 2014

  5. [5]

    Efficient clustering and matching for object class recognition

    B. Leibe, K. Mikolajczyk, and B. Schiele, “Efficient clustering and matching for object class recognition.” in BMVC, 2006

    work page 2006

  6. [6]

    Algorithms for hier- archical clustering: an overview,

    F. Murtagh and P. Contreras, “Algorithms for hier- archical clustering: an overview,”Wiley Interdisci- plinary Reviews: Data Mining and Knowledge Dis- covery, vol. 2, no. 1, 2012

    work page 2012

  7. [7]

    Algorithms for hierarchical clustering: an overview, II,

    ——, “Algorithms for hierarchical clustering: an overview, II,”Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, vol. 7, no. 6, 2017

    work page 2017

  8. [8]

    Modern hierarchical, agglomerative clus- tering algorithms,

    D. Müllner, “Modern hierarchical, agglomerative clus- tering algorithms,”arXiv preprint arXiv:1109.2378, 2011

    arXiv 2011

Show all 62 references
  1. [9]

    fastcluster: Fast hierarchical, agglomerative clustering routines for r and python,

    ——, “fastcluster: Fast hierarchical, agglomerative clustering routines for r and python,” Journal of Statistical Software, vol. 53, 2013

    2013

  2. [10]

    Optimal implementations of upgma and other common clustering algorithms,

    I. Gronau and S. Moran, “Optimal implementations of upgma and other common clustering algorithms,” Information Processing Letters, vol. 104, no. 6, 2007

    2007

  3. [11]

    Multiple upgma and neighbor-joining trees and the performance of some computer packages,

    T. Stefan Van Dongen and B. Winnepenninckx, “Multiple upgma and neighbor-joining trees and the performance of some computer packages,”Mol. Biol. Evol, vol. 13, no. 2, 1996

    1996

  4. [12]

    Evaluation of hierarchical clustering algorithms for document datasets,

    Y. Zhao and G. Karypis, “Evaluation of hierarchical clustering algorithms for document datasets,” in Proceedings of the eleventh international conference on Information and knowledge management, 2002

    2002

  5. [13]

    MGUPGMA: a fast UPGMA algorithm with multiple graphics processing units using NCCL,

    G.-J. Hua, C.-L. Hung, C.-Y. Lin, F.-C. Wu, Y.-W. Chan, and C. Y. Tang, “MGUPGMA: a fast UPGMA algorithm with multiple graphics processing units using NCCL,” Evolutionary Bioinformatics, vol. 13, 2017

    2017

  6. [14]

    A hierarchical algorithm for extreme clustering,

    A. Kobren, N. Monath, A. Krishnamurthy, and A. McCallum, “A hierarchical algorithm for extreme clustering,” in ACM SIGKDD, 2017

    2017

  7. [15]

    Bayesian hierarchical community discovery,

    C. Blundell and Y. W. Teh, “Bayesian hierarchical community discovery,” inAdvances in Neural Infor- mation Processing Systems (NeurIPS), vol. 26, 2013

    2013

  8. [16]

    Author disambiguation using error-driven machine learning with a ranking loss function,

    A. Culotta, P. Kanani, R. Hall, M. Wick, and A. Mc- Callum, “Author disambiguation using error-driven machine learning with a ranking loss function,” in Sixth International Workshop on Information Inte- gration on the Web (IIWeb-07), Vancouver, Canada, 2007

    2007

  9. [17]

    Hierarchical agglomerative graph clustering in poly-logarithmic depth,

    L. Dhulipala, D. Eisenstat, J. Łącki, V. Mirrokni, and J. Shi, “Hierarchical agglomerative graph clustering in poly-logarithmic depth,” inNeurIPS, 2022

    2022

  10. [18]

    Hierarchical agglomerative graph clustering in nearly-linear time,

    ——, “Hierarchical agglomerative graph clustering in nearly-linear time,” inInternational Conference on Machine Learning (ICML), 2021

    2021

  11. [19]

    Scalable hierarchical agglomerative clustering,

    N. Monath, K. A. Dubey, G. Guruganesh, M. Zaheer, A. Ahmed, A. McCallum, G. Mergen, M. Najork, M. Terzihan, B. Tjanakaet al., “Scalable hierarchical agglomerative clustering,” inProceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, 2021

    2021

  12. [20]

    Affinity clustering: Hierarchical clustering at scale,

    M. Bateni, S. Behnezhad, M. Derakhshan, M. Ha- jiaghayi, R. Kiveris, S. Lattanzi, and V. Mirrokni, “Affinity clustering: Hierarchical clustering at scale,” in Advances in Neural Information Processing Systems (NeurIPS), vol. 30, 2017. [Online]. Avail- able: https://proceedings...

    2017

  13. [21]

    A framework for parallelizing hierarchical clustering methods,

    B. Moseley, K. Lu, S. Lattanzi, and T. Lavastida, “A framework for parallelizing hierarchical clustering methods,” in ECML PKDD, 2019

    2019

  14. [22]

    Parallel batch-dynamic minimum spanning forest and the efficiency of dynamic agglomerative graph clustering,

    T. Tseng, L. Dhulipala, and J. Shun, “Parallel batch-dynamic minimum spanning forest and the efficiency of dynamic agglomerative graph clustering,” in SPAA, 2022

    2022

  15. [23]

    Online hi- erarchical clustering approximations,

    A. K. Menon, A. Rajagopalan, B. Sumengen, G. Citovsky, Q. Cao, and S. Kumar, “Online hi- erarchical clustering approximations,”arXiv preprint arXiv:1909.09667, 2019

    1909 arXiv

  16. [24]

    Birch: an efficient data clustering method for very large databases,

    T. Zhang, R. Ramakrishnan, and M. Livny, “Birch: an efficient data clustering method for very large databases,” SIGMOD, 1996

    1996

  17. [25]

    Pbirch: a scalable parallel clustering algorithm for incremental data,

    A. Garg, A. Mangla, N. Gupta, and V. Bhatnagar, “Pbirch: a scalable parallel clustering algorithm for incremental data,” inIDEAS, 2006

    2006

  18. [26]

    Scalable hierarchical clustering with tree grafting,

    N. Monath, A. Kobren, A. Krishnamurthy, M. R. Glass, and A. McCallum, “Scalable hierarchical clustering with tree grafting,” in ACM SIGKDD, 2019

    2019

  19. [27]

    Online level-wise hierarchical clustering,

    N. Monath, M. Zaheer, and A. McCallum, “Online level-wise hierarchical clustering,” inACM SIGKDD, 2023

    2023

  20. [28]

    Hierarchical clustering better than average-linkage,

    M. Charikar, V. Chatziafratis, and R. Niazadeh, “Hierarchical clustering better than average-linkage,” in SODA. SIAM, 2019

    2019

  21. [29]

    Hierarchical clustering: Objective functions and algorithms,

    V. Cohen-Addad, V. Kanade, F. Mallmann-Trenn, and C. Mathieu, “Hierarchical clustering: Objective functions and algorithms,” Journal of the ACM (JACM), vol. 66, no. 4, 2019

    2019

  22. [30]

    A cost function for similarity-based hierarchical clustering,

    S. Dasgupta, “A cost function for similarity-based hierarchical clustering,” inProceedings of the forty- eighth annual ACM symposium on Theory of Com- 9 puting, 2016

    2016

  23. [31]

    Approximation bounds for hierarchical clustering: Average linkage, bisecting k-means, and local search,

    B. Moseley and J. R. Wang, “Approximation bounds for hierarchical clustering: Average linkage, bisecting k-means, and local search,” Journal of Machine Learning Research, vol. 24, no. 1, 2023

    2023

  24. [32]

    Hierarchical clustering of data streams: Scalable algorithms and approximation guarantees,

    A. Rajagopalan, F. Vitale, D. Vainstein, G. Citovsky, C. M. Procopiuc, and C. Gentile, “Hierarchical clustering of data streams: Scalable algorithms and approximation guarantees,” inICML, 2021

    2021

  25. [33]

    Hierarchical clustering via sketches and hierarchical correlation clustering,

    D. Vainstein, V. Chatziafratis, G. Citovsky, A. Ra- jagopalan, M. Mahdian, and Y. Azar, “Hierarchical clustering via sketches and hierarchical correlation clustering,” in International Conference on Artificial Intelligence and Statistics. PMLR, 2021

    2021

  26. [34]

    Terrapattern: A nearest neighbor search service,

    M. Zaheer, G. Guruganesh, G. Levin, and A. Smola, “Terrapattern: A nearest neighbor search service,” ArXiv e-prints, 2019

    2019

  27. [35]

    Scaling hierarchical agglomerative clustering to billion-sized datasets,

    B. Sumengen, A. Rajagopalan, G. Citovsky, D. Sim- cha, O. Bachem, P. Mitra, S. Blasiak, M. Liang, and S. Kumar, “Scaling hierarchical agglomerative clustering to billion-sized datasets,”arXiv preprint arXiv:2105.11653, 2021

    2021 arXiv

  28. [36]

    Affinity clustering: Hierarchical clustering at scale,

    M. Bateni, S. Behnezhad, M. Derakhshan, M. Ha- jiaghayi, R. Kiveris, S. Lattanzi, and V. Mirrokni, “Affinity clustering: Hierarchical clustering at scale,” NeurIPS, vol. 30, 2017

    2017

  29. [37]

    Para- metric umap: learning embeddings with deep neu- ral networks for representation and semi-supervised learning,

    T. Sainburg, L. McInnes, and T. Q. Gentner, “Para- metric umap: learning embeddings with deep neu- ral networks for representation and semi-supervised learning,” ArXiv e-prints, 2020

    2020

  30. [38]

    The amsterdam library of object images,

    J. M. Geusebroek, G. J. Burghouts, and A. W. M. Smeulders, “The amsterdam library of object images,” International Journal of Computer Vision, vol. 61, no. 1, 2005

    2005

  31. [39]

    Imagenet: A large-scale hierarchical image database,

    J. Deng, W. Dong, R. Socher, L.-J. Li, K. Li, and L. Fei-Fei, “Imagenet: A large-scale hierarchical image database,” inCVPR, 2009

    2009

  32. [40]

    Rethinking the inception architecture for computer vision,

    C. Szegedy, V. Vanhoucke, S. Ioffe, J. Shlens, and Z. Wojna, “Rethinking the inception architecture for computer vision,” inCVPR, 2016

    2016

  33. [41]

    Probabilistic case-based reasoning for open-world knowledge graph completion,

    R. Das, A. Godbole, N. Monath, M. Zaheer, and A. McCallum, “Probabilistic case-based reasoning for open-world knowledge graph completion,” in Findings of EMNLP, 2020

    2020

  34. [42]

    ——, “Grinch,” 2020, https://github.com/ ameyagodbole/Prob-CBR/blob/main/prob_ cbr/clustering/grinch_with_deletes.py

    2020

  35. [43]

    GraphGrove,

    N. Monath, “GraphGrove,” 2023, https://github. com/nmonath/graphgrove

    2023

  36. [44]

    DiskANN: Fast accurate billion-point nearest neighbor search on a single node,

    S. Jayaram Subramanya, F. Devvrit, H. V. Simhadri, R. Krishnawamy, and R. Kadekodi, “DiskANN: Fast accurate billion-point nearest neighbor search on a single node,” inAdvances in Neural Information Processing Systems, 2019

    2019

  37. [45]

    Scaling graph- based anns algorithms to billion-size datasets: A comparative analysis,

    M. Dobson, Z. Shen, G. E. Blelloch, L. Dhulipala, Y. Gu, H. V. Simhadri, and Y. Sun, “Scaling graph- based anns algorithms to billion-size datasets: A comparative analysis,” 2023

    2023

  38. [46]

    Poly- logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity,

    J. Holm, K. De Lichtenberg, and M. Thorup, “Poly- logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity,”Journal of the ACM (JACM), vol. 48, no. 4, 2001

    2001

  39. [47]

    Dy- namic graph connectivity in polylogarithmic worst case time,

    B. M. Kapron, V. King, and B. Mountjoy, “Dy- namic graph connectivity in polylogarithmic worst case time,” inProceedings of the twenty-fourth an- nual ACM-SIAM symposium on Discrete algorithms. SIAM, 2013

    2013

  40. [48]

    Dynamic minimum spanning forest with subpoly- nomial worst-case update time,

    D. Nanongkai, T. Saranurak, and C. Wulff-Nilsen, “Dynamic minimum spanning forest with subpoly- nomial worst-case update time,” in2017 IEEE 58th Annual Symposium on Foundations of Computer Sci- ence (FOCS). IEEE, 2017

    2017

  41. [49]

    Approximate hierarchical clustering via sparsest cut and spreading metrics,

    M. Charikar and V. Chatziafratis, “Approximate hierarchical clustering via sparsest cut and spreading metrics,” inProceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms . SIAM, 2017

    2017

  42. [50]

    Hierarchical clustering: A 0.585 revenue approximation,

    N. Alon, Y. Azar, and D. Vainstein, “Hierarchical clustering: A 0.585 revenue approximation,” in Conference on Learning Theory. PMLR, 2020

    2020

  43. [51]

    Objective-based hierarchical clustering of deep em- bedding vectors,

    S. Naumov, G. Yaroslavtsev, and D. Avdiukhin, “Objective-based hierarchical clustering of deep em- bedding vectors,” inProceedings of the AAAI Confer- ence on Artificial Intelligence, vol. 35, no. 10, 2021

    2021

  44. [52]

    Efficient and stable fully dynamic facility location,

    S. Bhattacharya, S. Lattanzi, and N. Parotsidis, “Efficient and stable fully dynamic facility location,” Advances in Neural Information Processing Systems, vol. 35, 2022

    2022

  45. [53]

    Fully dynamic consistent facility location,

    V. Cohen-Addad, N. O. D. Hjuler, N. Parotsidis, D. Saulpic, and C. Schwiegelshohn, “Fully dynamic consistent facility location,” Advances in Neural Information Processing Systems, vol. 32, 2019

    2019

  46. [54]

    Fully-dynamic coresets,

    M. Henzinger and S. Kale, “Fully-dynamic coresets,” arXiv preprint arXiv:2004.14891, 2020

    2004 arXiv

  47. [55]

    Clustering high dimensional dynamic data streams,

    V. Braverman, G. Frahling, H. Lang, C. Sohler, and L. F. Yang, “Clustering high dimensional dynamic data streams,” inInternational Conference on Ma- chine Learning. PMLR, 2017

    2017

  48. [56]

    Fully dynamic k-center clustering in low dimensional metrics,

    G. Goranci, M. Henzinger, D. Leniowski, C. Schulz, and A. Svozil, “Fully dynamic k-center clustering in low dimensional metrics,” in2021 Proceedings of the Workshop on Algorithm Engineering and Experiments (ALENEX). SIAM, 2021

    2021

  49. [57]

    Op- timal fully dynamic k-center clustering for adaptive and oblivious adversaries,

    M. Bateni, H. Esfandiari, H. Fichtenberger, M. Hen- zinger, R. Jayaram, V. Mirrokni, and A. Wiese, “Op- timal fully dynamic k-center clustering for adaptive and oblivious adversaries,” inProceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algo- rithms (SODA). SIAM, 2023

    2023

  50. [58]

    Fully dynamic consistent k-center clustering,

    J. Łącki, B. Haeupler, C. Grunau, R. Jayaram, and V. Rozhoň, “Fully dynamic consistent k-center clustering,” inProceedings of the 2024 Annual ACM- SIAM Symposium on Discrete Algorithms (SODA). SIAM, 2024

    2024

  51. [59]

    Bico: Birch meets coresets for k-means clustering,

    H. Fichtenberger, M. Gillé, M. Schmidt, C. Schwiegelshohn, and C. Sohler, “Bico: Birch meets coresets for k-means clustering,” inAlgorithms–ESA 2013: 21st Annual European Symposium, Sophia Antipolis, France, September 2-4, 2013. Proceedings

    2013

  52. [60]

    Parallel batch-dynamic algorithms for k-core decom- position and related graph problems,

    Q. C. Liu, J. Shi, S. Yu, L. Dhulipala, and J. Shun, “Parallel batch-dynamic algorithms for k-core decom- position and related graph problems,” inProceedings of the 34th ACM Symposium on Parallelism in Algo- rithms and Architectures, 2022

    2022

  53. [61]

    Online and consistent correlation clustering,

    V. Cohen-Addad, S. Lattanzi, A. Maggiori, and N. Parotsidis, “Online and consistent correlation clustering,” in International Conference on Machine Learning. PMLR, 2022

    2022

  54. [62]

    Single-pass streaming algorithms for correlation clustering,

    S. Behnezhad, M. Charikar, W. Ma, and L.-Y. Tan, “Single-pass streaming algorithms for correlation clustering,” inProceedings of the 2023 Annual ACM- SIAM Symposium on Discrete Algorithms (SODA). SIAM, 2023. 11 A Expanded Related Work Several studies have considered the proble...

    2023

Pith tools

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