Fully Dynamic $k$-Clustering in $\tilde O(k)$ Update Time
Authors: Sayan Bhattacharya
Martin Costa
Silvio Lattanzi
Nikos Parotsidis
Venue: NeurIPS 2023 poster (2023)
Keywords: clustering
k-median
k-means
dynamic algorithms
amortized analysis
TL;DR: We present a $O(1)$-approximate fully dynamic algorithm for the $k$-clustering problem with amortized update time $\tilde O(k)$ and worst-case query time $\tilde O(k^2)$.

Abstract: We present a $O(1)$-approximate fully dynamic algorithm for the $k$-median and $k$-means problems on metric spaces with amortized update time $\tilde O(k)$ and worst-case query time $\tilde O(k^2)$. We complement our theoretical analysis with the first in-depth experimental study for the dynamic $k$-median problem on general metrics, focusing on comparing our dynamic algorithm to the current state-of-the-art by Henzinger and Kale [ESA'20]. Finally, we also provide a lower bound for dynamic $k$-median which shows that any $O(1)$-approximate algorithm with $\tilde O(\text{poly}(k))$ query time must have $\tilde \Omega(k)$ amortized update time, even in the incremental setting.

Fully Dynamic lareek-Cuuua k-Clustering in Ō(k) Update Time
Sayan Bhattacharya University of Warwick
Martín Costa
University of Warwick
s. bhattacharry@rraaiikkkk....
martin. costa@warwick..... martti..cstaa@aaruaii
ac. uk
Silvio Lattanzi Google Research sil silviol@google.coo com
Nikos Parotsidis
Google Research
nikosp&google.com com
Abstract
We present a (1))axpproximat fully dynamic algorithm for the k-median and k- means problems on metric spaces with amortized update time (kk) and worst-case query time Ó We complement our theoretical analysis with the first in-depth experimental study for the dynamic k-median problem on general metrics, focusing on comparing our dynamic algorithm to the current state-of-the by Henzinger and Kale [20]. Finally, we also provide lower bound for dynamic k-median which shows that any O(p)aaproxximate algorithm with (ppoy((k) query time must have (2k) amortized update time, even the incremental setting.
1 Introduction
Clustering is a fundamental problem in unsupervised learning with several practical applications. In clustering, one is interested in partitioning elements into different groups (i.e. clusters), that elements in the same group are more similar to each other than to elements in other groups. One of the most studied formulations of clustering the metric clustering formulation. In this setting, elements are represented by points in a metric space, and the distances between points represent how similar the corresponding elements formally, the input to our problem consists of set of points U in metric space with distance function R 22, real number p 2 1, and an integer & > The goal is compute subset C U of size |S| < k, so as to minimize cost(S) == Σxey d(x,S) where d(z, S) == minges d(x, v). We refer to the points in as centers. We note that this captures well-known problems such as k-median clustering (when
(the closer elements are, the more similar they are). More
U x
1) or k-means clustering (when p 2).
Due this simple and elegant formulation, metric clustering has been extensively studied throughout the years, across range of computational models [14, 22, 1, 12, 15, 2, 31, 11, 7J. In this paper, we focus on the dynamic setting, where the goal is efficiently maintain good clustering when the input data keeps changing over time. Because of its immediate real-world applications, the dynamic clustering problem has received lot of attention from the machine learning community in recent years [16. 6, 10. 24, 18]. Below, we formally describe the model [13, 20, 3] considered in this paper.
At preprocessing. the algorithm receives the initial input U. Subsequently, the input keeps changing by means a sequence of update operations, where each update inserts/deletes point in U. Throughout this sequence of updates, the algorithm needs to implicitly maintain solution S C U to the current input (U. d). The algorithm has an approximation ratio of p 2 if and only if we always have cost(S*) S p oUt(U), where (U)(U) Finally, whenever one queries the algorithm, it has to return the list of centers in S*. The performance of dynamic algorithm is captured by its approximation ratio, its update time, and its query time. Let
minsçu,s & cost(S) denotes the optimal objective.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

UNNIT be the state of the input U at preprocessing. A dynamic algorithm has (amortized) update time O()) if for any sequence of t 2 0 updates, the total time it spends on preprocessing and handling the updates is O + [UNsr]) X). The time it takes to answer a query is called its query time.
Our Contributions. Our primary contribution is to design an algorithm for this problem with a near-optimal update time of Ökk), without significantly compromising on the approximation ratio and query time.' Interestingly, our algorithm can be easily extended to dynamic k-clustering for any constant p (see Appendix A). In the theorem below, we summarize our main result for dynamic k-median and k- m-maas..
Theorem 1.1. There exists dynamic algorithm that, with high probability, maintains ((1)- approximate solution to the k-median and k-means problems for general metric spaces under point insertions and deletions with (k) amortized update time and Ō(k²) worst-case query time.
is important to note that in practice an algorithm often receives the updates in batches of variable sizes [25, 29], so it is common for there to be significant number of updates between cluster requests. As a consequence, optimizing the update time is of primary importance in practical applications. For example, if the size of each batch of updates is ((k),, then our amortized query time becomes Ō(k2/k) ÖK), because the algorithm has to answer a query after processing least one batch. Thus, our dynamic algorithm has near-optimal update and query times when the updates arrive in moderately large batches.
In addition, it is possible to observe that any dynamic k-clustering algorithm must have (2k) query time, since the solution it needs to return while answering query can consist of k centers. We also show a similar lower bound on the update time of any constant approximate dynamic algorithm for this problem. This lower bound holds even in incremental setting, where we only allow for point-insertions in U. We defer the proof of Theorem 1.2 to Appendix D.
Theorem 1.2. Any ((1))approximat incremental algorithm for the k-median problem with (k)) query time must have Q(kk) amortized update time.
Theorem 1.2 implies that the ultimate goal in this line of research is to get ((1) approxxmmeee dynamic k-clustering algorithm with O(k) update time and (kk) query time. Prior to this work, however, the state-of-the-art result for dynamic k-median (and k-means) was due to Henzinger and Kale [20], who obtained ((1)-approximation ratio, Ō(A²2) update time and Ö(k²) query time. In this context, our result is a meaningful step toward obtaining asymptotically optimal algorithm for the problem.
We supplement the above theorem with experiments that compare our algorithm with that of [20]. To the best of our knowledge, this the first work in the dynamic clustering literature with detailed experimental evaluation of dynamic k-median algorithms for general metrics. Interestingly, we observe that experimentally our algorithm is significantly more efficient than previous work without impacting the quality of the solution.
Our Techniques. We first summarize the approach used in the previous state-of-the-ar result. In [20], the authors used a static algorithm for computing coreset of size Ö(k) black box to get a fully dynamic algorithm for maintaining a coreset of size Ö(k) for general metric spaces in worst-case update time Ō(k2). Their algorithm works by maintaining a balanced binary tree of depth O(logn)) n). where each leaf in the tree corresponds to point in the metric space [4]. Each internal node of the tree then takes the union of the (weighted) sets of points maintained by its two children and computes its coreset, which is then fed to its parent. They maintain this tree dynamically by taking all the leaves affected by an update and recomputing all the coresets at nodes contained in their leaf-to-root paths. Using state-of-the-a the-art static coreset constructions, this update procedure takes time Ö(k²). Unfortunately, if one wants to ensure that the final output is a valid corset of the metric space after each update, then there is no natural way to bypass having to recompute the leaf-to-ron path after the deletion of point that is contained in the final coreset. Hence, it is not at all clear how to modify this algorithm in order to reduce the update time to Ö(k).
'Trooughout this paper, use Ō(.) and (2(.) notations to suppress polylog(n) factors, where 10/.

---

