Pith. sign in

REVIEW 3 major objections 4 minor 39 references

Parallel Hierarchical Agglomerative Clustering in Low Dimensions

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

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

Pith's one-line read This paper shows that (1+ε)-approximate centroid and Ward's hierarchical agglomerative clustering admit near-linear-work, poly-log-depth parallel algorithms in low dimensions, and that in arbitrary dimensions the problem is CC-hard.

desk verdict Centroid HAC result is a genuine advance, but the Ward's theorem is not proven because Lemma 24 applies the approximate triangle inequality without the required size condition. read the letter →

arxiv 2507.20047 v1 pith:VG6R77A6 submitted 2025-07-26 cs.DS cs.CCcs.DC

MohammadHossein Bateni , Laxman Dhulipala , Willem Fletcher , Kishen N Gowda , D Ellis Hershkowitz , Rajesh Jayaram , Jakub {L}ącki This is my paper · ORCID
classification cs.DScs.CCcs.DC MSC 68W1068Q1762H30
keywords hierarchicalagglomerativeclusteringcentroidlinkageWard'sparallelalgorithmslow-dimensionalgeometrydendrogramheightcomplexityclassNCCC-hardness
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

The paper's central claim is that two widely used but non-monotone linkage functions—centroid distance and Ward's distance—can be parallelized effectively in low dimension: for constant dimension $k$, a $(1+\epsilon)$-approximate centroid hierarchical agglomerative clustering can be computed in near-linear total work and poly-logarithmic depth, and the same holds for Ward's linkage in dimensions up to $O(\log\log n / \log\log\log n)$. The structural reason is a new theorem: for any linkage function satisfying five formal 'well-behaved' properties, every constant-factor-approximate HAC dendrogram on $n$ points in $\mathbb{R}^k$ has height at most polylogarithmic in $n$, so the merge history is shallow enough to parallelize. The paper also shows the low-dimension assumption is essential: in $\mathbb{R}^n$, even deciding the merge order of three specified points for $(1+1/n^7)$-approximate centroid HAC is hard for the class CC (comparator circuits), which is widely taken to rule out poly-log-depth algorithms. If correct, these results give the first highly parallel algorithms for non-monotone linkage functions and a theoretical explanation for the practical observation that centroid and Ward's often build balanced hierarchies on low-dimensional data.

What carries the argument

The load-bearing object is the 'well-behaved linkage function' (Definitions 1–6 in the paper), a set of five axioms that let Euclidean packing and triangle-inequality arguments survive for non-metric, non-monotone cluster distances. The height proof fixes an arbitrary input point $x_0$ and tracks its cluster through phases; within a phase it assigns each cluster a value $\exp_2(-d(\widetilde{X}_j, A)/(4\widetilde{\delta}_j))$ that decays exponentially in linkage distance from the phase's starting cluster, and a potential sums these values over clusters smaller than half the tracked cluster's size. Merges of the tracked cluster drain the potential by a constant, while the number of phases is bounded by the aspect ratio, cluster-size doubling, and a drift lemma, yielding the $\widetilde{O}((k c)^{O(k)})$ height. On the algorithmic side, the key secondary object is the bounce-back path of a cluster—the merges it must perform until its linkage values return above the current phase threshold—and its length $\ell$; for Ward's, the standard update formula for Ward's distances implies a weak-reducibility property that makes $\ell = 1$.

What would settle it

Implement the proposed parallel algorithm for Ward's HAC with $k = \Theta(\log\log n / \log\log\log n)$ on a polynomial-aspect-ratio dataset and measure the depth of the merge schedule; the theorem predicts $\widetilde{O}(1)$ depth with high probability, so observing depth that grows as $n^{\delta}$ would refute Theorem 6. For a purely mathematical check, test the weak-reducibility inequality $d(A \cup C, B) \ge d(B, C)$ on triples of Ward's distances: since $\ell = 1$ rests on it, any concrete triple of point sets where it fails after an allowed $(1+\epsilon)$-approximate merge would break the algorithm's bounce-back analysis.

Watch

Extended reading notes

Core claim

