Pith. sign in

REVIEW 4 major objections 4 minor 1 cited by

Fully dynamic hierarchical diameter k-clustering and k-center

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

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

Pith's one-line read This paper shows that a pointwise approximate hierarchical k-center or diameter k-clustering can be maintained under insertions and deletions, with polylogarithmic update time in constant dimension.

desk verdict First fully dynamic hierarchical k-clustering data structure with a genuinely new framework; the main theorems are likely correct, but Corollary 6 overreaches and several proof details need patching before acceptance. read the letter →

arxiv 1908.02645 v1 pith:GPRCFKP4 submitted 2019-08-07 cs.DS

Melanie Schmidt , Christian Sohler This is my paper · ORCID
classification cs.DS MSC 68W2568P05
keywords hierarchicalclusteringk-centerdiameterk-clusteringfullydynamicdatastructurepointwiseapproximationgridhashingEuclideanspacerandomizedgrids
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

Dynamic clustering usually means maintaining a single k-center solution; this paper tackles the harder object of a whole hierarchy of clusterings for every k. It constructs a nested family of point sets, called an α-good family, with only O(log Δ) levels, and shows that every level induces a clustering that is an 8α-approximation to the optimal k-center or diameter k-clustering for all relevant k. For points on the grid $\{1,\ldots,\Delta\}^d$ in constant dimension $d$, it maintains this family under insertions and deletions in expected amortized time $O_d(\log \Delta \log n)$ per insertion and $O_d(\log^2 \Delta \log n)$ per deletion, with cluster-representative queries in $O_d(\log \Delta + \log n)$. In high dimension a randomized variant achieves an $O(d\ell)$-approximation with deletion time $O(d^2 n^{1/\ell} \log^2 n \log \Delta)$. If correct, these are the first fully dynamic data structures for hierarchical versions of these classic problems, and a by-product is a near-linear-time static algorithm.

What carries the argument

Central object: an α-good family — a nested chain $P_0 = P \supseteq P_1 \supseteq \cdots \supseteq P_M = \{p\}$ with $M = O(\log \Delta)$, where points in $P_i$ have mutual distance $> 2^i$ and every point removed between consecutive levels lies within $\alpha 2^i$ of a survivor. It carries the argument because it compresses the entire hierarchy into logarithmically many levels while a lemma shows that any such family yields an $8\alpha$-pointwise approximation. The implementation is powered by grid hashing: each $P_i$ is stored by hashing points into grid cells of side about $2^i/\sqrt{d}$, so the question 'is there a point within distance $2^i$?' costs $O_d(1)$ cell probes; parent and child pointers tie the levels together so a deletion only re-inserts the affected children. In high dimension, randomly shifted grids with $O(\log n)$ repetitions replace exact cell lookup and yield the $O(d\ell)$-approximation.

What would settle it

Run the insertion routine on adversarial point sets in, say, two dimensions and record, for each level $i$, the maximum number of points in $P_{i-1}$ whose parent is a single point $p$. The deletion-time bound requires this maximum to be a constant depending only on $d$; if it grows with $n$ or $\Delta$, deletions will be slower than claimed. This is a finite, automatable check on small grids.

Watch

Extended reading notes

Core claim

The paper's core claim is that a pointwise approximate hierarchical clustering can be represented by a tiny nested family of subsets rather than by n distinct clusterings, and that this family can be maintained locally under updates. The family satisfies: points in $P_i$ are pairwise farther than $2^i$ apart, and every point that disappears between level $i-1$ and level $i$ has a surviving 'parent' within $\alpha 2^i$. From these two conditions alone, the paper proves that the clusters induced by the family form an $8\alpha$-approximation for the optimal diameter k-clustering and k-center for every $k$ between consecutive level sizes; with $\alpha < 2$ this yields the 16-approximation. The dynamic structure keeps the family valid by grid lookups: on insertion a point climbs the levels until it meets a close survivor, and on deletion the orphaned children are re-inserted, producing a controlled cascade. The high-dimensional extension replaces exact close-neighbor checks with randomly shifted grids and subsampling, giving an $O(d\ell)$-approximation and making deletion time $n^{1/\ell}$.

Load-bearing premise

In the low-dimensional deletion routine, the paper asserts without proof that a deleted point has only $O_d(1)$ children in the parent forest; if that packing bound failed, deletions could cascade through many points and the $O_d(\log^2 \Delta \log n)$ deletion time would break.

Editorial extensions