We circumvent this bottleneck by taking a completely different approach compared to [20]. Our algorithm instead follows from the dynamization of a ((nk) time static algorithm for k-median by Mettu and Plaxton [28], where n = |U] We refer to this static algorithm as the MP algorithm. Informally, the MP algorithm works by constructing a set of (llog(//k)) layers by iteratively sampling random points at each layer, defining clustering of the points in the layer that are 'close' to these samples, and removing these clusters from the layer. The algorithm then obtains solution to the k-clustering problem by running a static algorithm for weighted k-median (defined in Section 2), on an instance of size Ok log(n/k)) defined by the clusterings at each layer. In order to dynamize this algorithm, we design a data structure that maintains (log(( n /k)) layers that are analogous to the layers in the MP algorithm. By allowing for some 'slack' in the way that these layers are defined, ensure that they can be periodically reconstructed in a way that leads to good amortized update time, while only incurring a small loss in the approximation ratio. The clustering at each layer is obtained by random sampling every time it is reconstructed and is maintained by arbitrarily reassigning a point in cluster the new center when the current center is deleted. We obtain a solution to the k-clustering problem from this data structure in the same way as the (static) MP algorithm- by running a static algorithm for weighted k-median an instance defined by the clusterings maintained at each layer.
2 Preliminaries
In our computational model, the algorithm has access to the distance d(a,yy for any x.y E U in ((1) time?. Given any two sets X,5 C U. define the cost of X w.r.f. S as cost(S, X) == Exex minyes d(a,,)) In addition, let cost(S) be function π U + U, and say that π assigns x E U ((). We refer to an assignment I with (TU)) S m as an m-assignment. The cost of X C U w.r.t. assignment π is cost( X) == Exex d(x, π (z)). We denote cost(z, U) by cost(TT. For any p 2 1, say that a p-approximate if cost(T) S p OU)(U), where OU) is the cost of the optimal solution.
cost(S, U). Next, define an assignment to
Given any subset U' C U and æ E U", we denote by By (x, r) the set ty E [d(x, v) S r), i.c. the closed ball in U" of radius 2 0 centered at x. When it is clear from the context that U" = U, we omit the subscript U' and simply write B(x, r). For X C U' C U, we define By (X. r) to be the union of the balls By (z, r) for E X.
Definition 2.1. Given < p < and subsets X U' C U, we define the following real numbers:
vx,XXU)) == min 2 0| (X, 2 p-10")), ==
IY S U" |Y| = k}.
In words, the real number (x, U²) is the smallest radius such that the closed ball of radius around X captures at least a p-proportion of the points in U'. The real number pa (U') is then defined to be the smallest such radius (X, U") over all subsets X C U of size k. Note that (X, U') and (4p(U") are both increasing as functions of p.
Finally, we will sometimes refer to the weighted k-median problem. An instance of this problem given by a triple (U, d, w). where w U + Rzo assigns nonnegative weight to every point E U. in a metric space with distance function d. Here, the goal is to compute a subset of at most centers S C U, so as to minimize cost,, (S) := Ever w(u)- - ddxx, S). We let opt.,. = minggu./sis* (S) denote the optimal objective value of this weighted k-mediaa instance. We will analogously use the symbol cost., (S, := Ezex w(x) d(x, S) denote the cost of set of points X w.r.t. S and the weight function w.
3 Our Algorithm
Throughout this section, we fix the following parameters: a, 3, 6, 7 and k': where a 2 is a sufficiently large constant, 3 is any constant in the interval (0, 1), > 0 is sufficiently small constant, 7 == eB, and k'' := max log((U]))
"This is standard and common assumption in clustering settings.
3

---

3.1 The Static Algorithm of [28]
Our starting point is the static algorithm of [28] for computing a (k)) U -> U, with = (U), such that cost(a) & O(1) opt(U') The relevant pseudocode appears in Algorithm and Algorithm 2.
Algorithm StaticAlgo(U))
I:
d and U1 t- U
2:
while [U]] > ak' do
3: (Ss, Ci, Gz 13) +- AlmostCover(U:)
4: U111+ U; \
5: iei+1
6: end while
7: i+i
8: S. S Un, Ct f- St and 1/ <
9: Assign each E C₁ to itself (i.e., (x) S
10: S U
be the assignment such that for j [f] and Cj, we have o(x) (x 12: return (8, (8,a,t)
Let
Algorithm 2 AlmostCover(U")
1: Construct a set S", by sampling ak' points from U' independently and u.a.r. with replacement
2: v' +- (S(S", U') and C" +- B(S', ,²)
3: Assign each x E C' some of (z) S' such that o o (x)) sv
4: return (S", C", C",'',1")
The algorithm runs for iterations. Let U, U denote the of unassigned points the start of iteration i E [t - 1] (initially, we have U1 = U). During iteration i, the algorithm samples a set of ak'' points S; as centers. uniformly random from U,. It then identifies the smallest radius vy such that the balls of radius around S; cover at least 3-fraction of the points in Ug. Let C2 C U, denote the set of points captured by these balls (note that C, 2 S, and |C| 8 -Ut)). The algorithm assigns each x E C to some center (1) E S; within distance of vs It then sets U4+1 <- U; \ C., and proceeds to the next iteration. In the very last iteration f, we have [U, I ak', and the algorithm
sets S, = U, C, == U,, and o, (x:) == for each U,
The algorithm returns the assignment with set of centers o oUU) S, where is simply the union of o; for all E [t].
Fix any i E [t 1]. Since |C|1 2 3 [Ur] we have |0+11| < (1 3) [U As is constant, it follows that the algorithm runs for Ö(1) iterations. Since each iteration picks O(k) new centers, get: |S| Ō(k), and hence -as)-aassggmmen. Furthermore, [28] showed that cost(a) 011 oU)(
3.2 Our Dynamic Algorithm
The main idea behind our dynamic algorithm is that it maintains the output S of the static algorithm from Section 3.1 in a lazy manner, by allowing for some small slack at appropriate places. Thus, maintains layers, where each layer i E [t] corresponds to iteration i of the static algorithm. In the dynamic setting, the value
changes over time. Specifically, layer E [t] consists the tuple (U,, St, C, ox 144,, in Algorithm 1. Whenever large fraction of points gets inserted or deleted from some layer j E [t], the dynamic algorithm rebuilds all the layers E [j. t] from scratch.
The dynamic algorithm maintains the sets U,, S; and C explicitly, and the assignment implicitly, manner which ensures that for æ E C, it can return (x) E S; in O(1) time. Furthermore, for each layer i E [4] it explicitly maintains the value (resp. nt), ), which denotes the size of the set U, at (resp. the number of updates to U, since) the time was last rebuilt. We explain this more detail below. The value is needed only for the sake of analysis.

---

Algorithm 3 Preprocess(U)
U1 t
2: ConstructFromlayer((]
Algorithm 4 ConstructFromLayerr()
1:
2: while | > ak' do
3:
R2 + |U and n +-
4: (S), Cj 5. v2) AlmostCover(U;)
5:
Un+1 + U \
6:
jti+1
7: end while
8: j
9: S. U, Ct +- S, and v4 <- 0
Assign each x C₁ itself (i.e., (x)x) x E S.)
11: S 3 UsEnn
12: : + S be the assignment such that for all j E [t] and E Cj. we have oxx) = =z((x)
Preprocessing: At preprocessing, essentially run the static algorithm from Section 3.1 to set the value and construct the layers E [t]. See Algorithm and Algorithm 4. Note that at this stage n; = 0 for all layers E [t].
Algorithm 5 Insert(r)
for I,.... do
2: Add x to U;
3: n <-n +1
4: end for
5: Add x to C, and S,, and set (x))) + x
6: Rebuild
Handling the insertion of a point x in U: We simply add the point to U,, for each layer E [t]. Next, in the last layer we create new center at point a: and assign the point x to itself. Finally, we call the Rebuild subroutine (to be described below). See Algorithm 5.
Handling the deletion of a point æ from U: Let j E [t] be the last layer (with the largest index) containing the point x. We remove æ from each layer i [i]. Next, i was center layer j. then pick any arbitrary point x' E Eoj (x) \ {a) (if such point exists), make x' center, and assign every point E o (xx {a} to the newly created center x'. Finally, we call the Rebuild subroutine (to be described below). See Algorithm 6.
The rebuild subroutine: We say that a layer [t] is rebuilt whenever our dynamic algorithm calls ConstructFromLayeera
for some add/remove point in U,. It is easy to see that nę denotes the number of updates in layer E [t] since the last time it was rebuilt (see Line 3 in Algorithm 4, Algorithm 5 and Algorithm 6). Next, we observe that Line
and that there is update in layer i whenever
Algorithm 5 and Line 16 Algorithm 6, along with the pseudocode of Algorithm imply the following invariant.
Invariant 3.1. n S rn; for all [t]. Here, n; is the size of U, just after the last rebuild of layer i, and n is the number of updates in layer since that last rebuild.
Intuitively, the above invariant ensures that the layers maintained by our dynamic algorithm remain close to the layers of the static algorithm in Section 1.1. This is crucially exploited in the proofs of Lemma 3.2 (which helps us bound the update and query times) and Lemma 3.3 (which leads to desired bound on the approximation ratio). We defer the proofs of these two lemmas Appendix B.
Lemma 3.2. We always have i = Ö(1), where denotes the number of layers maintained by our dynamic algorithm.
5

---

Algorithm 6 Delete(1)
for l.... do if x: E U, then
2:
3: Remove a from U, and set ni + ni +
4:
if x E C, then
5:
Remove x from C2
6:
if x E S₁ then
7:
Remove x from S if 3 y E of (x) (xx)
8:
{ then
9:
Pick any such and place it into S;
10:
Set a;()) to y for each Eo (x)
11:
end if
end
13: end if
14: end if'
15:
end for
16: Rebuild
Algorithm 7 Rebuild
2: while i S and m < rn, do
3: i i+1
4: end while
5: if S then
6:
ConstruccFromlayer((
7: end if
Lemma 3.3. The assignment maintained by our dynamic algorithm always satisfies cost(o) (pt))))
Answering a query: Upon receiving query, consider weighted k-median instance (S, w), where each point æ E receives a weight w(x) == -=-=(()) Next, we compute (11)aaprroximate solution S C S, with |S*| S k, this weighted instance, that cost., (S* S) O(1) opt,,
We then return the centers in S*
Corollary 3.4. cost(S*) = 0(1) oU)(U).
Corollary 3.4 implies that our dynamic algorithm has ((1) approximation ratio. holds because of Lemma 3.3, and its proof immediately follows from [19]. We delegate this proof to Appendix C.
Corollary 3.5. Our algorithm has Ō(k²) query time.
Proof (Sketch). By Lemma 3.2, we have Ō(1). Since the dynamic algorithm maintains most Ö(k) centers S, in each layer (follows from Invariant 3.1), have |S| Σie(t) |S| Ō(k). Using appropriate data structures (see the proof Claim 3.7), in O(1) time we can find the number of points assigned any center
S under (given by |o -1 (x:) w(x)). Thus, the weighted k-median instance (S, d, w) is of size Ökk), and upon receiving query in Ō(k) time. We now run static O())aaprrxximation algorithm [27] on (S, d, w), which returns the set St in ((k2) time.
construct the instance
Lemma 3.6. Our algorithm has Ö(k) update time.
Corollaries 3.4, 3.5 and Lemma 3.6 imply Theorem 1.1. now remains to prove Lemma 3.6.
3.3 Proof Lemma 3.6
We first bound the time taken to handle an update, excluding the time spent rebuilding the layers.

---

To summarize, each update in U creates Ö(1) units of potential, and the total time spent on the calls to Rebuild is at most Ō(k) times the decrease the potential. Since the potential & is always nonegative, follows that the amortized time spent on the calls to Rebuild is Ö(k). This observation, Claim 3.7. Excluding the calls to Rebuild, Algorithm 5 and Algorithm 6 both run in (11) time.
Proof. We first describe how our dynamic algorithm maintains the assignment a implicitly, In each layer i E [t), the assignment
partitions the set C₁ into |S:] clusters {o, (a)) For each such cluster Z = o; (x), we maintain: (1) a unique id, given by id( Z), (2) its center, given by (enter(id(2)) == x; and (3) its size, given by size(id(Z)) == |Z]. For each point y E Z, we also maintain the id of the cluster it belongs to, given by cluster(y)) == id (). Using these data
structures, for any y E C, we can report in ((1) time the center oi and we can also report the size of cluster in (1) time.
Recall that t = ((1) as per Lemma 3.2. Thus, Algorithm 5 takes (1)) time, excluding the call to Rebuild in Line 6. For Algorithm 6, the key thing to note is that using the data structures described above, Lines 8 10 can be implemented in O(1) time, by setting as the new center of the cluster
of (z) and by decreasing the size of the cluster by one. It follows that excluding the call to Rebuil Id in Line 16, Algorithm 6 also runs in (() time.
Claim 3.8. A call to ConstructPromLayert
described in Algorithm 4, takes Ö(k (U:]) time.
Proof (Sketch). By Lemma 3.2, the while loop in Algorithm 4 runs for Õ(1) iterations. Hence, within a (() factor, the runtime of Algorithm 4 is dominated by the call to AlmostCover(U), in Line 4. Accordingly, we now consider Algorithm 2. As the ball By (X, can be computed in O . (0"l) time, using a binary search the value v' (see Line 2) can be found in Ö(k (U"() time. The rest of the steps in Algorithm 2 also take Ö(k - (U')) time. Thus, it takes Ō [Uy]] time to implement Line 4 of Algorithm 4. Hence, the total runtime of Algorithm 4 is Σ}e((,)) Ö(k ((U)))))) ΣjEu, Ö(k (U+)) = Ō(k (U,)).
Define the potential = Eiejg nz. For each update in U, the potential & increases by at most t, excluding the calls to Rebuild ld (see Algorithm 5 and Algorithm 6). Thus, by Lemma 3.2, each update increases the value of & by at most Ó(1). Now, consider any call to ReconstrrctFroonayyer(( Algorithm 7 and Invariant 3.1 ensure that just before this call, we had nę rn, (2(UU)), since is a constant. Hence, because of Line 3 in Algorithm 4, during this call the value of Φ decreases by at least I2(( Claim 3.8, in contrast, implies that the time taken to implement this call is Ó(k: (U,]).
along with Claim 3.7, implies Lemma 3.6.
4 Experimental Evaluation
Datasets. We conduct the empirical evaluation of our algorithm on five datasets from the UCI
repository [17]: (1) Census [23] with 2, 458, 285 points of dimension 68, (2) KDD-Cup [32]
containing 311, 029 points of dimension 74, (3) Song [5] with 515, 345 points of dimension 90, (4) Drift [33, 30) with 13, 910 points of dimension 129, and (5) SIFT10M [17] with 11, 164, 866 points of dimension 128.3
We generate the dynamic instances that we use in our study follows. We keep the first 10, 000 points of each dataset, in the order that they appear in their file. This choice allows us to test against competing algorithms that not efficient, and at the same time captures the different practical aspects of the algorithms that we consider; as a sanity check, we perform an experiment on an instance that is order of magnitude larger to confirm the scalability of our algorithm, and that the relative behavior in terms of the cost of the solutions remains the same among the tested algorithms.
'e are not aware of any dynamic dataset containing the sequence of arrivals and that is publicly available. We generated sequences of updates following typical setting used in studies of dynamic algorithms (e.g.. [16]..
7

---

We use the Ly distance of the embeddings of two points to compute their distance. To avoid zero distance without altering the structural properties of the instances, we add 1/|U] all distances, where U is the set of points of the instance.
Order of Updates. We obtain a dynamic sequence of updates following the sliding window approach. In this typical approach, one defines a parameter k indicating the size of the window, and then "slides" the window over the static sequence of points in steps creating at each step i a point insertion of the i-th point (if there are more than i points) and a point deletion of the (i x))th point (if K > i), until each point of the static instance is inserted once and deleted once. We set A = 2, 000, which results in our dynamic instances having at most 2, 000 points at any point in time.
Algorithms. We compare our algorithm from Section against the state-of-the art algorithm for maintaining solution to the k- k-median problem, which is obtained by dynamically maintaining coreset for the same problem [20]. In particular, [20] presented an algorithm that can dynamically maintain e-coreset of size O( poly (log n, log(1 (1/))) for the k-median and the k-means problems. Their algorithm has a worst-case update time of (c poly (log n, log(1/e))). To the best of our knowledge, this is the first implementation of the algorithm in [20]. For brevity, we refer to our algorithm as OURALG, and the algorithm from [20] as HK.
Since the exact constants and thresholds required to adhere to the theoretical guarantees of [20] are impractically large, there is no obvious way to use the thresholds provided by the algorithm in practice without making significant modifications. In order to give fair comparison of the two algorithms, we implemented each of them to have single parameter controlling a trade-off between update time, query time, and the cost of the solution. OUR ALG has a parameter d which we set to be the number of points sampled during the construction of a layer in Algorithm 2. In other words, we sample é points in Line 1 of Algorithm 2 instead of ak'' We fix the constants and used by our algorithm (see Section 3) to 0.2 and 0.5 respectively. HK has a parameter & which we set to be the number of points sampled during the static coreset construction from [9] which is used as black box, replacing the large threshold required to adhere to the theoretical guarantees. Since this threshold is replaced by single parameter, also replaces the other parameters used by HK, which are only used in this thresholding process. For the bicriteria algorithm required by this static coreset construction, we give the same implementation as the empirical evaluations in [9] and use kmeans++ with 2 iterations of Lloyd's.
For each of Φe and vis we experimented with the values 250, 500, 1000. As the values of Φb and are increased, the asymptotic update times and query times of the corresponding algorithms increase, while the cost of the solution decreases.
Setup. All of our code is written in Java and is available online.* 4 We did not use parallelization. We used a machine with 8 cores, a 2.9Ghz processor, and 16 GiB of main memory.
Results. We compare OURALG(Ø = 500) against HK = 1000). We selected these parameters such that they obtain good solution quality, without these parameters being unreasonably high w.r.t. the size of our datasets. Our experiments suggest that the solution quality produced by OURALG robust against different values of & (typically these versions of the algorithm differ by less than 1%), while that of HK is more sensitive (in several instances the differences are in the range of 3 - 9%, while for KDD-Cup HK (wb = 250) produces much worse solutions). The update time among the different versions of each algorithm do not differ significantly. Lastly, the query time of OURALG is less sensitive compared to the query time of HK. Specifically, the average query time of O 1000) is roughly 3 times slower than OURALG time of HK(2 = 1000) is 11 times slower compared to HK (v' = 250). For OURALG we selected the middle value 6 500. Since the solution quality of HK drops significantly when using smaller values of v we selected فi = 1000 to prioritize for the quality of the solution produced by the algorithm. Since we did not observe significant difference in the behavior across the datasets, we tuned these parameters considering three or our datasets. We provide the relevant plots in Appendix E.4.
250). while the average query
Update Time Evaluation. In Figure 1 (left) we plot the total update time over the sequence of updates for the dataset Song, and only for = 50. OURALG runs up to more than 2 orders of
http://wwww..eaaettttotttttttttt http://s2s--dyyyi----ree-- k-lustrring
8

---

magnitude faster compared to HK. independently of their parameter setup (see Appendix E for more details). The relative performance of the algorithms is similar for all datasets and choices of k; we summarize the results in Table 1, while the corresponding plots can be found in Appendix E.
Cost of Solution (song, k 50)
Total Update Time (sec) (song, 50)
3.5
10a
101
2.5
2.0
15-
10-1
1.0
10
OutA 500
Ourölgelg
HR0p 10000]
0.0
HKipp 1000)
2500
5000
7500
10000
12500
15000
17500
20009
2500
5000
7500
10000
12500
15900
17500
20000
Upsates
Upoates
Figure 1: The total update time in seconds (left) and the solution cost (right) for OURALG =50) and HK (e) = 1000) on Song, for h = 50.
Table 1:
The ratio of the total update time incurred by ( = 1000) divided by the time for OURALG(Ø 500), for the five datasets that we considered and for & {10,50, 100).
Song
Census
KDD-Cup
Drift
SIFT10M
k: 10
31.774
32.172
62.776
32.408
32.857
k: 50
134.850
131.333
201.147
140.826
142.989
k: 100
262.427
255.927
377.350
276.848
280.925
Solution Cost Evaluation. Figure 1 (right) shows the of the solution obtained by AUGAL = 500) and (K( = 1000), on dataset Song for k = 50. In general, the two al- 500) producing slightly better (1.3% 1.3%%
gorithms have similar performance with OURALG( solutions on most instances; the exceptions being on the KDD-Cup dataset, where for k = 10 HK(μ 1000) performs 1.2% better, and for 100 where OURALG(Ø 500) performs 35% better. We summarize their relevant performance on the different datasets in Table 2, and provide the complete set of plots in the Appendix.
Table 2: The mean ratio of the solution cost for HK(1 1000) divided by that of OURALG 500) averaged over the updates, for the five datasets that we considered and for k E {10, 50, 100}.
Song
Census
KDD-Cup
Drift
SIFT10M
k 10
1.013
1.018
0.988
1.020
1.014
k = 50
1.036
1.056
1.019
1.037
1.032
k 100
1.049
1.065
1.538
1.059
1.038
Query Time Evaluation. Finally, we compare OURALG = 5000 to HK(2/ = 1000) in terms of their query time. To measure query time, we evenly distribute 100 queries across the update sequence and measure the average query time. In Table 3 we report the average ratio of the query times obtained by OURALG(Ç = 500) divided by that of HK (1/ 1000) over the queries executed on each of the datasets and parameters of i that we considered. The query time obtained by the 500) performs better on
two algorithms is typically within a factor 2 of each other. OURAL. KDD-Cup, while (K 1000) performs better rest of the datasets. This inconsistency is due to differences in the structure of the datasets (we also tried randomizing the order of the updates, and it didn't change the relative picture w.r.t. query time).
Longer Sequence Updates. While the above experiments capture well the different aspects of the two algorithms, we further conducted an experiment on the KDD-CUP dataset where we consider

---

Table 3: The mean ratio of query times for (* 1000) divided by that of OURALG 500), for the five datasets that we considered and for & E {10, 50, 100).
Song
Census
KDD-Cup
Drift
SIFT10M
k 10
0.575
0.586
2.629
0.577
0.572
k 50
0.568
0.577
1.888
0.570
0.564
A: 100
0.560
0.573
1.543
0.564
0.558
a window size of a = 5, 000 and applied it to the first 100, 000 points. As expected the relative performance in terms of solution cost and query time remains the same, while the gap in terms of update time grows significantly (HK(w) = 1000) performs more than 3 orders of magnitude worse than AURALG 500)). The corresponding plots and numbers provided in the Appendix.
Conclusion of the Experiments. Our experimental evaluation shows the practicality of our al- gorithms on set of five standard datasets used for the evaluation of dynamic algorithms in metric spaces. In particular, our experiments verify the theoretically superior update time of our algorithm w.r.t. to the state-of-the-ar algorithm for the fully-dynamic i--median problem [20], where our algorithm performs orders of magnitude faster than HK. On top of that, the solution quality produced by our algorithm is better than HK in most settings, and the query times of the two algorithms are comparable. We believe that our algorithm is the best choice when it comes to efficiently maintaining a dynamic solution for the k-median problem in practice.
References
[1] Sara Ahmadian, Ashkan Norouzi-Fard, Ola Svensson, and Justin Ward. Better guarantees for k-means and euclidean k-median by primal-dual algorithms. SIAM Journal on Computing, F9C4):707 2019.
[2] Nir Ailon, Ragesh Jaiswal, and Claire Monteleoni. Streaming k-means approximation. Advances in neural information processing systems, 22, 2009.
[3] MohammadHossein Bateni, Hossein Esfandiari, Hendrik Fichtenberger, Monika Henzinger, Rajesh Jayaram, Vahab Mirrokni, and Andreas Wiese. Optimal fully dynamic k-center clustering for adaptive and oblivious adversaries. SODA, 2023.
[4] Jon Louis Bentley and James B Saxe. Decomposable searching problems i. static-to-yynamia transformation. Journal of Algorithms, 144):301-358, 1980.
[5] Thierry Bertin-Mahieux, Daniel PW Ellis, Brian Whitman, and Paul Lamere. The million song dataset. 2011.
[6] Sayan Bhattacharya, Silvio Lattanzi, and Nikos Parotsidis. Efficient and stable fully dynamic facility location. Advances in neural information processing systems, 2022.
[7] Michele Borassi, Alessandro Epasto, Silvio Lattanzi, Sergei Vassilvitskii, and Morteza Zadi- moghaddam. Sliding window algorithms for k-clustering problems. Advances in Neural Information Processing Systems, 1187776-87777. 2020.
[8] Vladimir Braverman, Vincent Cohen-Addad, Shaofeng H.-C. Jiang, Robert Krauthgamer, Chris Schwiegelshohn, Mads Bech Toftrup, and Xuan Wu. The power of uniform sampling for coresets. In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver, CO, USA, October -Nvember 3, 2022, pages 462-473. IEEE, 2022.
[9] Vladimir Braverman, Dan Feldman, and Harry Lang. New frameworks for offline and streaming coreset constructions. CoRR, abs/1612.00889, 2016.
[10] Vladimir Braverman, Gereon Frahling, Harry Lang, Christian Sohler, and Lin F Yang. Clustering high dimensional dynamic data streams. In International Conference on Machine Learning, pages 576-585. PMLR, 2017.
10