In its own formal language, the paper establishes that centroid linkage $d_{\mathrm{cen}}$ and Ward's linkage $d_{\mathrm{Ward}}$ are 'well-behaved': each is $O(1)$-packable, satisfies a restricted approximate triangle inequality, is weight-stable under merges with small clusters, is average-reducible, and has poly-bounded diameter. It then proves the height theorem: any $c$-approximate HAC run with a well-behaved linkage on a polynomial-aspect-ratio point set in $\mathbb{R}^k$ produces a dendrogram of height $\widetilde{O}((k c)^{O(k)})$. From that bound, the paper builds a parallel algorithm whose depth is $\widetilde{O}(h \ell^{O(k)})$ and whose work is $\widetilde{O}(W_{\mathrm{NN}} n h \ell^{O(k)})$, where $h$ is the dendrogram height and $\ell$ is the 'bounce-back length' measuring how many merges a cluster needs before its linkage values recover from a non-monotone drop. Plugging in the height bound and parallel cover-tree nearest-neighbor searches yields near-linear-work, $\widetilde{O}(1)$-depth algorithms for centroid with $k = O(1)$ and for Ward's with $k$ up to $O(\log\log n / \log\log\log n)$; the Ward's gain comes from a weak-reducibility property that forces $\ell = 1$. The matching hardness result reduces the telephone-communication problem to centroid HAC in $\mathbb{R}^n$, proving that $(1+1/n^7)$-approximate promise-decision centroid HAC is CC-hard.

Load-bearing premise

The near-linear-work, constant-depth guarantees for centroid ($k = O(1)$) and Ward's ($k = O(\log\log n / \log\log\log n)$) depend on the existence of a batch-dynamic nearest-neighbor data structure that answers $p$-nearest-neighbor queries in $\widetilde{O}(p 2^{O(k)})$ work and $\widetilde{O}(1)$ depth at those dimensions on input sets with polynomial aspect ratio; if no such structure achieves those costs in that regime, the stated work and depth bounds do not follow.

Editorial extensions

If this is right

  • In constant dimension, $(1+\epsilon)$-approximate centroid HAC drops from quadratic sequential work to near-linear parallel work with polylog depth; the same holds for Ward's in dimensions up to $O(\log\log n / \log\log\log n)$.
  • Any constant-approximate HAC run with a well-behaved linkage on low-dimensional polynomial-aspect-ratio data produces a balanced dendrogram of polylog height, giving a rigorous basis for the empirical balancing behavior of centroid and Ward's.
  • The centroid result yields a $(1+\epsilon)^2$-approximate algorithm for squared-centroid HAC, a variant used in practice.
  • The CC-hardness result implies that, barring a collapse of CC into NC, no NC algorithm for Euclidean centroid HAC can exist when the dimension is linear in $n$, so the low-dimensional restriction is intrinsic.
  • For Ward's, the bounce-back length is always 1, meaning each parallel round needs only one corrective merge per cluster, which is what allows the larger dimension range.

Reading between the lines

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

  • If the five well-behaved axioms are satisfied by other centroid-based linkage functions, the same height theorem would give NC algorithms for those variants, a direct generalization the paper leaves implicit.
  • With a stronger low-dimensional nearest-neighbor scheme than the one the paper invokes, the Ward's dimension ceiling could move beyond $O(\log\log n / \log\log\log n)$ and the remaining polylog factors could shrink.
  • The phase potential argument suggests a sequential near-linear-time algorithm for constant-approximate centroid HAC in constant dimension, improving on current subquadratic running times.
  • A testable empirical prediction follows from the height theorem: on low-dimensional datasets with polynomial aspect ratio, measured dendrogram heights for centroid and Ward's should remain polylogarithmic in $n$.
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

3 major / 4 minor