If this is right

  • For points on a grid in constant dimension, insertions, deletions, and cluster-representative queries for any number of clusters $k$ all run in polylogarithmic time, so an interactive user can inspect every level of the hierarchy without rebuilding.
  • The same maintained family serves both k-center and diameter k-clustering: representatives act as centers, and the partition into clusters has the same approximation ratio.
  • Setting $\ell = \lceil 1/\epsilon \rceil$ in the high-dimensional structure makes the amortized deletion time $n^{\epsilon}$ for any constant $\epsilon>0$ while keeping a constant-factor approximation whose constant depends on $d$ and $\epsilon$.
  • Since insertion-only operation builds the family from scratch, the paper yields a static algorithm for pointwise approximate hierarchical clustering in $O(n d \log n \log \Delta)$ time, improving on the $O(n^2 d)$ cost of prior methods.
  • All queries are correct with high probability in the high-dimensional case, so the structure is suitable for data sets with many insertions and deletions where exact recomputation is infeasible.

Reading between the lines

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

  • The grid-hashing mechanism is really a close-neighbor oracle; replacing it with an approximate nearest-neighbor data structure in another metric would plausibly carry the same α-good family argument, giving dynamic hierarchical clusterings beyond Euclidean grids.
  • The low-dimensional deletion bound depends on an asserted but unproved packing fact: each point has $O_d(1)$ children. A direct measurement of the maximum in-degree in the parent forest on random and worst-case grids would test this and is easy to automate.
  • Because the family stores all levels independent of $k$, the same dynamic structure could serve as a building block for streaming or distributed settings where one wants approximate clusterings at multiple resolutions simultaneously.
  • For practical input in floating point, rescaling to the grid $\{1,\ldots,\Delta\}^d$ and choosing $\Delta$ as the spread would make the algorithmic guarantees directly applicable; the paper does not discuss this numerical preprocessing.
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

4 major / 4 minor

Summary. The paper develops two fully dynamic data structures for maintaining a pointwise approximate hierarchical k-center / diameter k-clustering on point sets in {1,...,Δ}^d. The low-dimensional data structure maintains a 16-approximation with expected amortized insertion time O_d(log Δ log n), expected amortized deletion time O_d(log^2 Δ log n), and cluster-representative queries in O_d(log Δ + log n) time. The high-dimensional data structure maintains an O(dℓ)-approximation with insertion time O(d^2ℓ log n log Δ), deletion time O(d^2 n^{1/ℓ} log^2 n log Δ), and queries in O(dℓ log n log Δ) time, with high-probability correctness. The constructions are based on nested α-good families, grid hashing, and randomly shifted grids, following ideas from Hochbaum-Shmoys and McCutchen-Khuller.

Significance. If the gaps identified below are repaired, the main results would be notable: to my knowledge these are the first fully dynamic data structures for pointwise approximate hierarchical k-center and diameter k-clustering, extending the static 8-approximation of Dasgupta-Long and the streaming ideas of McCutchen-Khuller to a dynamic setting. The paper is mostly self-contained, uses standard tools (triangle inequality, packing, Chernoff bounds, hashing), gives explicit approximation ratios, and does not fit any parameter to data. The high-dimensional result, while having a sublinear-in-n deletion time, is a nontrivial first step. The proof gaps are localized and appear repairable, but several are load-bearing for the stated runtime or approximation guarantees.

major comments (4)
  1. [Section 3, Deletions] The sentence 'By the same argumentation as for the insertions, the number of children of a point is O_d(1)' is asserted without proof, and this bound is load-bearing: it is what keeps a deletion from triggering a cascade that is linear in n. The needed packing calculation is that children of p at level i lie in P_{i-1} within distance at most α 2^i of p (with α<2), while any two distinct points of P_{i-1} have distance greater than 2^{i-1}; in fixed dimension d this bounds the number of children by a constant depending only on d. Please add this calculation explicitly, since without it the O_d(log^2 Δ log n) deletion bound in Lemma 9 is not established.
  2. [Lemma 11 and Section 4.1] The recursive-covering proof of Lemma 11 is off by one hop. Starting from p ∈ P_{i-1} = P_{i,0}, a point can be covered successively by points in P_{i,1}, ..., P_{i,ℓ}, and then needs one final hop to an element of I_{i,ℓ}; in the worst case this gives (ℓ+1)·√d·R, not ℓ·√d·R. The final statement would still be O(dℓ) after adjusting the constant, but the lemma as written and the claimed parameter α = 2dℓ in the introduction of Section 4 need to be corrected.
  3. [Corollary 6 and preceding discussion] Corollary 6 is not valid as stated when P_{i-1} = P_i, a case explicitly allowed by the footnote in Section 2. If P_{i-1} = P_i and j < i-1 is the largest index with |P_j| > |P_i|, a set T ⊆ P_j \ P_i may contain points that are not in P_{i-1}, so C_{i-1}(y) is undefined for y ∈ T. The data structure's Cluster(p,k) definition avoids this by using the smallest i with |P_i| ≤ k, since then |P_{i-1}| > k and the additional representatives are drawn from P_{i-1} \ P_i. The proof of the exact-k approximation guarantee must be tied to that choice, and Corollary 6 should be restated with the hypothesis |P_{i-1}| > |P_i| (or with T ⊆ P_{i-1} \ P_i).
  4. [Lemma 4 proof] The proof of Lemma 4 contains a garbled summation: the printed expression writes ‖x - p1(x)‖ + ‖x - p2(x)‖ + ... + ‖x - pi(x)‖, which is not a telescoping sum. The intended argument is the telescoping sum over consecutive representatives, ∑_{j=1}^i ‖p_{j-1}(x) - p_j(x)‖ ≤ ∑_{j=1}^i α 2^j ≤ α 2^{i+1}. The claimed bound is correct once this typo is fixed.