---

[11] Vladimir Braverman, Harry Lang, Keith Levin, and Morteza Monemizadeh. Clustering problems on sliding windows. In Proceedings of the wventy-sevente annual ACM-SIAM symposium on Discrete algorithms, pages 1374-1390. SIAM, 2016.
[12] Jaroslaw Byrka, Thomas Pensyl, Bartosz Rybicki, Aravind Srinivasan, and Khoa Trinh. An improved approximation for k-median and positive correlation in budgeted optimization. ACM Trunsactions on Algorithms (TALG), 13(2):1-31, 2017.
[13] TH Hubert Chan, Arnaud Guerqin, and Mauro Sozio. Fully dynamic k-center clustering. In Proceedings of the 2018 World Wide Web Conference, pages 579-587, 2018.
[14] Moses Charikar, Sudipto Guha, Eva Tardos, and David B Shmoys. A constant-factor approx- imation algorithm for the k-median problem. Proceedings of the thirty-first annual ACM symposium on Theory of computing, pages 1-10, 1999.
[15] Moses Charikar, Liadan O' O'Callaghan, and Rina Panigrahy. Better streaming algorithms for clustering problems. In Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, pages 30-39, 2003.
[16] Vincent Codan-Addad, Niklas Oskar D Hjuler, Nikos Parotsidis, David Saulpic, and Chris Schwiegelshohn. Fully dynamic consistent facility location. Advances in Neural Information Processing Systems, 32, 2019.
[17] Dheeru Dua and Casey Graff. UCI machine learning repository, 2017.
[18] Gramoz Goranci, Monika Henzinger, Dariusz Leniowski, Christian Schulz, and Alexander Svozil. Fully dynamic k-center clustering in low dimensional metrics, In Proceedings of the Symposium on Algorithm Engineering and Experiments, ALENEX 2021, Virtual Conference, Jamuary 10-11, 2021, pages 143-153. SIAM, 2021.
[19] Sudipto Guha, Nina Mishra, Rajeev Motwani, and Liadan O'Callaghan. Clustering data streams. In 4/st Anmual Symposium on Foundations of Computer Science, pages 359-366, IEEE Computer Society, 2000.
[20] Monika Henzinger and Sagar Kale. Fully-dynamic coresets. In 28th Annual European Sympo- sium on Algorithms, ESA 2020, September 7-9, 2020, Pisa, Italy (Virtual Conference), volume 173 of LIPIcs, pages 57:1-57:21 2020.
[21] Lingxiao Huang and Nisheeth K. Vishnoi. Coresets for clustering in euclidean spaces: impor- tance sampling is nearly optimal. In Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020, pages 1416-1429. ACM, 2020.
[22] Kamal Jain and Vijay V Vazirani. Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and lagrangian relaxation. Journal of the ACM (JACM), 48(2):274-296 2001.
[23] Ron Kohavi et al. Scaling up the accuracy of naive-bayes classifiers: A decision-tree hybrid. In Kdd, volume 96, pages 202-207, 1996.
[24] Silvio Lattanzi and Sergei Vassilvitskii. Consistent k-clustering, In International Conference on Machine Learning, pages 1975-1984. PMLR, 2017.
[25] Quanquan C. Liu, Jessica Shi, Shangdi Yu, Laxman Dhulipala, and Julian Shun. Parallel batch-dynamic algorithms for k-core decomposition and related graph problems. In 34th ACM Symposium on Parallelism in Algorithums and Architectures (SPAA), pages 191-204, ACM, 2022.
[26] Ramgopal R. Mettu. Approximation Algorithms for NP-Hard Clustering Problems. PhD thesis, Department of Computer Science, University of Texas at Austin, 2002.
[27] Ramgopal R. Mettu and C. Greg Plaxton. The online median problem. In 41st Annual Symposium on Foundations of Computer Science, FOCS 2000, 12-14 November 2000, Redondo Beach, California, USA, pages 339-348. IEEE Computer Society, 2000.
11