Summary. The paper studies (1+epsilon)-approximate hierarchical agglomerative clustering in Euclidean space for non-monotone linkage functions, specifically centroid and Ward's linkage. It introduces a class of 'well-behaved' linkage functions satisfying packing, approximate triangle, weight-stability, average-reducibility, and diameter properties, and proves a structural result (Theorem 3) bounding the dendrogram height of any c-approximate HAC by ~O((kc)^{O(k)}). It then presents a parallel algorithm whose work and depth depend on this height and on an auxiliary 'bounce-back length' parameter, yielding near-linear-work, polylog-depth algorithms for centroid HAC when k=O(1) (Theorem 5) and for Ward's HAC when k=O(log log n / log log log n) (Theorem 6). Complementing this, the paper proves CC-hardness for centroid HAC in R^n (Theorem 7).

Significance. If the algorithm and height bound are correct, this is a substantial contribution: it gives the first NC-style algorithms for approximate HAC with non-monotone linkage functions in low dimensions, and the height bound for well-behaved linkage functions is a clean structural statement with no fitted parameters. The potential-function proof of Theorem 3 is carefully argued and appears sound. The hardness result, if completed, would be the first CC-hardness for HAC in Euclidean space rather than on abstract graphs. However, the correctness proof of the parallel algorithm has a load-bearing gap concerning clusters that are not in the current candidate set, and the Ward's bounce-back claim and the unweighting of the hardness reduction are not fully established. These issues affect Theorems 4-7 as stated, so the paper needs substantial revision before the algorithmic claims can be accepted.

major comments (3)
  1. [Sections 5.1-5.2, Definitions 12-13, Lemma 25] The correctness proof of Algorithm 1 does not account for clusters outside C_{t,r} that become attracted to a selected cluster during the round. Locally-optimal and bounce-back paths are defined over C_{t,r} - A only, yet Algorithm 1's inner loop (lines 12-13) queries nearest neighbors in the full active set C. The paragraph before Definition 12 asserts that external clusters need not be processed, but this is not proved and is in fact false. Concretely, take epsilon=0.1, lower threshold 1, upper threshold 1.1, and in R^2 let X=(0,0), B=(1.05,0), Z=(1.1 cos 60°, 1.1 sin 60°). Then d(X,B)=1.05 is in [1,1.1), d(X,Z)=1.1 is not below the upper threshold, and d(B,Z) is approximately 1.076, so all initial distances are at least 1 and Z is not in C_{t,0}. After X merges with B, the new centroid is (0.525,0), whose distance to Z is about 0.953, below the lower threshold. Algorithm 1 therefore merges the growing cluster with Z at lines 12-13, even though Z is not on the precomputed bounce-back path of X. This contradicts Lemma 25's claim that selected clusters merge exactly along their bounce-back paths. Since Lemmas 24-26 and Theorems 4-6 rely on this non-interference argument, the algorithmic claims are not established as written.
  2. [Section 5.4.2, Definition 15, Lemma 32] The assertion that Ward's linkage has bounce-back length ell=1 is not justified by the cited weak-reducibility property as written. Definition 15 is stated for the case where the non-merged pair is the largest side of the triple, whereas Algorithm 1 merges a cluster with its nearest neighbor. The text simply says that after a cluster A merges with its nearest neighbor, all other linkage values remain at least (1+epsilon)^t. A proof needs the additional observation that for every third cluster C, the merged pair (A,N) is never the unique largest side, because d(A,N) <= d(A,C); then Lemma 32 can be applied to whichever of d(A,C) or d(N,C) is largest. This case analysis is absent. The value ell=1 is load-bearing for Theorem 6, since it determines the dimension range k = O(log log n / log log log n) and the near-linear work bound, so the gap must be repaired.
  3. [Section 6.1, first paragraph] The hardness reduction starts with the sentence 'We will use weighted points as it is not difficult to place many points close together to achieve the same result', but Theorem 7 is stated for ordinary unweighted centroid HAC in R^n. No proof of the weighted-to-unweighted conversion is given. A standard simulation by replacing a weight-W point with W coincident singleton points requires checking that the internal merges of duplicates do not interact with the reduction's ordering arguments, and that the resulting point count and approximation parameter behave correctly. Since the CC-hardness result is a stated contribution, this handwave is not sufficient; the reduction must either be formalized for unweighted points or the theorem restated for the weighted variant.