minor comments (4)
  1. [Section 3, first paragraph] The text says 'For every 0 ≤ i ≤ d log Δ we store P_i', but the definition in Section 2 gives M = log(√d·(Δ−1)); the bound should be stated as 0 ≤ i ≤ M, which is O(log Δ + log d).
  2. [Section 3, Insertions] The displayed distance bound for the parent found during insertion contains inconsistent notation (2i + 2/√d versus 2^i + 2^i/√d), and it is not clear whether 2^i/√d is the side length or the Euclidean diameter of a grid cell. Please reconcile the notation so that the derivation of α < 2 is checkable.
  3. [Section 1.1 and operation semantics] The paper allows multiple insertions of a point but defines P as a set. The treatment of multiplicities is not formalized; please clarify whether multiplicities are tracked separately and how deletion of one copy affects the hierarchical clustering.
  4. [Section 4, proof of Theorem 2] The proof says the data structure has 'O(d log Δ) levels'; this is a valid but loose upper bound on M = log(√d(Δ−1)). It may be clearer to state M = O(log Δ + log d) and then note that this is O(d log Δ) when d is not constant.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the main approximation and runtime theorems are derived from explicit packing, grid, and Chernoff-bound arguments, with no fitted input relabeled as a prediction and no load-bearing self-citation.

full rationale

The paper's derivation is self-contained in the relevant sense. Section 2 defines an alpha-good family and proves Lemma 4 (representative distance bound) and Lemma 5 (pointwise approximation guarantee) directly from the family's packing property (b), covering property (c), and the triangle inequality. The low-dimensional data structure (Section 3) then proves that its insertion routine maintains an alpha-good family for alpha < 2 by an explicit grid-distance calculation, and the deletion routine relies on a packing bound (children per point is O_d(1)) that is asserted without proof but is not an input to the approximation argument. The high-dimensional structure (Section 4) uses randomly shifted grids and Chernoff bounds to prove the covering and packing properties; the success probability is computed from the grid lemma, not imported from the theorem. The only author-overlapping citation is [CSS16], which appears in related work on sliding windows and is not used in any proof. The correctness gap identified by the skeptic in Corollary 6 (choosing T from the set difference of P_j and P_i while C_{i-1}(y) is only defined for y in the set difference of P_{i-1} and P_i, with the possibility that P_{i-1}=P_i) is a genuine proof gap in the exact-k clustering extension, but it is not circularity: the approximation bound is not assumed as an input, and the missing case does not make the claimed result equivalent to its hypotheses by construction.

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

The paper introduces no new entities and fits no parameters. It relies on standard probabilistic and geometric tools plus the domain assumption of a bounded discrete grid. The central proofs are self-contained within these.