---

[28] Ramgopal R. Mettu and C. Greg Plaxton. Optimal time bounds for approximate clustering. In UAI '02, Proceedings of the 18th Conference in Uncertainty in Artificial Intelligence, pages 344-351. Morgan Kaufmann, 2002.
[29] Krzysztof Nowicki and Krzysztof Onak. Dynamic graph algorithms with batch updates in the massively parallel computation model. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2939-29999 2939-2958. SIAM, 2021.
[30] Irene Rodriguez-Lujan, Jordi Fonollosa, Alexander Vergara, Margie Homer, and Ramon Huerta. On the calibration of sensor arrays for pattern recognition using the minimal number of experi- ments. Chemometrics and Intelligent Laboratory Systems, 130: 123-14,,, 2014.
[31] Michael Shindler, Alex Wong, and Adam Meyerson. Fast and accurate k-means for large datasets. Advances in neural information processing systems, 24, 2011.
[32] S.J. Stolfo, Wei Fan, Wenke Lee, A. Prodromidis, and P.K. Chan. Cost-hased modeling for fraud and intrusion detection: results from the jam project. In Proceedings DARPA Information Survivability Conference and Exposition. DISCEX 00, volume 2, pages 130-144 vol.2, 2000.
[33] Alexander Vergara, Shankar Vembu, Tuba Ayhan, Margaret A Ryan, Margie L Homer, and Ramón Huerta. Chemical gas sensor drift compensation using classifier ensembles. Sensors and Actuators B: Chemical, 166:320-329, 2012.
12