minor comments (4)
  1. [Section 5.4.2, Lemma 45] The claim that a nearest neighbor by centroid distances within a size bucket is a 2-approximate nearest neighbor for Ward's linkage is not accurate: for sizes within a factor of 2, the coefficient |A||B|/(|A|+|B|) in Lemma 45 varies by a factor of 3, not 2. This does not affect the asymptotic results, but the constant should be corrected.
  2. [Equation (15), Lemma 20] There is a typographical error in the displayed inequality: '2˜delta_j))' has an unbalanced parenthesis. The intended bound is c_Delta (epsilon * z * (c_Delta)^{log z} * delta_tilde_j + 2 delta_tilde_j).
  3. [Theorem 7 proof] The proof text says 'Lemma 36, Lemma 37, Lemma 38, Lemma 38, Lemma 40, Lemma 41, and Lemma 42'; Lemma 38 is cited twice and Lemma 39, which proves the F-merges-with-C case, is omitted from the list.
  4. [Theorems 5 and 6] The phrase '~O(1) depth' could mislead readers, since ~O hides polylogarithmic factors and the actual depth bounds are polylogarithmic in n. A brief clarification in the theorem statements would help.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the height bound, parallel algorithms, and CC-hardness reduction are derived from stated definitions, in-paper lemmas, and external prior results; all self-citations are contextual and not load-bearing.

full rationale

This is a pure-theory paper, so the fitted-input-called-prediction pattern does not apply: no parameter is fit to data, and every constant (epsilon, c, alpha, c_Delta, W, Delta, tau, r_i, l_i) is either explicit or algebraically verified. The derivation chain is acyclic. Definition 6 (well-behaved) is a conjunction of five axioms; Theorems 1-2 verify centroid and Ward's against those axioms using Euclidean packing (Theorem 8) and two external results with no author overlap: Lance-Williams [LW67] and the Ward's approximation [GRS19]. Theorem 3 is derived, not assumed: the phase decomposition (Definition 9) and the exponentially damped potential (Definitions 10-11) are introduced in this paper, and the bound follows from Lemmas 14-22, with Lemma 16 using the packability axiom and Lemma 20 explicitly checking the size hypothesis before applying the approximate triangle inequality (Definition 2); the dependency order Lemma 17 -> Lemma 20 -> Lemma 21 is acyclic. Theorem 4 is a clean parameterization: h and ell are promised bounds, the algorithm does not fit them, and Lemma 29 uses h only through the definition of dendrogram height (each time a cluster is picked, some original point advances by at least one merge). Theorems 5-6 then plug Theorem 3's polylogarithmic height into Theorem 4 together with the external parallel cover-tree data structure of [GNSW22] (again no author overlap), so the near-linear-work polylog-depth claims follow arithmetically from stated assumptions rather than from any self-referential definition. Hardness (Theorem 7) reduces from the external CC-hard TCP problem [RW91] with parameters fixed and verified in Lemmas 36-42. Self-citations ([DEŁ+22], [BDG+24], [BDF+24], [DDGG24], [DŁLM23], [YDŁP25]) appear only as background or efficiency comparisons and are not load-bearing; no uniqueness theorem is imported from the authors' prior work. The flagged risks (Lemma 24's application of the approximate triangle inequality without verifying |Y'_j| >= min(|X'_i|, |Y|) in Cases 2-4, and sensitivity to the exact scope of [GNSW22]'s guarantees at k up to log log n / log log log n) are correctness or robustness concerns about the proof as written; they are not instances of a claimed prediction reducing to its own input by construction, so they do not raise the circularity score. Finding: no significant circularity, score 0.

Assumptions & free parameters 6 free parameters · 7 assumptions · 0 invented entities

The definitions of well-behaved, bounce-back paths, and bounce-back shells are new mathematical frameworks, not invented physical entities. No free parameters are fitted to data; the listed parameters are hand-chosen constants in the hardness reduction. The central algorithmic results rely on standard analysis and two external theorems: parallel cover trees and TCP hardness.

free parameters (6)
  • epsilon_approx = 1/n^7
    Approximation factor in the CC-hardness reduction; chosen small enough to satisfy the separation inequalities in Lemmas 36-42.
  • tau = 1/n
    Offset increment in event positions in the reduction; chosen to enforce the merge ordering of events.
  • W = n^3
    Weight of the center and outer points in the reduction; chosen so centroid drift stays within the bounds used by the reduction.
  • Delta = n^5
    Base distance of events from the center; chosen large enough for the separation inequalities in the reduction to hold.
  • r_i = (1+2/n^7) sqrt((k-1+f(S_i)) delta_u^2 + (Delta + tau e(S_i))^2)
    Distance from S_i to R_i; set so S_i merges with R_i iff call i is dropped in the TCP instance.
  • l_i = (1+2/n^7) sqrt((k+f(F_i)) delta_u^2 + (Delta + tau e(F_i))^2)
    Distance from F_i to L_i; set so F_i merges with L_i iff S_i did not merge with C.
assumptions (7)
  • standard math Euclidean packing bound (Theorem 8)
    Used to prove packability of centroid and Ward's; proved in Appendix A.1.
  • standard math Lance-Williams update formula for Ward's (Lemma 7)
    Used throughout Sections 3 and 5.4.2; proved in Appendix A.2.
  • standard math Ward's approximation by centroid distance (Lemma 6)
    Cited from [GRS19] and proved in Appendix A.2; used for packability and bucketing.
  • domain assumption Parallel batch-dynamic cover trees (Theorem 9, [GNSW22])
    External data structure result used for nearest neighbor queries; assumed to hold with the stated work and depth for the dimensions used.
  • domain assumption CC-hardness of TCP (Lemma 33, [RW91])
    Reduction source for the hardness result; external complexity result used as the base of the reduction.
  • domain assumption poly(n) aspect ratio
    Assumed for all main theorems (Theorems 3-6); restricts the input point sets and is needed for the height and phase bounds.
  • domain assumption Definition of well-behaved linkage functions (Definition 6)
    Theorems 3 and 4 are conditional on this definition; the paper proves it holds for centroid and Ward's in Theorems 1 and 2.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Parallel Hierarchical Agglomerative Clustering in Low Dimensions." pith.science (2026). https://pith.science/paper/VG6R77A6

@misc{pith2026250720047,
  author       = {Pith},
  title        = {Pith review of: Parallel Hierarchical Agglomerative Clustering in Low Dimensions},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/VG6R77A6}},
  note         = {Machine review of arXiv:2507.20047}
}
abstract