assumptions (5)
  • domain assumption Input points lie in {1,...,Δ}^d, so all pairwise distances are at most √d(Δ−1) and at least 1.
    Defines the problem model in Section 1.1; it bounds the number of hierarchy levels M = log(√d(Δ−1)) and is needed for all polylog(Δ) time bounds.
  • domain assumption The Johnson-Lindenstrauss lemma can reduce the dimension to O(log n) while preserving distances up to a constant factor.
    Stated in Section 1.1 as a way to assume d = O(log n); not actually used in the proofs of Theorems 1 and 2, which bound the number of levels by O(d log Δ) directly.
  • standard math Dynamic perfect hashing or cuckoo hashing supports constant expected amortized insert/delete and constant worst-case lookup.
    Invoked in Sections 3 and 4 to store the grid hash tables for each P_i and P_{i,j}.
  • standard math Chernoff bounds: for independent Bernoulli variables, Pr[sum = 0] ≤ e^{-expected/2} (as used in Lemma 12).
    Used to bound the expected cost of processing grid cells in the high-dimensional sampling analysis.
  • standard math In constant dimension d, the packing number of points with mutual distance > r within a ball of radius O(r) is O_d(1).
    Underlies the unproved claim that a point has O_d(1) children in Section 3, Deletions.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Fully dynamic hierarchical diameter k-clustering and k-center." pith.science (2026). https://pith.science/paper/GPRCFKP4

@misc{pith2026190802645,
  author       = {Pith},
  title        = {Pith review of: Fully dynamic hierarchical diameter k-clustering and k-center},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/GPRCFKP4}},
  note         = {Machine review of arXiv:1908.02645}
}
abstract

We develop dynamic data structures for maintaining a hierarchical k-center clustering when the points come from a discrete space $\{1,\ldots,\Delta\}^d$. Our first data structure is for the low dimensional setting, i.e., d is a constant, and processes insertions, deletions and cluster representative queries in $\log^{O(1)} (\Delta n)$ time, where $n$ is the current size of the point set. For the high dimensional case and an integer parameter $\ell > 1$, we provide a randomized data structure that maintains an $O(d \ell)$-approximation. The amortized expected insertion time is $O(d^2 \ell \log n \log \Delta)$. The amortized expected deletion time is $O(d^2 n^{1/\ell} \log^2 n \log \Delta)$. At any point of time, with probability at least $1-1/n$, the data structure can correctly answer all queries for cluster representatives in $O(d \ell \log n \log \Delta)$ time per query.

Figures

Figures reproduced from arXiv: 1908.02645 by the authors.

Figure 1
Figure 1. A point set P, an α-good set family, and two ways to represent this family as a tree. The middle one shows a compacted dendrogram, where multiple merges can happen at the same time. The right one shows a representation that is closer to the set family. Finally, every point in Pi−1 that was not promoted to Pi has a neighbor in Pi , i.e., a point at distance 2 i . Thus, condition (c) is true for all points in Pi−1 \ P… view at source ↗
Figure 2
Figure 2. The example from Figure 1, and a clustering for [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗

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. Fully Dynamic k-Center Clustering in Doubling Metrics

    cs.DS 2019-08 conditional novelty 7.0 of 10

    A fully dynamic algorithm maintains a (2+ε)-approximate k-center clustering in doubling metrics with polylogarithmic update time independent of k.

Reference graph

Works this paper leans on

22 extracted references · 22 canonical work pages · cited by 1 Pith paper

  1. [1]

    1-2, 29--53

    Hyung - Chan An, Aditya Bhaskara, Chandra Chekuri, Shalmoli Gupta, Vivek Madan, and Ola Svensson, Centrality of trees for capacitated k-center, Mathematical Programming 154 (2015), no. 1-2, 29--53

    work page 2015

  2. [2]

    3, 385--415

    Judit Bar - Ilan, Guy Kortsarz, and David Peleg, How to allocate network centers, Journal of Algorithms 15 (1993), no. 3, 385--415

    work page 1993

  3. [3]

    55, 2016, pp

    Deeparnab Chakrabarty, Prachi Goyal, and Ravishankar Krishnaswamy, The non-uniform k -center problem , Proceedings of the 43rd I nternational C olloquium on A utomata, L anguages, and P rogramming (ICALP), vol. 55, 2016, pp. Art. No. 67, 15

    work page 2016

  4. [4]

    T. - H. Hubert Chan, Arnaud Guerqin, and Mauro Sozio, Fully dynamic k-center clustering , Proceedings of the 2018 World Wide Web Conference on World Wide Web (WWW), 2018, pp. 579--587

    work page 2018

  5. [5]

    5036--5044

    Flavio Chierichetti, Ravi Kumar, Silvio Lattanzi, and Sergei Vassilvitskii, Fair clustering through fairlets, Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017 (NIPS), 2017, pp. 5036--5044

    work page 2017

  6. [6]

    Chen, Jian Li, Hongyu Liang, and Haitao Wang, Matroid and knapsack center problems, Algorithmica 75 (2016), no

    Danny Z. Chen, Jian Li, Hongyu Liang, and Haitao Wang, Matroid and knapsack center problems, Algorithmica 75 (2016), no. 1, 27--52

    work page 2016

  7. [7]

    505--517

    Michael Cochez and Hao Mou, Twister tries: Approximate hierarchical agglomerative clustering for average distance in linear time, Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data, 2015, pp. 505--517

    work page 2015

  8. [8]

    19:1--19:12

    Vincent Cohen - Addad, Chris Schwiegelshohn, and Christian Sohler, Diameter and k-center in sliding windows, Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP), 2016, pp. 19:1--19:12

    work page 2016