---

A Extension to k-Means and (k.p))Clustering
As stated in [21, 81. while [28] only discusses the k-median problem. their construction can easily be modified to work for k-means clustering and further generalized to work for (k, p)-clsttering, where the -cclutttng problem is defined the same way as k-median problem except that we want to minimize ΣzEU d(z, S)" for some S S U of size at most k. Note that (k, 1 -lclusterigg and (k; 2) 2)-cuettei correspond to k-median and k-means respectively.
We define p-metric space (U, d) in the same way metric space except for relaxing the condition that d must satisfy the triangle inequality to the condition that d(x, y) S p(d(x, 2) + d(z, y)) for all x, y/ U. Given metric space (U, d) and some p 2 1, the results in Section 6 of [9] can easily be used to show that (U, is a 2 -mttric space, where d' (z. y) is defined to be d(x y)P.
We now show that the assignment a maintained by our algorithm is O >approximatee when U is p-metrie space (i.e. that cost(ar) = O(p²). opt(U)) and that the extraction technique of [19] can be generalized to p-metric spaces.
Lemma A.1. When the underlying space U is a p-metric space, the assignment a maintained by our algorithm is "(p"))apppooiiiiii -approximate.
Proof. By making the appropriate changes to the proofs of Lemma B.3 and Lemma B.4, we get generalizations of these lemmas to p-metric spaces, where the lemma statements are the same except for an extra p factor in the inequalities.
Lemma A.2. Given any positive &, there exists sufficiently large choice of a such that vs S )
2p- p4, (U for each E [t [t- 1] with probability at least 1 -tk
Lemma A.3. Given metric subspaces U1 and U2 Of such that |01 U2 S E7/U1), we have that (Ui) s 2p- pay (U2).
These two lemmas immediately imply the following generalization of Lemma B.5.
Lemma A.4. V; S 4p² pa- (U:) for each E [t - 1] with probability at least e -Ek"
The upper bound on cost(a) given in Lemma B.6 can be generalized by noticing that cost(o, Ct) S [p for all E [t 1]. which us that
cost(a)
2pus[Ci].
The lower bound OU)(U) given in Lemma B.10 holds for p-metric spaces with no modifications.
Hence, we get that with probability at least - = we have that
16p
cost(a) Σ 2pp; C.l $
Σ 8p pppp/CCil
cost(S).
By making the appropriate modifications the proof of Theorem C.I, we can extend this theorem to work for p-metric spaces. In particular, we can obtain a proof of Theorem A.5 by taking the proof of Theorem C.1 and adding extra p factors whenever the triangle inequality applied.
Theorem A.S. Given a d-approximate m-assigument π U - U, any v-approximate solution to the weighted k-median instance ( (U), d, w). where each point I E (U) receives weight =app--xiaaappp
w(x) = | (x)), is also a (øp + 2(1 + x)bp"") -approximate solution to the k-median instance (U.d) where a p-metric space.
Since the algorithm in [27] is apprroiie on -(1)-metric spaces, it immediately follows by applying Theorem A.5 and Lemma A. that our algorithm maintains a O(1) aapr-appoee solution to the k-median problem on (U, dP) for p = O(1). Since the k-median problem on (U, d²) is exactly the (k:, plcustrtgi problem on (U, J, follows that our algorithm generalizes to solve instances of (k, p) cllustering in metric spaces.
13

---

B Proofs of Lemma 3.2 and Lemma 3.3
Throughout this section, we fix y to be any real such that 8 < y < 1 and be any real such that 0 minf 1-y
24 1}. Let (+ and y denote B(1 -c) c) and 7(1 2c) respectively.
B.1 Proof of Lemma 3.2
We first prove Lemma B.I, which shows that the sizes of the sets Us decrease exponentially with i. Lemma B.1. For all i E [t - 1), [Us+1| & (1- [Us)
Proof. Consider the ratio UU,1//|U,). Since U4+1 Us and U++1 is reconstructed every time U, is reconstructed, it follows that [U,-1/|U,; is at most (n + f)/(n, + - E'), where n, the size of Uş at the time it was last reconstructed and l and l' are the number of insertions and deletions that have occurred since the last time U141 was reconstructed respectively. By Lemma B.2, we get that this expression upper bounded by (n:-1 + Tm4+1)/ 1)/ng. Now
observe that
Us+1 UU:
T4+1 +
+6-6 S n4+1 + TTR411 < Ni+1
S
+ (1- -
where we use the facts that ni+1 S (1 3)n, and S eB in the final inequality.
Lemma B.2. Given some integer E [t 11, let i and E' be the number of insertions and deletions that have occurred since the last time U++1 was reconstructed respectively. Then we have that
74+1 +
R++1 + TR++1
1
+ 8
Proof. First, note that (M441 + (), + - E) < (M141 + ff/(m; - C). Now, given some reals A 2
a 2 and < I a, we define a function f: : [0. 1] + R by f(x) = (At
The derivative of f is -N(a
A 4 N)/((x 1)N + A)2 and is non-negative for all x [0. 1].
Hence, f(x) S /(1) for all x E [0, 1].
By setting A = T24 a m441. N & + l' and noting that E l' s TR++1 by Invariant 3.1 and M1+1 S 8)n, we get that
(+ l S T7,-1 & BBi+1 = (1 + 3)m++1 - 7:41 S (1 B)(1 - 3)m; R4+1 S n. - n4+1,
and hence it follows that
1++1 + E.
Ri41 + $((1)
ni+1 + TB++1
f E++
Since UU| U8, |,,1| (1 -)akk' [(k)) and 3 is constant, it follows from Lemma B. that O (log(UU) (k)))) = -(1).
B.2 Proof of Lemma 3.3
Bounding the Radii vs (Lemma B.5). Let UOLD denote the state the layer the last time reconstructed for i [t]. We now use the following crucial lemma which is analogous to Lemma
4.3.3 in [26].
Lemma B.3. Given any positive & there exists sufficiently large choice of a such that vs S 2μh (UPLD) ) for each E 1 with probability at least -ek!
Henceforth, we fix some positive and sufficiently large a such that Lemma B.3 holds.
Lemma B.4. Given metric subspaces Un and U2 of U such that U1 U2| S en(U1), we have that My (Un) < 2,py0 (U2).
S denotes symmetric difference,, i.e. U1 @ U2 (U1 101)U2) V.).
14

---

Proof. Let X be subset of U2 of size &o such that (3((+2))(XU3)) = (T(1+2)(U2), P = (x()+2)(U2), and A = Bu; (X, p). Now note that
IA = BB,, (X, Busu (X, p)1
2 (X, [BuSy (X)
2 7(1 + 2c) - -U2 Unl
2 + 2c) cy(Uil
2 + [[Ui] 1 ey(Uil) eq|Uil
+ ey(1 10(1->(1 2c)
2 7/11l-
Since there also exists a subset Y C A of size &o such that A S Bv, (Y it follows that (Y,YU1) < 2p. Hence, (,((1) & (Y, U1) & (V))
Lemma B.5. vs S (U:) each
with probability at least Ckk
Proof. For each i E [t 1]. U, @ U < T | since, by Invariant 3.1, at most 7 7|U points have been inserted or deleted from Ug since was last reconstructed. Noticing that T S E7, we can that
U U I eylUp
By now applying Lemma B.4 it follows that Hey (U,U)) S 2 (U:). The lemma follows by combin- ing this result with Lemma B.3.
Upper Bounding cost(a) (Lemma B.6). Lemma B.6.
cost(a) Σ Cz.
Proof. We first note that for all i E [t 1]. cost(a, C₁) < 2v,[C,]. This follows directly from the fact that each point x in C₁ assigned to some point y E C; such that d(x, I 214. Since the C, partition U and cost(a, C.) = O, get:
cost(o) Σ cost(o, Ci) < Σ 2v/Cal.
Lower Bounding (U)(U) (Lemma B.10). Let r denote [log] g 1-7" and for each E [t] let pa denote (U+))
For the rest of this subsection we fix an arbitrary S C of size k. For each i E [1] let F; denote the set (xr U, d(x,, 5) > p4), and for any integer
0, let F. denote F; (Uizo (U)zoFitjm) and
Gi. denote the set of all integers E [t] and j = i (mod m).
Lemma B.7. Given some E [t] and a subset C Fg we have that [F.] 2 (1 - and cost(S, 2 P.
Proof. It follows directly from the definition of μ4s that we have that F 2 (1 ---7"11 7 Ull.
By the
definition of F,, we have that cost(S, Exex d(z, 2 p.|
The following lemma is proven in [26].
Lemma B.8 ([26), Lemma 4.3.8). Given integers & [t] and m > O, we have that
cost(S, UIEG, F.T
Σ
n. Fm
iEGz.m
Lemma B.9. For all i E 1]. we have that FF
F.
15

---

Proof. We first note that for all i [t r], we have that |Pttl S 3 that
Frl. This follows from the fact
(1- 8r)
Fitrl |U - (1 3-y-1 - 1 y- F F.
where the first inequality follows from the fact that Fi+r S Uptr the second inequality follows from Lemma B. the third inequality follows from Lemma B.7, and the fourth inequality follows from the definition of r. We now get that
1
PP |P, Ujsofitorl 2 |B
j>0
Lemma B.10.
1-
cost(S) 2
us
C.l.
2r
Proof. Let l arg maxoster (EiEGer M4l PTlF
Then we have that
cost(S) 2 cost(S, UiEGe, FT)
E
1 2r
m|Fi
iEGer
1 1-7
U
2r
2r
The second inequality follows from Lemma B.8, the third inequality from averaging and the choice of f, the fourth inequality from Lemma B.9, and the fifth inequality from Lemma B.7
Proof of Lemma 3.3. follows that with probability at least
-ek we have that
cost(a) S
20/|Ci S Σ Sui/Cal S
1- cost(S)
16r
1
for any set S C U of size k. Hence, have that
16r
cost(o) S 1 1- opt(U).
C Proof of Corollary 3.4
In order to prove this corollary, we apply the extraction technique presented in [28] (with full details appearing in [26]) which a slight generalization of the techniques from [19]. In particular, we the following theorem which follows as an immediate corollary of Theorem in [26]. For completeness, we provide a proof of this theorem.
Theorem C.1. Given d-approximate m-assignment т - U, any d-approximate solution to the weighted k-median instance ( (U),, d, w). where each point x E TU)) receives weight w(x) = j (x)), is also (Ø + 2(1 6) approximate solution to the k-median instance (U, d).
Proof. Let S* be a solution to the weighted k-median instance (T(),, d, w) and let S be an optimal solution the k-median instance (U, d). Let ó and & be constants such that cost U) s d-opt(U) and cost... (S*, (U)) & vo opt,, (T()) We now show that cost(S*, U) = O(1) opt(U). We first note that
cost (S* ,U))=== = Σ d(z,
zEU
Σ d(x, π (x))(())))))))))) + Σ w(y) d(y,
zEu
VE+(U)
cost(T, U) + (S" (S,
< Φ opto()) + cost, (St, (U)).
16

---

Now note that, for any X S U of size at most k2 there exists some Y C (U)) of size at most k such that cost,, (Y, f cost, TT (U)). (X, Since co " xU)) I , (U)) for
all Y C (Y) of size at most k we get the following.
cost (S i(U)) S 2 cost ( (U))
2
Σ
w(y) d(y.
VER(U)
2
Σ d(<(()),
NEU
$ 2 Σ
d(x, π7 (x)) + 2/h Σ d(x,S)
aet
aet
2xh cost( n. U) + 2 opt(UU)
2(1 Φ) opt(U).
By combining these two chains of incqualities, we get that
cost(( ,U) s Φ oU)(U) cost (5", xTU)) < (6b + 2(1 + +)))) opt(U).
immediately follows that we can get a static weighted k-median algorithm on the instance (o(U), dd, w)
solution to the instance (U, by running
D Lower Bounds on Update and Query Time
In the static (i.e. non-dynamic) setting, the k-median problem is defined as follows: given metric space U, return set at most points from U which minimizes the value of > d(x, S). The following lower bound for the static k-median problem is proven by Mettu in [26].
Theorem D.I. Any app-apppo randomized (static) algorithm for the k-median problem, which succeeds with even negligible probability, runs in time ((nk).
Informally, the proof of this lower bound is obtained by constructing, for each 5 > 0, an input distribution of metric spaces (with polynomially bounded aspect ratio) on which no deterministic algorithm for the k-median problem succeeds with probability more than 5. Theorem D.1 then follows by application of Yao's minmax principle.
We can use this lower bound from the static setting in order to get a lower bound for the dynamic setting. First note that any incremental algorithm for k-median with amortized update time unn k) and query time qn,, k)) can be used to construct a static algorithm for the i-mmddian problem with running time u(n, k) + q(n, k)) by inserting each point in the input metric space U followed by a solution query. Hence, by Theorem D.1, we must have that n u(n, k) + q(n, k) = Q(nk). Now assume that some incremental algorithm for k-median has query time (pply(k)). If this algorithm also has an amortized update time ö(k), then for the range of values of & where qn, k) ō(nk). it follows that o(nk) is ((nk), giving contradiction. Hence, the amortized update time must be ②(k) and Theorem D.2 follows.
Theorem D.2. Any O(1) aaprxxppoe incremental algorithm for the k-median problem with (k)) query time must have Q((k) amortized update time.
It follows that the update time of our algorithm is optimal up to polylogarithmic factors.
17

---

E
Omitted Experimental Results
E.1
Update Time Evaluation
Total Update Time (sec)
Total Update Time (sec) (song. K 501
101
10
1-
10"1
20
10ah
OurA 9010
OurAlget 590)
HKlp 10201
Hilii 1000)
2500
5000
7500
10000
12500
15000
17500
20000
2500
5000
7500
10000
12500
15000
17500
20009
Upcasss
Updales
TRotal Update Time [sec] (song, k 100)
102
10'
10.1
OurAkgelg HK0p - 1.000
Figure 2: The cumulative update time for the different algorithms, on the Song dataset for A: = 10 (top left), k = 50 (top right), & 100 (bottom).
"Iotal Update Time (sec) (census,
Total Update Time
50)
10a
1.4
101
151
10-1
10*
10-1
10
DunA golg 5500 500)
OurAigeu--500 505)
HKjp 1020)
Hilip 1000)
2500
5000
7500
10000
12500
15000
17500
20000
2500
5000
75000
10000
12500
15000
17500
20200
Updines
Updasees
Total Update Time (sec) (census, k 100)
10-1
10-1
10-4
OurrMpel
1900pm 100000
125.0
15:00
37530
Figure 3: The cumulative update time for different algorithms, on the Census dataset for t: 10 (top left), k = 50 (top right), A: 100 (bottom).
18

---

Total Update Time (sec) Ikdiccp, K 10)
Total Update Time isec) (kddcup, k 50)
10a
10
104
127
10-3
30-1
Ourligeeg
11Kpp 1000)
1800 1000)
Updates
Updatess
Update (kddrup,
101
107
OurAkge 593)
HKk 1000)
2500
5000
7500
10303
12520
15:00
375.0
20005
Updates
Figure 4: The cumulative update time for the different algorithms, on the KDD-Cup dataset for k 10 (top left), 50 (top right), &t 100 (bottom).
Total Update Time (sed) idrit, k 10)
Total Update Time (sec) (dittt, 50)
107
301
1.2
201
100
10
Ourliporg
HKig 10201
1800p 10000
Ubdatess
Updates
Update
10-3
10-1
OurAlge 593)
Hil 1000)
2530
5200
7500
10003 Updates
12530
15300
375.0
20203
Figure 5: The cumulative update time for the different algorithms, on the Drift dataset for & = 10 (top left), is 50 (top right), & 100 (bottom).
19

