- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This manuscript studies dynamic local search for (k,z)-clustering (z=1 is k-median and z=2 is k-means) in dynamic metric spaces subject to monotonic distance decreases.
To get over the static O(n^2) bottleneck of finding improving center/non-center swaps in local search, the paper designs a deterministic dynamic swap-table data structure. It maintains the best improving swap in worst-case time O(k log k + log n) when the updated pair is disjoint from the current centers, and O(n log n) otherwise, with O(nk) preprocessing.
The paper proves that this data structure maintains a O(1) approximate clustering with total update time O~(k n^2) across all adversarial distance decreases, which matches the runtime of one static local search.
The method is evaluated on temporal graph snapshots (DBLP & Stack Overflow, up to 55K vertices) for k-median, against FastPAM1 (cold start or with warmup).
Critical strengths
S1. Proving that an arbitrary sequence of distance decreases can be maintained in total update time O~(k n^2) is a notable theoretical achievement in dynamic algorithms, as this matches up to polylog factors the runtime of one static local search.
S2. Algorithm is fully deterministic, and provides worst-case guarantees against adaptive adversaries.
Critical weaknesses
W1. Motivating monotonic distance decreases with "embedding drift" is incorrect. The dynamic model is limited strictly to distance decreases. This is well-motivated for shortest-path graph growth (with edge insertion), but it cannot accommodate metric fluctuations where distances increase, edges are deleted, or points are dynamically added/removed.
W2. Isolating swap-table maintenance while ignoring the Omega(n^2) cost of dynamic APSP distance maintenance gives a false impression of real-world speedups on evolving graphs.
W3. Edge insertions rarely trigger any swap improvements. So comparing solely against FastPAM1 methods (which rebuild swap tables from scratch at every insertion) constructs an artificial baseline advantage. A simple lazy threshold baseline (e.g., recompute only after objective drift exceeds some epsilon) must be benchmarked.
W4. Extending local search approximation guarantees via rho-relaxed triangle inequalities introduces large constant factors into the approximation that are not properly discussed in the paper.
Questions for authors
Q1. What is the exact numerical constant-factor approximation ratio resulting from the proof in Appendix B when instantiated for k-median (z=1) and k-means (z=2) in a \rho-relaxed metric space?
Q2. How does your dynamic local search compare in wall-clock time and objective cost against a lazy baseline that triggers local search only when cumulative edge insertions modify vertex neighborhoods of existing centers?
Q3. If an incremental APSP data structure (like Ramalingam-Reps or Even-Shiloach) is integrated to supply the distance updates, what is the net wall-clock throughput per edge insertion?
\paragraph{Motivation and scope beyond graphs (qVXZ; Paao: W1).} We agree that the embedding example may only apply to very specific settings in which the drift is of a form that makes points move closer but not apart. We will state this limitation more explicitly.
However, we would like to stress that our contribution is not limited to dynamic graphs. Our model and algorithms apply to any fixed point set whose pairwise distances only decrease; graphs under edge insertions are just one such instance. Another example is when distances are estimates that are refined as new measurements arrive: the latency between two servers is commonly estimated by the minimum round-trip time observed so far, which can only decrease. We ran our experiments on graphs because in this setting natural update sequences from real data are readily available.
\paragraph{Recompute only after objective drift exceeds some epsilon (Paao: W3, Q2).} This criterion does not guarantee detection of improving swaps, since objective drift alone does not determine whether such a swap exists. Notice that these two scenarios are possible:
Therefore, we use the swap table algorithm to efficiently detect whether a sufficiently improving swap exists. Regarding (Q2), we would politely like to note that we do not see the intuition why this would be a good baseline.
\paragraph{APSP maintenance cost (Paao: W2, Q3).} In our theoretical result for graphs (Theorem 1.5), we account for the cost of maintaining distances. In the experiments, we assume that the distance matrix is given, since the model of our main contribution works with given distances rather than computing them from a graph. Our goal was to clearly isolate the performance of the local search aspect instead of benchmarking the full pipeline.
\paragraph{Approximation constants (Paao: W4, Q1).} After every adversarial update, the maintained solution satisfies the same condition that static local search guarantees at termination. By choosing ρ sufficiently close to 1 and δ sufficiently small, the approximation bound can be made arbitrarily close to the corresponding static bound.