Show all 22 references
  1. [9]

    Martin Dietzfelbinger, Anna R. Karlin, Kurt Mehlhorn, Friedhelm Meyer auf der Heide , Hans Rohnert, and Robert Endre Tarjan, Dynamic perfect hashing: Upper and lower bounds, SIAM Journal on Computing 23 (1994), no. 4, 738 -- 761

    1994

  2. [10]

    Long, Performance guarantees for hierarchical clustering, Journal of Computer and System Sciences 70 (2005), no

    Sanjoy Dasgupta and Philip M. Long, Performance guarantees for hierarchical clustering, Journal of Computer and System Sciences 70 (2005), no. 4, 555--569

    2005

  3. [11]

    David Eppstein, Fast hierarchical clustering and other applications of dynamic closest pairs, ACM Journal of Experimental Algorithmics 5 (2000), 1

    2000

  4. [12]

    Greene, Optimal algorithms for approximate clustering, Proceedings of the 20th Annual ACM Symposium on Theory of Computing (STOC), 1988, pp

    Tom \' a s Feder and Daniel H. Greene, Optimal algorithms for approximate clustering, Proceedings of the 20th Annual ACM Symposium on Theory of Computing (STOC), 1988, pp. 434--444

    1988

  5. [13]

    Gonzalez, Clustering to minimize the maximum intercluster distance, Theoretical Computer Science 38 (1985), 293--306

    Teofilo F. Gonzalez, Clustering to minimize the maximum intercluster distance, Theoretical Computer Science 38 (1985), 293--306

    1985

  6. [14]

    1371--1380

    Sean Gilpin, Buyue Qian, and Ian Davidson, Efficient hierarchical clustering of large high dimensional datasets, 22nd ACM International Conference on Information and Knowledge Management (CIKM), 2013, pp. 1371--1380

    2013

  7. [15]

    Nemhauser, Easy and hard bottleneck location problems, Discrete Applied Mathematics 1 (1979), no

    Wen - Lian Hsu and George L. Nemhauser, Easy and hard bottleneck location problems, Discrete Applied Mathematics 1 (1979), no. 3, 209--215

    1979

  8. [16]

    Hochbaum and David B

    Dorit S. Hochbaum and David B. Shmoys, A unified approach to approximation algorithms for bottleneck problems, Journal of the ACM 33 (1986), no. 3, 533--550

    1986

  9. [17]

    Sussmann, Fault tolerant k-center problems, Theoretical Computer Science 242 (2000), no

    Samir Khuller, Robert Pless, and Yoram J. Sussmann, Fault tolerant k-center problems, Theoretical Computer Science 242 (2000), no. 1-2, 237--245

    2000

  10. [18]

    Sussmann, The capacitated K-center problem , SIAM Journal on Discrete Mathematics 13 (2000), no

    Samir Khuller and Yoram J. Sussmann, The capacitated K-center problem , SIAM Journal on Discrete Mathematics 13 (2000), no. 3, 403--418

    2000

  11. [19]

    Williamson, A general approach for incremental approximation and hierarchical clustering, SIAM Journal on Computing 39 (2010), no

    Guolong Lin, Chandrashekhar Nagarajan, Rajmohan Rajaraman, and David P. Williamson, A general approach for incremental approximation and hierarchical clustering, SIAM Journal on Computing 39 (2010), no. 8, 3633--3669

    2010

  12. [20]

    188--200

    Jian Li, Ke Yi, and Qin Zhang, Clustering with diversity, Proceedings of the 37th International Colloquium on Automata, Languages and Programming (ICALP), 2010, pp. 188--200

    2010

  13. [21]

    165--178

    Richard Matthew McCutchen and Samir Khuller, Streaming algorithms for k-center clustering with outliers and with anonymity, Proceedings of the 11th APPROX and 12th RANDOM , 2008, pp. 165--178

    2008

  14. [22]

    2, 122--144

    Rasmus Pagh and Flemming Friche Rodler, Cuckoo hashing, Journal of Algorithms 51 (2004), no. 2, 122--144

    2004

Pith tools

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