---

Total Update Time (sec) IsiR:O0M, km 100
Total Update Time (sec) (siit10M, km 50)
109
104
107
10"
10"
10
10t4
Ourligeeg
11Kpp 1000)
1800 1000)
Updates
Updatees
Update (sift] 10M,
10-3
10 1.
OurAkge 593)
HKl 10000
2500
5000
7500
10303
12520
15:00
375.0
20305
Updates
Figure 6: The cumulative update time for the different algorithms, on the SIFT1OM dataset for k 10 (top left), 50 (top right), &o 100 (bottom).
E.2
Solution Cost Evaluation
Cost Solution (song, k - 10)
Cost of Solution (song, k 50)
3.0-
2.5
2.0
1.5
3.0-
OurRipale HRlg - 1000)
3.5
Ounligal
HKis 1000))
12503
dodatis
of (song.
2.5
05
OurAlgll 500)
0.-
2500
5000
7500
12000
52500
15000
37500
20300
Updates
Figure 7: The solution cost by the different algorithms, on Song for A = 10 (top left), k = 50 (top right), & 100 (bottom).
20

---

Cost Solution Icensus, k 10:
Cost of Soluutin Icensus, k 50)
19300
15000
10203
10030
5020
2303
OurMgnig
116g 1000)
1KKgy-1000) 10000
18083
14000
6300
4000
2003
OutAlyoip- 500)
0
Hkiy 1096)
2500
5003
7500
10000
12500
15003
17500
20003
Upsates
Figure 8: The solution cost by the different algorithms, on Census for = 10 (top left), k = 50 (top right), & 100 (bottom).
Cost Solution (kdidcup, k 10)
Cost of Solution (kddcup, k 50)
23000
Ourdipate
7020
OurAlyolp 5000 Hilip 10001
Am
6000
5000
15030
4000
3000
of (kddcupp
DurAlpot
160gg
4030
3000
0
2500
5030
7503
10503
12500
15203
17500
20203
Upsiites
Figure 9: The solution cost by the different algorithms, on KDD-Cup for k = 10 (top left), k 50 (top right). & 100 (bottom).
21

---

Cost of Solution (drift, k 10)
Cost Solution (drrit, k 50)
5001
OurAlget@ 500)
3.0
H40g
Cost Solution (dríft, 100)
OurAkge 503)
25-
-0000-1000)
20
15-
10
05-
0.
2500
5000
7500
19000
12500
150000
17500
20000
Updates
Figure 10: The solution cost by the different algorithms, on Drift for A: = 10 (top left), k = 50 (top right), & 100 (bottom).
Cost of Solution (sittIOM, k 10)
Cost of Solution (sirt00, k 50)
502000
600002
502020
103030
420000
300030
200030
Ounlppo 10000
Ourligzld [K0y 1000))
Updaxes
Updatess
of (sif
703000
403030
503030
103000
Cust (ilkigidd-000
1002)
2500
5050
7500
15020
12500
15000 17500 20000
Updates
Figure 11: The solution cost by the different algorithms, on SIFT10M for A = 10 (top left), k = 50 (top right). & 100 (bottom).
22

---

E.3 Query Time Evaluation
Table 4: The average query times for the algorithm OURALG(Ø 500) and HK(2 1000) (we omit the parameter value from the table to simplify the presentation), on the different datasets that we consider and for k {10, 50, 1003.
Song
Census
KDD-Cup
Drift
SIFT10M
OURALG
HK
OURALG
HK
OURALG
HK
OURALG
HK
OURALG
HK
k 10
0.569
0.327
0.478
0.280
0.069
0.176
0.729
0.421
0.732
0.419
& 50
0.610
0.347
0.511
0.295
0.075
0.141
0.784
0.447
0.795
0.448
& 100
0.665
0.373
0.552
0.317
0.085
0.131
0.857
0.483
0.866
0.483
E.4 Parameter Tuning
E.4.1 Update Time
Total Update Time (sec) Isong, = 50)
Total Update Time (sec) Icensus, k 50)
30a
10a2
10-2
DurAigst - 230)
OurAlger - 250)
10
CurAigole - 500)
10-4
GurAlger 500)
HKGpp #Rip-3001
HMX 1000)
HKigp 1000)
Update (sec) (kddcup, 50)
10
30
OutAlppr 10001
HGy- 2501
10
Hoy 500)
3000
2009
3000
4000
5003
6000
Upcatess
Figure 12: The cumulative update time for different parameters of OURALG and HK, for k = 50, on datasets Song (top left), Census (top right), and KDD-Cup (bottom).
23