Hierarchical Agglomerative Clustering (HAC) is an extensively studied and widely used method for hierarchical clustering in $\mathbb{R}^k$ based on repeatedly merging the closest pair of clusters according to an input linkage function $d$. Highly parallel (i.e., NC) algorithms are known for $(1+\epsilon)$-approximate HAC (where near-minimum rather than minimum pairs are merged) for certain linkage functions that monotonically increase as merges are performed. However, no such algorithms are known for many important but non-monotone linkage functions such as centroid and Ward's linkage. In this work, we show that a general class of non-monotone linkage functions -- which include centroid and Ward's distance -- admit efficient NC algorithms for $(1+\epsilon)$-approximate HAC in low dimensions. Our algorithms are based on a structural result which may be of independent interest: the height of the hierarchy resulting from any constant-approximate HAC on $n$ points for this class of linkage functions is at most $\operatorname{poly}(\log n)$ as long as $k = O(\log \log n / \log \log \log n)$. Complementing our upper bounds, we show that NC algorithms for HAC with these linkage functions in \emph{arbitrary} dimensions are unlikely to exist by showing that HAC is CC-hard when $d$ is centroid distance and $k = n$.

Figures

Figures reproduced from arXiv: 2507.20047 by the authors.

Figure 1
Figure 1. An example of HAC run on P ⊆ R k . Recently, the widespread usage of HAC on large datasets has motivated considerable interest in developing the theory of efficient parallel HAC algorithms. For the simpler linkage functions of 1One can also study linkage functions that give the “similarity” between clusters; see, e.g., [DEŁ+22]. 1 [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Two examples where centroid HAC fails to be monotone. 2a / 2b gives 3 equidistant points in R 2 where the minimum merge reduces from 1 and √ 3/2 < 1. 2c / 2d gives 3 points in R 2 where a 2-approximate merge reduces the minimum distance from 1 to an arbitrarily small ϵ. 2 Our Contributions In this work, we show that (1 + ϵ)-approximate HAC is in NC for a general class of linkage func￾tions which includes both centro… view at source ↗
Figure 3
Figure 3. An example of centroid HAC with an Ω(n)-length chain of dependencies. Each point/cluster points at its nearest other cluster. Notice that the (n − 1)th point does not know if it merges left or right until Ω(n) merges have been performed. and (i+ 1)th point is 1 +i· ϵ for some small ϵ > 0 as in [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗
Figures from the paper (3 more)
Figure 4
Figure 4. Figure 4: An illustration of our height bound argument for centroid. Figure 4a/4b/4c/4d/4e show x merging until there is nothing within its 2δ ball. Figure 4f/4g/4h shows how new centroids can enter its ball but only by merging off in pairs where 8 centroids at distance 4δ becom…
Figure 5
Figure 5. Figure 5: Illustration of the recursive application of the approximate triangle inequality to bound the distance from cluster A to the i th cluster on its bounce-back path. 5.2 Correctness In this section, we prove that algorithm 1 produces a valid (1+ϵ)-approximate HAC merge se…
Figure 6
Figure 6. Figure 6: An example of the reduction from TCP to HAC for two phone calls. 2. S merges with C: For some unmerged Sj , if for less than f(Sj ) + κ coordinates c of C (i) , |[C (i) ]c| ∈ (δl , δu) and for the rest including c = j, [C (i) ]c = 0, then (1 + ϵ) · d(C (i) , Sj ) < rj …

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

39 extracted references · 36 canonical work pages

  1. [1]

    Subquadratic high-dimensional hierarchical clustering

    Amir Abboud, Vincent Cohen-Addad, and Hussein Houdrouge. Subquadratic high-dimensional hierarchical clustering. In Annual Conference on Neural Information Processing Systems (NeurIPS) , 2019

    work page 2019

  2. [2]

    Efficient centroid-linkage clustering

    MohammadHossein Bateni, Laxman Dhulipala, Willem Fletcher, Kishen N Gowda, D Ellis Hershkowitz, Rajesh Jayaram, and Jakub Lacki. Efficient centroid-linkage clustering. Annual Conference on Neural Information Processing Systems (NeurIPS) , 2024

    work page 2024

  3. [3]

    It's hard to hac with average linkage! In International Colloquium on Automata, Languages and Programming (ICALP) , 2024

    MohammadHossein Bateni, Laxman Dhulipala, Kishen N Gowda, D Ellis Hershkowitz, Rajesh Jayaram, and Jakub a cki. It's hard to hac with average linkage! In International Colloquium on Automata, Languages and Programming (ICALP) , 2024

    work page 2024

  4. [4]

    Introduction to Parallel Algorithms (DRAFT) , 2024

    Guy E Blelloch, Laxman Dhulipala, and Yihan Sun. Introduction to Parallel Algorithms (DRAFT) , 2024

    work page 2024

  5. [5]

    Cover trees for nearest neighbor

    Alina Beygelzimer, Sham Kakade, and John Langford. Cover trees for nearest neighbor. In Proceedings of the 23rd International Conference on Machine Learning , ICML '06, page 97–104, New York, NY, USA, 2006. Association for Computing Machinery

    work page 2006

  6. [6]

    The complexity of the comparator circuit value problem

    Stephen A Cook, Yuval Filmus, and Dai Tri Man Le. The complexity of the comparator circuit value problem. ACM Transactions on Computation Theory (TOCT) , 6(4):1--44, 2014

    work page 2014

  7. [7]

    Twister tries: Approximate hierarchical agglomerative clustering for average distance in linear time

    Michael Cochez and Hao Mou. Twister tries: Approximate hierarchical agglomerative clustering for average distance in linear time. In Proceedings of the 2015 ACM SIGMOD international conference on Management of data , pages 505--517, 2015

    work page 2015

  8. [8]

    Optimal parallel algorithms for dendrogram computation and single-linkage clustering

    Laxman Dhulipala, Xiaojun Dong, Kishen N Gowda, and Yan Gu. Optimal parallel algorithms for dendrogram computation and single-linkage clustering. In Proceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures , pages 233--245, 2024

    work page 2024

Show all 39 references
  1. [9]

    Hierarchical agglomerative graph clustering in nearly-linear time

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

    2021

  2. [10]

    Hierarchical agglomerative graph clustering in poly-logarithmic depth

    Laxman Dhulipala, David Eisenstat, Jakub a cki, Vahab Mirrokni, and Jessica Shi. Hierarchical agglomerative graph clustering in poly-logarithmic depth. Annual Conference on Neural Information Processing Systems (NeurIPS) , 35:22925--22940, 2022

    2022

  3. [11]

    The faiss library

    Matthijs Douze, Alexandr Guzhva, Chengqi Deng, Jeff Johnson, Gergely Szilvasy, Pierre-Emmanuel Mazar \'e , Maria Lomeli, Lucas Hosseini, and Herv \'e J \'e gou. The faiss library. arXiv preprint arXiv:2401.08281 , 2024

    2024 arXiv

  4. [12]

    Terahac: Hierarchical agglomerative clustering of trillion-edge graphs

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

    2023

  5. [13]

    Blelloch, Laxman Dhulipala, Yan Gu, Harsha Vardhan Simhadri, and Yihan Sun

    Magdalen Dobson, Zheqi Shen, Guy E. Blelloch, Laxman Dhulipala, Yan Gu, Harsha Vardhan Simhadri, and Yihan Sun. Scaling graph-based ANNS algorithms to billion-size datasets: A comparative analysis. CoRR , abs/2305.04359, 2023

    2023 arXiv

  6. [14]

    A new near-linear time algorithm for k-nearest neighbor search using a compressed cover tree

    Yury Elkin and Vitaliy Kurlin. A new near-linear time algorithm for k-nearest neighbor search using a compressed cover tree. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, Proceedings of the 40th Internationa...

    2023

  7. [15]

    Clustering for private interest-based advertising

    Alessandro Epasto, Andr \'e s Mu \ n oz Medina, Steven Avery, Yijian Bai, Robert Busa-Fekete, CJ Carey, Ya Gao, David Guthrie, Subham Ghosh, James Ioannidis, et al. Clustering for private interest-based advertising. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge...

    2021

  8. [16]

    Tight analysis of parallel randomized greedy mis

    Manuela Fischer and Andreas Noever. Tight analysis of parallel randomized greedy mis. ACM Trans. Algorithms , 16(1), December 2019

    2019

  9. [17]

    Parallel cover trees and their applications

    Yan Gu, Zachary Napier, Yihan Sun, and Letong Wang. Parallel cover trees and their applications. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) , 2022

    2022

  10. [18]

    J. C. Gower. A comparison of some methods of cluster analysis. Biometrics , 23(4):623--637, 1967

    1967

  11. [19]

    Analysis of ward's method

    Anna Gro wendt, Heiko R \"o glin, and Melanie Schmidt. Analysis of ward's method. In Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) . SIAM, 2019

    2019

  12. [20]

    Clustering.jl

    JuliaStats. Clustering.jl

  13. [21]

    Hierarchical clustering

    Wolfram: Computation Meets Knowledge. Hierarchical clustering

  14. [22]

    A framework for parallelizing hierarchical clustering methods

    Silvio Lattanzi, Thomas Lavastida, Kefu Lu, and Benjamin Moseley. A framework for parallelizing hierarchical clustering methods. In Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2019, W \"u rzburg, Germany, September 16--20, 2019, Procee...

    2019

  15. [23]

    A general theory of classificatory sorting strategies: 1

    Godfrey N Lance and William Thomas Williams. A general theory of classificatory sorting strategies: 1. hierarchical systems. The computer journal , 9(4):373--380, 1967

    1967

  16. [24]

    Agglomerative hierarchical cluster tree - matlab linkage

    MathWorks. Agglomerative hierarchical cluster tree - matlab linkage. https://www.mathworks.com/help/stats/linkage.html, 2024

    2024

  17. [25]

    Algorithms for hierarchical clustering: an overview

    Fionn Murtagh and Pedro Contreras. Algorithms for hierarchical clustering: an overview. Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery , 2(1):86--97, 2012

    2012

  18. [26]

    Algorithms for hierarchical clustering: an overview, ii

    Fionn Murtagh and Pedro Contreras. Algorithms for hierarchical clustering: an overview, ii. Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery , 7(6):e1219, 2017

    2017

  19. [27]

    The complexity of circuit value and network stability

    Ernst W Mayr and Ashok Subramanian. The complexity of circuit value and network stability. Journal of Computer and System Sciences , 44(2):302--323, 1992

    1992

  20. [28]

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

    Daniel M \"u llner. fastcluster: Fast hierarchical, agglomerative clustering routines for r and python. Journal of Statistical Software , 53:1--18, 2013

    2013

  21. [29]

    Benjamin Moseley and Joshua R. Wang. Approximation bounds for hierarchical clustering: Average linkage, bisecting k-means, and local search. In Annual Conference on Neural Information Processing Systems (NeurIPS) , pages 3094--3103, 2017

    2017

  22. [30]

    Scikit-learn: Machine learning in python

    Fabian Pedregosa, Ga \"e l Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, et al. Scikit-learn: Machine learning in python. the Journal of machine Learning research , 12:2825--2830, 2011

    2011

  23. [31]

    hclust function - rdocumentation

    RDocumentation. hclust function - rdocumentation

  24. [32]

    Parallel algorithm and complexity results for telephone link simulation

    Vijaya Ramachandran and Li-Chung Wang. Parallel algorithm and complexity results for telephone link simulation. In Proceedings of the Third IEEE Symposium on Parallel and Distributed Processing . IEEE Computer Society, 1991

    1991

  25. [33]

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

    Suhas Jayaram Subramanya, Devvrit, Rohan Kadekodi, Ravishankar Krishnaswamy, and Harsha Simhadri. Diskann: Fast accurate billion-point nearest neighbor search on a single node. In Annual Conference on Neural Information Processing Systems (NeurIPS) , 2019

    2019

  26. [34]

    A new approach to stable matching problems

    Ashok Subramanian. A new approach to stable matching problems. SIAM Journal on Computing , 23(4):671--700, 1994

    1994

  27. [35]

    How small is a unit ball? Mathematics Magazine , 62(2):101--107, 1989

    David J Smith and Mavina K Vamanamurthy. How small is a unit ball? Mathematics Magazine , 62(2):101--107, 1989

    1989

  28. [36]

    Alglib, a simple symbol-manipulation package

    JM Shearer and Michael A Wolfe. Alglib, a simple symbol-manipulation package. Communications of the ACM , 28(8):820--825, 1985

    1985

  29. [37]

    Scipy 1.0: fundamental algorithms for scientific computing in python

    Pauli Virtanen, Ralf Gommers, Travis E Oliphant, Matt Haberland, Tyler Reddy, David Cournapeau, Evgeni Burovski, Pearu Peterson, Warren Weckesser, Jonathan Bright, et al. Scipy 1.0: fundamental algorithms for scientific computing in python. Nature methods , 17(3):261--272, 2020

    2020

  30. [38]

    Dynhac: Fully dynamic approximate hierarchical agglomerative clustering

    Shangdi Yu, Laxman Dhulipala, Jakub a cki, and Nikos Parotsidis. Dynhac: Fully dynamic approximate hierarchical agglomerative clustering. arXiv preprint arXiv:2501.07745 , 2025

    2025 arXiv

  31. [39]

    The parclusterers benchmark suite (pcbs): A fine-grained analysis of scalable graph clustering

    Shangdi Yu, Jessica Shi, Jamison Meindl, David Eisenstat, Xiaoen Ju, Sasan Tavakkol, Laxman Dhulipala, Jakub a cki, Vahab Mirrokni, and Julian Shun. The parclusterers benchmark suite (pcbs): A fine-grained analysis of scalable graph clustering. arXiv preprint arXiv:2411.10290 , 2024

    2024 arXiv

Pith tools

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