---

E.4.2 Solution Cost
Cost Solution
Cost Solution
35
37503
3.0
13003
25-
12503
2.0
10302
7302
Oustigoli
Ou/lgpol -50)
1.9
Ounligolé 19030
5202
Ou/lige/ 1000)
HKly 2501
1MRp-2233 250)
0.5
Hill 5201
2509
HH 500)
0.0
10001
1000
2000
3000
4000
5000
0000
1000
2000
3000
4000
5000
0000
Upcates
Cost Solution (kddcupp k 50)
Outhlgec p 2525
OunAlges
0303
HGl
p10pp
H1lpp 1003)
4300
2003
2050
Figure 13: The solution cost for different parameters of OURALe and HK, for k: 50, datasets Song (top left), Census (top right), and KDD-Cup (bottom).
E.4.3 Query Time
Table The average query times for the algorithm OURALG and HK with different parameters, on the different datasets for k 50.
Song
Census
KDD-Cup
HK (1b 250)
0.026
0.021
0.012
HK 1b 500)
0.087
0.073
0.043
HK ( 1000)
0.293
0.249
0.156
OURALG 250)
0.223
0.187
0.054
OURALG 500)
0.439
0.364
0.086
OURALG( Ø 1000)
0.719
0.605
0.146
24

---

E,5
Randomized Order of Updates
E.5.1
Update Time
Total Update Time (9ec) (sang,
Total Update Time (sec) (cenous, 50)
12a
100
12"
1019
Outhiger
10
OurAlgold - 1000)
CurAlgole 500)
OurAlgor 1000)
9 500)
HMP 256
HKip- 2591
10m0
10-4
1000)
1000
2000
2000 Ioderio
4.000
5000
6000
1000
2005
3000 Uptates
4000
5002
6000
Total Update Time (Sec) (kddcup,
50)
102
105
10
Ounklpe 254)
10-1
Ounklpec
Outhlpec
Hdly
Hdy 5001
H10p 1003)
3000
3002
Figure 14: The cumulative update time for different parameters of OURALG and HK, for = 50, over sequence of updates given by randomized order of the points in the dataset, on the datasets Song (top left), Census (top right), and KDD-Cup (bottom).
E.5.2
Solution Cost
Cost of Solution (song, k 50)
Cost of Solution Ecensus, k 50)
3.5
17500
3.0
13000
12500
2.9
10003
1.5
Duskigsld - 2301
7500
Dusiigole 220)
Ousligole 5001
Ou 5500
1.0
Ourtigole 1903)
HK0p=2001
0.5
5201
0.0
HKTs 1000
p 10001
Solution (kddcup.
6003
4003
Bunk gote Ounk golle 10000
2003
HKig 203)
[Kip- 502)
1000
2000
3000
4000
5003
6000
Uptaasss
Figure 15: The solution cost for different parameters of OURALG and HK, for k 50, over sequence updates given by a randomized order of the points the dataset, on the datasets Song (top left), Census (top right), and KDD-Cup (bottom).
25

---

E.5.3
Query Time
Table 6: The average query times for the algorithm OURALG and HK with different parameters, for A = 50, over sequence of updates given by randomized order of the points in each of the datasets that we consider.
Song
Census
KDD-Cup
HK 6 250)
0.025
0,021
0.014
HK 0 500)
0.086
0.073
0.050
HK = 1000)
0.292
0.247
0.173
OURALG 250)
0.225
0.185
0.062
OURALG 500)
0.440
0.364
0.100
OURALG 1000)
0.723
0.605
0.165
E.6 Larger Experiment
Update (kddcup,
10a
10-
10
10-2
OunAlgo - 500)
HKly 1000)
25000
50000
75000
125000 150000 175000 200000 Updates
100000
Figure 16: The total update time for OURALG(Ø- = 500) and (K( 1000), on the larger instance derived from KDD-Cup, for 50.
Cost of Solution (kddcup, k 50)
20000
5000
2500
OurAlgold 500)
HKlp 1000)
75000 100000
Updates
Figure 17:
The solution cost produced by OURALG 500) and HK(1) 1000) two algorithms, on the larger instance derived from KDD-Cup, for k = 50.
The average query times for OURALG(ò = 500) and HK( = 1000) while handling this longer sequence of updates were 0.416 and 0.225 respectively.
26


Reviews:
[{"review_id": "XUeMaI9Jw6", "reviewer": "Reviewer_wnsQ", "summary": "This paper considers the dynamic version of the $k$-median and the $k$-means clustering problem in an arbitrary metric space. The authors provide an $O(k)$ amortized time (which is near optimal based on a lower bound that the authors provide) for insertions and deletions of points and a query time of $O(k^2)$. This is an improvement of the recent result by Henzinger and Kale, ESA 2020 which provided a dynamic algorithm with a worst case $O(k^2)$ update time. The algorithm in this paper is based on making the algorithm of Mettu and Plaxton dynamic. The authors also provide implementations of their algorithm as well as prior works (including a coreset construction algorithm) and then provide an empirical performance analysis of these algorithms.", "questions": "My questions were answered in a previous review cycle", "limitations": "NA", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "This paper is providing a near-optimal bound for amortized update time for dynamic k-means and k-median clustering problems.\n\n The authors provide implementations of their algorithm as well as prior works which is very useful.\n", "weaknesses": "In terms of techniques, the methods used are adaptation of an existing algorithm of Mettu and Plaxton and perhaps somewhat incremental in nature.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their effort and the review. \n\nWe agree that we extend the Mettu-Plaxton algorithm to the dynamic setting. We believe this to be an important contribution, since our algorithm is simple and practical to implement, and improves upon the prior bound for this fundamental clustering problem in the dynamic setting."}, {"review_id": "wLWKRl4Ptc", "reviewer": "Reviewer_REqo", "summary": "Fully dynamic k-clustering in O(k) update time\n\nThis paper studies fully dynamic k-clustering. It gives a fully dynamic algorithm that maintains O(1)-approximate solutions to k-median and k-means with \\tilde O(k) amortized update time and \\tilde O(k^2) worst-case query time. On the negative side, the authors showed that the Omega(k) amortized update time is required if one needs to achieve O(1)-approximation ratio and poly(k) query time. So they gave the optimal update time, and the time improves the prior best-known update time of O(k^2).  The authors also did experiments to complement the theoretical analysis. \n\nThe dynamic algorithm is built on the static algorithm of [27]. It runs for many iterations. In each iteration i, the algorithm samples a set S_i of points and creates a set of smallest-radius balls around the samples so that the balls cover at least beta fraction of the remaining points, for a constant beta. The algorithm then removes the covered points and repeats the process.  This gives a partition of the points into \\tilde O(k) balls. They construct an assignment that maps every point to its ball center. Then a k-median or k-means solution can be constructed using the centers only. \n\nThe dynamic algorithm maintains the tree-structure constructed in the static algorithm in a lazy manner by allowing some slack at many places. It needs to rebuild the tree from some layer if the cost of the assignment at that layer or above becomes bad. On average, it needs many updates for the algorithm to rebuild a tree from some layer, giving a good amortized update time. \n\n", "questions": "1. Can you give a rough bound on the approximation ratio of the algorithm?\n\n2. What happens if each update contains a batch of p points? Can you achieve an update time of O(p + k), instead of O(pk)? ", "limitations": "No limitations.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "Overall, the paper gives a tight update time of \\tilde O(k) for the fully dynamic k-clustering problem, using elegant techniques. This is a solid accept.  ", "weaknesses": "The hidden approximation ratio is a little big. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their effort and the review. \n\nQ1: The approximation ratio of our algorithm is (very close to) a factor $4$ off the approximation ratio of the static algorithm by Mettu-Plaxton. This is about $83 + 168\\alpha$, where $\\alpha$ is the approximation ratio of the static algorithm used to handle queries. However, we observe in our experiments that the quality of the solution returned by our algorithm is significantly better than the one predicted by the analysis.\n\nQ2: There is an existing lower bound which asserts that for any $k$, a constant approximate k-median algorithm takes $\\Omega(nk)$ time in the static setting. If our dynamic algorithm could handle an update consisting of a batch of $p$ points in $o(pk)$ time, then this would imply the existence of a static algorithm that runs in $o(nk) + O(k^2)$ time (by passing all the n points to the dynamic algorithm in one batch and making a query). In the event that $k = o(n)$, this leads to a contradiction. Hence, any constant approximate dynamic algorithm must take $\\Omega(pk)$ time to handle a batch update consisting of $p$ points (as long as the query time is polynomial in $k$). \n"}, {"review_id": "4bBKPIbSUG", "reviewer": "Reviewer_nK4h", "summary": "This paper studies the $k$-median/means problems in fully dynamic settings. Clustering in fully dynamic setting is a recent hot topic, where fully dynamic $k$-center has been well studied in literature. However, little was known for fully dynamic $k$-median/means problems. Inspired by the static framework proposed by Mettu and Plaxton, where a minimum radius ball coverage strategy is used to obtain $t=O(logn)$ layers of representations for good approximation of the given $k$-median/means instance. This paper modifies the classic framework by Mettu and Plaxton and presents an $O(1)$-approximation algorithm for the fully dynamic $k$-median/means problems with $\\tilde{O}(k)$ amortized update time and $\\tilde{O}(k^2)$ worst case query time, which improves the previous coreset-based method with $\\tilde{O}(k^2)$ worst case update time. ", "questions": "1. In each insertion, why should the data point to be inserted added to each layer $i \\in [t]$ instead of one of the $t$ layers?\n\n2. Can the authors discuss the challenges for applying the Mettu's and Plaxton's method for solving the fully dynamic $k$-clustering problems?\n\n\n\n", "limitations": "Since this is a theoretical paper, I don't think there is potential negative societal impact of this paper.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. This paper proposes simple but efficient approximation algorithm for the fully dynamic $k$-median/means problems with $\\tilde{O}(k)$ amortized update time and $\\tilde{O}(k^2)$ worst case query time, which improves the previous result with $\\tilde{O}(k^2)$ update time and $\\tilde{O}(k^2)$ query time. The authors also show that the update time of our algorithm is optimal up to polylogarithmic factors.\n\n2. This paper gives detailed experimental evaluation of fully dynamic k-median algorithms for general metrics and shows that the proposed framework is more efficient than previous ones.", "weaknesses": "1. The techniques used in this paper seem to rely heavily on the minimum ball coverage method by Mettu and Plaxton. \n\n2. The challenges for obtaining good update time and query time is not well discussed.\n\n3. The theoretical analysis is not an easy read in a limited time. The intuition behind the analysis and algorithm before going into the details of lemmas and proofs should be given before the proofs. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their effort and the review. \n\nRegarding the challenges behind getting our result: Typically, the first challenge towards designing a dynamic algorithm for a given problem is to identify a suitable static algorithm which is flexible enough that it can be adapted to the dynamic setting. This is emphasised in line 83 (and the paragraph preceding it), where we explain that the static algorithm that we build upon is completely different from prior work. Next, even after identifying the Mettu-Plaxton algorithm as our starting point, we have to note that simply following a strategy of corresponding to the output of the static algorithm at every time-step will lead to very large update time. To circumvent this difficulty, we have to suitably modify the Mettu-Plaxton algorithm so that it lazily waits until it accumulates sufficiently many updates at some layer $j$, and then reconstructs all the layers $i \\geq j$. Thus, we need to be lazy in a ``fine-grained’’ manner. We cannot simply say that we wait for a certain period of time, and then run the static algorithm again from scratch on the whole input. We will clarify this point in the final version.\n\nRegarding handling an insertion: Note that the layers are nested within one another (see line 4 of Algorithm 1). Thus, if we add the point $x$ being inserted to layer $U_i$, then we must add it to all layers $j \\leq i$. Now, one might ask why can’t we just add the point $x$ only to $U_1$ and be done with it? The reason is this: Then necessarily $x$ will become part of the set $C_1$ (see line 4 of Algorithm 1), but there will be no guarantee that this point $x$ in $C_1$ is covered by some ball of radius $\\nu_1$ around $S_1$ (see lines 124 - 131).\n\nRegarding the presentation in the paper: In Section 3.1, we described the static algorithm by Mettu-Plaxton, which was our starting point. In Section 3.2, we provided some intuitions regarding the modifications we need to make in order to make it dynamic (see lines 169 - 172), and along with it described concretely the dynamic algorithm. For space constraints, we had to defer the complete proofs for the analysis to the appendix."}, {"review_id": "ysNJKizvsI", "reviewer": "Reviewer_f4hU", "summary": "This paper studies dynamic algorithms for k-median (and k-means) in general metrics. The main result is an \\tilde{O}(k) update time, poly(k) query time algorithm that achieves O(1)-approximation. Here, the update model is point insertion/deletion, and the algorithm has access to the distance oracle. A query operation asks to return a list of k points that is O(1)-approximate.\n\nThe result improves over the k^2 update time achieved in HK20. This is achieved using a somewhat different but more direct approach. In particular, in HK20, a general reduction to coreset via merge-and-reduce framework was employed, but this work employs a direct dynamization of MP04.\n\nComprehensive experiments are also provided. Compared with HK20 as a baseline, the new algorithm runs faster and achieves an overall better accuracy. ", "questions": "- The first paragraph of \"our techniques\" tried to explain why HK20 has k^2 dependence, but it's not very clear. Here, the black-box coreset is linear in k, and the depth of the binary tree is O(log n). Then how come we have another k factor?\n- Followup of the above question: is it true that HK20 relies on a bi-criteria solution? Is that part constitute the bottleneck? Also, does HK20 give bi-criteria solution whose update time is near-linear in k? If so, then maybe it's also an interesting angle to compare with their result, since yours may be viewed as a (strict) improvement of it.\n- In the end of Sec 1, it is mentioned that an algorithm for weighted k-median is presented in Sec 2. But I didn't find it\n- In Sec 3.1, it seems the algorithm only returns a bi-criteria solution. What's the procedure for making it a real feasible solution? How does that procedure affects the final time complexity?", "limitations": "I didn't find these explicitly discussed. A discussion of limitations, and possibly mentioning future directions, could be helpful. This paper is a theory paper and I don't see a potential negative societal impact.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper achieves near-linear in k update time, which is a nice improvement over the previous k^2\n- The experiments are convincing, and justify the theoretical improvement\n- A nearly-matching lower bound is provided", "weaknesses": "- This work only yields O(1)-approx, while HK20 uses coreset approach and hence can build an eps-coreset even for general metrics (even though it does not imply an efficient algorithm for finding a solution). This also means this work cannot be easily generalized to the Euclidean case, where near-linear time PTAS was known.\n- The query time is k^2, which may be improved", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their effort and the review.\n\nWeakness 1: We would like to point out here that in the HK20 result, if one wishes to ensure that $\\epsilon$ is small, then the resulting coreset has to be very large. For example, for the HK20 guarantee to hold with probability $½$ and $\\epsilon=1$, the size of the output coreset would need to be at least $3.3$ million points in size, when $n=2000$ and $k=100$. So in many real world scenarios, the HK20 algorithm would need a coreset that contains the full dataset, to have the concerned theoretical guarantees. \n\nWeakness 2: The ultimate goal in this line of research is to obtain a $O(1)$ approximate dynamic $k$-median algorithm with $\\tilde{O}(k)$ update time and $\\tilde{O}(k)$ query time. We made substantial progress towards this goal by bringing down the update time from $\\tilde{O}(k^2)$ to $\\tilde{O}(k)$. Bringing the query time down to $\\tilde{O}(k)$ remains a tantalising open question.\n\nQuestion 1: While the sizes of the corsets is $\\tilde{O}(k)$, the time taken to compute these coresets (on inputs of size $\\tilde{O}(k)$) is $\\tilde{O}(k^2)$, which is why the update time is $\\tilde{O}(k^2)$. This is because HK20 needs to recompute the coresets after each update, to ensure that the output is a valid coreset at all times.\n\nQuestion 2: Our focus on this paper has been to consider the original $k$-median problem, without any bi-criteria approximation. But it is true that we can also maintain a bicriteria approximation in $\\tilde{O}(k)$ update time. \n\nAlso, it is indeed the case that the bottleneck in the static coreset construction used by HK20 is the computation of a bi-criteria solution (while the rest of the coreset construction can be done in $\\tilde{O}(k)$ time), which is the reason why HK20 takes $\\tilde{\\Omega}(k^2)$ time to handle an update. While the output coreset of HK20 can also be viewed as a bi-criteria solution, it’s still not clear how this can be maintained in $o(k^2)$ update time using the HK20 framework.\n\nQuestion 3: We apologise for the confusion. We actually intended to cite the definition of the weighted k-median problem, not the algorithm. We use a weighted k-median algorithm as a black box, as described in the proof of Corollary 3.5. We will clarify this point in the final version.\n\nQuestion 4: This is answered in line 177 (towards the end of Section 3.1). In the final version of the paper, we will take this comment into account and make appropriate changes.\n\nLimitations: Thanks for pointing this out. In the final version of the paper, we will add a paragraph at the very end, pointing out the key, remaining open problem in this topic - namely, to get a constant approximate dynamic $k$-median algorithm with $\\tilde{O}(k)$ update time AND $\\tilde{O}(k)$ query time.\n"}]

Author rebuttal:

Meta-review: The paper is generally supported by the reviewers.

The strength of the submission is in improving the update time of an important dynamic clustering problem and the reviewers also appreciate the improved performance in many scenarios in the experiments. The new algorithm generally improves on the previous dynamic algorithm in both time and solution quality.

On the downside, the techniques are somewhat incremental in nature as it is a modification of an existing static algorithm. The theoretical approximation factor is very high compared with previous works so even though it performs well in the scenarios in the experiments, there could be other scenarios where it does not improve the previous works.
Decision: Accept (poster)