Near-Optimal $k$-Clustering in the Sliding Window Model
Authors: David Woodruff
Peilin Zhong
Samson Zhou
Venue: NeurIPS 2023 poster (2023)
Keywords: clustering
streaming algorithms
sliding window model

Abstract: Clustering is an important technique for identifying structural information in large-scale data analysis, where the underlying dataset may be too large to store. In many applications, recent data can provide more accurate information and thus older data past a certain time is expired. The sliding window model captures these desired properties and thus there has been substantial interest in clustering in the sliding window model. In this paper, we give the first algorithm that achieves near-optimal $(1+\varepsilon)$-approximation to $(k,z)$-clustering in the sliding window model. Our algorithm uses $\frac{k}{\min(\varepsilon^4,\varepsilon^{2+z})}\,\text{polylog}\frac{n\Delta}{\varepsilon}$ words of space when the points are from $[\Delta]^d$, thus significantly improving on works by Braverman et. al. (SODA 2016), Borassi et. al. (NeurIPS 2021), and Epasto et. al. (SODA 2022).

Along the way, we develop a data structure for clustering called an online coreset, which outputs a coreset not only for the end of a stream, but also for all prefixes of the stream. Our online coreset samples $\frac{k}{\min(\varepsilon^4,\varepsilon^{2+z})}\,\text{polylog}\frac{n\Delta}{\varepsilon}$ points from the stream. We then show that any online coreset requires $\Omega\left(\frac{k}{\varepsilon^2}\log n\right)$ samples, which shows a separation between the problem of constructing an offline coreset, i.e., constructing online coresets is strictly harder. Our results also extend to general metrics on $[\Delta]^d$ and are near-optimal in light of a $\Omega\left(\frac{k}{\varepsilon^{2+z}}\right)$ lower bound for the size of an offline coreset.

Near-Optimal h h--Cluttrring in the Sliding Window Model
David P. Woodruff
Peilin Zhong Google Research peilinzogoogle. com
Samson Zhou Texas A&M University
CMU
dwoodruf@cs. cmu, edu
samsonzhou@gmail. com
Abstract
Clustering is an important technique for identifying structural information in large- scale data analysis, where the underlying dataset may be too large to store. In many applications, recent data can provide more accurate information and thus older data past certain time is expired. The sliding window model captures these desired properties and thus there has been substantial interest in clustering in the sliding window model.
In this paper, we give the first algorithm that achieves near-optimal (1 + E) aapppoximationn to (k, cllusterin in the sliding window model, where z is the exponent of the distance function in the cost. Our algorithm uses 22 polylog words of space when the points are from [A] thus sig- nificantly improving on works by Braverman et. al. (SODA 2016), Borassi et. (NeurIPS 2021), and Epasto et. al. (SODA 2022).
Along the way, develop data structure for clustering called online coreset, which outputs a coreset not only for the end of stream, but also for all prefixes the stream. Our online coreset samples min(ef,221a) polylog nA points from the stream. We then show that any online coreset requires Ω ( log samples, which shows a separation from the problem of constructing constructing online coresets strictly harder. Our results also extend to general metrics on [A] d and are near-optimal in light of Ω size of an offline coreset.
offline coreset, i.e.,
k lower bound for the
Introduction
Clustering a fundamental procedure frequently used to help extract important structural information from large datasets. Informally, the goal of clustering partition the data into & clusters that the elements within each cluster have similar properties. Classic formulations of clustering include the k-median and k-means problems, which have been studied since the 1950's ssss [60, 50]. More generally, for a set X of n points in R along with a metric dist, a cluster parameter > 0, and an exponent > ( that positive integer, the clustering objective be defined
min CCR
Σ min dist (2), CEC
When dist is the Fuclidean distance, the problem is known (k, =--lusteenn and more specifically, k-median clustering and k-means clustering, when is additionally set to and 2, respectively.
As modern datasets have significantly increased in size, attention has shifted to large-scale compu- tational models, such as the streaming model of computation, that do not require multiple passes over the data. In the (insertion-only) streaming model, the points . En, of X arrive sequentially,
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

and the goal is to output an optimal or near-optimal clustering of X while using space sublinear in n, ideally space & polylog(n, d). since outputting the cluster centers uses words of space, where each word of space is assumed to be able to store an entire input point in Rd. There exist slight variants of the insertion-only streaming model and long line of active research has been conducted on clustering in these models [42, 21, 44, 43, 23, 17, 37, 39, 1, 11, 59, 46, 14, 27, 10, 25, 61, 29].
The sliding window model. Unfortunately, an important shortcoming of the streaming model is that it ignores the time at which a specific data point arrives and thus it is unable to prioritize recent data over older data. Consequently, the streaming model cannot capture applications in which recent data is more accurate and therefore considered more important than data that arrived prior to a certain time, e.g., Census data or financial markets. Indeed, it has been shown that for number of applications, the streaming model has inferior performance [4, 52, 57, 62] compared to the sliding window model [33], where only the most recent W updates in the stream comprise the underlying dataset. Here, W >> 0 is a parameter that designates the window size of the active data, so that all updates before the W most recent updates are considered expired, and the goal is to aggregate statistics about the active data using space sublinear in W. In the setting of clustering, where the data stream is 21, 21...., In C R" the active data set is X = {ain- (#n-W+1;---- W+1....., Fn for n 2 W and X- = (x1,..., In otherwise. Thus the sliding window model is generalization of the streaming model, depending on the choice of W. and is especially relevant for time-sensitive settings, such as data summarization [22, 34), event detection in social media [56], and network monitoring [32, 30J.
The sliding window model is especially relevant for applications in which computation must be restricted to data that arrived after certain time. Data privacy laws such as the General Data Protection Regulation (GDPR) mandate that companies cannot retain specific user data beyond a certain duration. For example, the Facebook data policy [36] states that user search histories are retained for months, the Apple differential privacy overvíew [3] states that collected user information is retained for 3 months, and the Google data retention policy states that browser information may be stored for up to months [41]. These retention polices can be modeled by the sliding window model with the corresponding setting of the window parameter W and thus the sliding window model has been subsequently studied in a wide range of applications [48, 49, 18, 19, 12, 13, 9, 20, 63, 2, 47, 7].
Clustering in the sliding window model. Because the clustering objective not well-suited to popular frameworks such as the exponential histogram or the smooth histogram, there has been significant interest in clustering in the sliding window model. We now describe the landscape of clustering algorithms in the sliding window model; these results are summarized in Table 1. In 2003, [5] first gave a 2011 approxxiiiooiiiaiiinn algorithm for k-median clustering in the sliding window model 2 log 2 W) words of space, where E (0, 1) is an input parameter. Subsequently, [15] gave an O (1) -approximate bicriteria algorithm using 2k centers and k² polylog (W) space for the k-median problem in the sliding window model. The question of whether there exists a poly(k (k log W) space algorithm for k-clustering on sliding windows remained open until [16] gave constant-factor approximation sliding window algorithms for k-median and k-means using O (k.3 log W) space and [28] gave constant-factor approximation algorithmss for k-center clustering using O (k log A) space, where A is the aspect ratio, i.e., the ratio of the largest to smallest distances between any pair of points. Afterwards, [8] gave a C-approximation algorithm for some constant C > 21d though it should be noted that their main contribution was the first constant-factor approximation algorithm for k-clustering using space linear in k. i.e., k polylog (W, A) space, and thus they did not attempt optimize the constant C. Recently, [35] gave the first (1 + ->-approximation algorithm
using O &
E
for (k, >)-cusstering using (kd+d polylog (W, A, 11) words of space, for some constant C > 7. Using known dimensionality reduction techniques, i.e., [51], the algorithm's 's dependence on de can be removed in exchange for ąा polylog (W; overhead. However, neither the dc dependency nor the 2 polylog (W, !) trade-off is desirable for realistic settings of d and E for applications of k-clustering on sliding windows. In particular, recent results have achieved efficient summarizations,
i.c., coresets, for k-median and k k-means clustering in the offline setting using Ô ( log words of space [27, 25] when the input is from [A] 1d and it is known that this is optiool i..., Ω (=+ log n) samples are necessary to form coresets for (k:, =)-clustering [45] in that setting. Thus a natural question is to ask whether such near-optimal space bounds can be achieved in the sliding window model.

---

1.1 Our Contributions
In this paper, we answer the question in the affirmative. That is, we give near-optimal space algorithms for k-median and k-means clustering in the sliding window model. In fact, we give more general algorithms for (k, clucstrrn in the sliding window that nearly match the space used by the offline coreset constructions of [27, 25, 26]:
Theorem 1.1. There exists an algorithm that samples min(e" s polylog ni points and with high
probubility, oulputs a (1 + appproxximaaionn to (ki, =)-cluttering for the Euclidean distance on [A] in the sliding window model.
In particular, our bounds in Theorem 1.1 achieve k polylog Dd words of space for k-median <i clustering and k-means clustering, i.e., and 2, respectively, matching the lower bounds of [25, 45] up to polylogarithmic factors.
Reference
Accuracy
Space
Setting
[S]
20(178)
O W log" W)
k-median, E (0.
[16]
C>
O (K3 log W)
k-median and k-means
[34]
C' 2
h polylog W A)
(k,
[35]
(1 + e)
polylog W. A, C2,C27
(k: =Blustcen
Our work
E1+
min(ef.e 3) polylog
(k, (k,2)-clustering
Table Summary of (ks, 2) cluuteriig results in the sliding window model for input points on a window of size W
[A]*
Moreover, our algorithm actually produces a coreset, i.e., data structure that approximately answers the clustering cost of the underlying dataset with respect to any set of l centers, not just the optimal k centers.
Theorem 1.2. There exists an algorithm that samples mim(e""_=** 2tay polylog nA points and with high probability, outputs (1 + e)-crret cllusttnn in the sliding window model for general metrics on [A]d.
We emphasize that the guarantees of Theorem 1.2 are for general metrics on [A]á, such as Lp metrics. Note that in light of the properties of coresets, the guarantee of Theorem 1.1 follows from taking a coreset for (k; =lccusttering on Euclidean distances and then using an offline algorithm for (k, 2) ccluusteini for post-procsssing after the data stream, i.c., see Theorem 2.4.
Along the way, we provide construction for (1+ -nnoiie coreset for (k, 2).z)=z >)-clustering for general metrics on [A]d. An online coreset for (k: 2) cluustreg a data structure on a data stream that will not only approximately answer the clustering cost of the underlying dataset with respect any of l centers, but also approximately answer the clustering cost of any prefix of the data stream with respect any set of l centers.
Theorem 1.3. There exists an algorithm that samples min(e" polylog DA points and with high probability, outputs a (1 + e)-olline coreset for (k, =)cluusteini
We remark that Theorem 1.3 further has the attractive property that once a point is sampled into the online coreset at some point in the stream, then the point irrevocably remains in the online coreset. That is, the online coreset essentially satisfies two different definitions online: 1) data structure is coreset for any prefix of the stream and 2) points sampled into the data structure will never be deleted from the data structure.
We further remark that due to leveraging the coreset construction of [27, 25, 26], we can similarly trade factor of ş= for a poly(k) in the guarantees of Theorem 1.1, Theorem 1.2, and Theorem 1.3.
By contrast, the lower bound by [25] states that any offline coreset construction for k-means clustering only requires 52 ( points. This lower bound was later strengthened Ω ( points by [45], for which matching upper bounds are given by [27, 25J. Thus our online coreset constructions are near-optimal in the and _ dependencies for z > and nearly match the best known offline constructions for 1.
3

---

It is thus natural question to ask whether our polylogarithmic overheads in Theorem 1.3 are necessary for an (1 + =n-oli coreset. We show that fact, logarithmic overhead indeed necessary to maintain a (1 + E) -online coreset.
Theorem 1.4. Let (0, 1). For sufficiently large d. and A. there exists set X [ of n points 21,-.., In such that any (1 + s)-online coreset for k-means clustering on X requires Q 22 logn) points.
We emphasize that combined with existing offline coreset constructions [25, 26], Theorem 1.4 shows a separation between the problems of constructing offline coresets and online coresets. That is, the problem of maintaining data structure that recovers coresets for all prefixes of the stream is provably harder than maintaining a coreset for an offline set of points.
1.2 Technical Overview
In this section, we give high-level overview of our techniques. We also describe the limitations of many natural approaches.
Shortcomings histograms and sensitivity sampling. A first attempt at clustering in the sliding window model might be to adapt the popular exponential histogram [33] and smooth histogram techniques [18]. These frameworks convert streaming algorithms to sliding window algorithms in the case that the objective function is smooth, which informally means that once suffix of a data stream becomes good approximation of the overall data stream, then it always remains a good approximation, regardless of the values of new elements that arrive in the stream. Unfortunately, [16] showed that the k-clustering objective function is not smooth and thus these histogram- based frameworks cannot work. Nevertheless, they gave the first constant-facte approximation by showing that the k-clustering objective function is almost-smooth using a generalized triangle inequality, which inherently loses constant factors and thus will not suffice for our goal of achieving (1 + e)- approximation.
Another approach might be to adapt the popular sensitivity sampling framework of coreset construc- tion [37, 39, 10, 29]. The sensitivity sampling framework assigns value to each point, called the sensitivity, which intuitively quantifies the "importance" of that point, and then samples each point with probability proportional to its sensitivity. [9] observed that sliding window algorithms can be achieved from online sensitivity sampling, where the importance of each point is measured against the prefix of the stream, and then running the process in reverse at each time, so that more emphasis is placed the suffix of the sliding window. At high level, this is the intuition taken by [34, 35], which leverage data structures that prioritize more recent elements the data stream. However, is not known how to achieve optimal bounds simply using sensitivity sampling, and indeed the optimal coreset constructions use slightly more nuanced sampling schemes [27, 25].
Sliding window algorithms from online coresets. Instead, we recall an observation by [9], who noted that deterministic constructions for online coresets for linear algebraic problems can be utilized obtain sliding window algorithms for the corresponding linear algebraic problems. We first extend this observation to randomized constructions for online coresets for k-clustering problem.
The intuition is quite simple. Given an (1 + e)-oniine coreset algorithm for k-clustering problem on data stream of length from Rdd that stores S(n, d, k, s, 5) weights points and succeeds with probability 1 1- we store the (1,,, d, ,', most recent points in the stream, where s' =0 log
and 8' poly(nj' We then feed the S(n, d, k,,",, ,')) points to the online coreset construction in reverse order of their arrival. Since the online coreset preserves all costs for all prefixes of its input, then the resulting data structure will preserve all costs for all suffixes of the data stream. To extend this guarantee to the entire stream, including the sliding window, we can then use a standard merge-and- reduce framework. It thus remains to devise a (1 + eo-oline coreset construction for k-clustering with near-optimal sampling complexity.
8
Online coreset construction. To that end, our options are quite limited, as to the best of our knowledge, the only offline coreset constructions using Ô ( log n) words of space when the input is from [ are due to [27, 25]. Fortunately, although the analyses of correctness for these sampling

---

schemes are quite involved, the constructions themselves are quite accessible. For example, [27] first uses an (a, 3) appproximmtionn i.e., clustering that achieves a-approximation to the optimal cost but uses 3k centers, to partition the underlying dataset X into disjoint concentric rings around each of the Ak centers. These rings are then gathered into groups and it is shown that by independently sampling a fixed number of points with replacement from each of the groups suffices to achieve s)correee... Their analysis argues that the contribution of each the groups toward the overall k-clustering cost is preserved through an expectation and variance bounding argument, and then taking a sophisticated union bound over a net over the set of possible centers. Thus their argument still holds when each point of the dataset is independently sampled by the data structure with probability proportional to the probability would have been sampled by the group. Moreover, independently sampling each point with higher probability can only decrease the variance, so that correctness is retained, though we must also upper bound the number of sampled points. Crucially, independently sampling each point be implemented in the online setting and the probability of correctness can be boosted to union bound over all times in the stream, which facilitates the construction of our (1 + en-oliee coreset, given (a, -pppoppooximtiion.
Consistent (a, approoxxxint,. clustering at all times in the stream. A natural approach would be to use an algorithm that achieves (a, B)-approximation at a certain time in the stream with constant probability, e.g., [59], boost the probability of success
seemingly remains to find (a, -)pppoooximtioons for k-
poly(n)' and the union bound argue correctness over all times in the stream. However, a subtle pitfall here is that the rings and groups in the offline coreset construction of [27] are with respect a point xe was assigned to cluster i at time when the sampling process occurs but then assigned to cluster i2 at the end of the stream. Therefore, we require a consistent (a, (.) -pppoooxximtninn, so that once the algorithm assigns point xy to cluster i, then the point x will always remain in cluster i even if newer and closer center is subsequently opened later in the stream. To that end, we invoke a result of [34] that analyzes the popular Meyerson online facility location algorithm, along with a standard guess-and-doutde approach for estimating the input parameter to the Meyerson subroutine.
specific (a,, (0) -approximation. Hence their analysis would no longer hold if
Lower bound. The intuition for our lower bound that any (1++)-online) coreset for (k, 2) cllustrrn requires Q (x) is somewhat straightforward and in a black- manner. We first observe that [25] showed the existence of set X of Ω (+) unit vectors in Rd such that any coreset with o ( ( samples provably cannot accurately estimate the (kt, z)-cluttering cost for a set C' of 1 unit vectors.
Since an online (1 + e)-coreset must answer queries on all prefixes of the stream, embed 2(lg n) instances of X. We first increase the dimension by a logn n factor so that each of these instances can have disjoint support. We then give each of the instances increasingly exponential weight to force the data structure to sample Ω
points for each instance. Specifically, we insert r' copies of some constant. Because the weight of the i-th instance is substantially greater than the sum of the weights of all previous instances, then any (1 + c)-olinne
the i-th instance of X, where т >
coreset must essentially be (1 + -ffofiie coreset for the i-th instance, thus requiring S2 ([² for the i-th instance. This reasoning extends to all 22log n.) instances, thus showing that any online (1 + #) corrsttt requires Q (# log n) points.
k points
2 Algorithm
In this section, we describe our sliding window algorithm for k-clustering. We first overview the construction of an online (1 +)) coreset for (k, z)-clustering under general discrete metrics. We then describe how online coresct construction for (A, =)-clustering general discrete metric spaces can be used to achieve near-optimal space algorithms for (k, 2) -cllstrrii in the sliding window model.
Online (1 + cocoeeet.. We first recall the following properties from the Meyerson sketch, which we formally introduce in Appendix A.
Theorem 2.1. [8] Given an input stream I1,..., J.n E Rdd defining a set X c [A], there exists an online algorithm MULTMEYERSON that with probability at least 1 poly(a)'
5

---

(1) on the arrival of each point 2,, assigns 2; to center in C' through mapping x X - C, where C contains at most 0 (2 log log A) centers
(2) ExEx I., - (x:))l 2 2 Costis sa(X.
(3) MULTMEYERSON uses (2 log (ndA)) words of space
We also use the following notation, adapted from [27] to the online setting.
Let A be (a, approxximmii for k-means clustering an input set X S [A] and let Ci....: Cas be the clusters X induced by A. Suppose the points of X arrive in a data stream For fixed >> 0, define the following notions of rings and groups:
The average cost of cluster C is denoted by sC; Cost(C
[Ci]
For any i,j. the ring Ra,j is the set of points E C₁ such that 2'cc, S Cxst <
"kc, 2/'1kc,- For any j. R2- = URa.--
2
The inner ring [C. Ujg2slog log & Bag the set points of C, with cost at most
(5) 2> KC, More generally for a solution S, let Ry denote the union of the inner rings induced by S.
The outer ring Ro(C;) = Uy22a Rag is the set of points of C with cost at least (3)2s RC,. More generally for a solution S, let Ro denote the union of the outer rings induced by S.
The main ring (M((C)) ) is the set of points of C; that are not in the inner or outer rings, i.e., (C, C; (C,) U (C;)
For any j. the group G₁,, consists of the (2h-1 + 1)-th (2*)-th points of each ring R..j that arrive in S.
For any j. we use Gj,min to denote the union of the groups with the smallest costs, i.c.,
Cost (Rj. A)
Gjmin-
E Ray Cost A) < 4z
Bk
The outer groups G8 partition the outer rings Ry that
G. = a
(
3k Cost (RO, Ad.A) 2 I .)) <
( {=)
Cost (R..A) A)
2 22-11
42
4=
3k
We define Go UbsoGD and Go
Up> log 12 Go.
Algorithm 1 RINGSAMPLE
Input:
Points 31, -1,..., Tn E [A]d
Output: A set W of weighted points and timestamps
I: Initiate an instance of (a, B)bbirriteria algorithm MULTMEYERSON
2: 7 <- Cmax(a²,a log2 (k: log [C] + log log _ + log m) log²
3: W + (
4:
for each point 2r, t [n] do
5: Let q be the center assigned for v, by MULTMEYERSON
6:
Let S ||,, callă 2/+1 for j E E
7:
Let b E Z that the number of points in R2 between 2 + 1 and 2
8:
Let be the number of points in Gj,b at time t
9:
Ps - min
A - n,
10:
With probability Pa. add x to W with timestamp t and weight 1
p.
11:
return W
We then adapt the offline coreset construction of [27] an online setting at the cost of logarithmic overheads, which suffice for our purpose. The algorithm (Algorithm has the following guarantees:

---

Lemma 2.2. Let C be an A-approximatte centroid set for a fixed group G. There exists algorithm RINGSAMPLE that samples
max(a², a² log² log |C| log log min(c2, EE)
1 ε
log log" n log A Alog log² :)
points and with high probability, outputs (1 -n-line coreset for the k-means clustering problem.
Informally, an approximate centroid set is of possible points so that taking the centers from this set generates an approximately accurate solution (see Appendix B for formal definition). To bound log [C], we construct and apply terminal embedding to project each point lower dimension and then appeal to known bounds for approximate centroid sets in -ww-dmmnniioall Euclidean, thereby giving our online coreset algorithm with the guarantees of Theorem 1.3.
Sliding window model. We first recall a standard approach for using offline coreset constructions for insertion-only streaming algorithms. Suppose there exists randomized algorithm that produces an online coreset algorithm that uses S(n, E, points for an input stream of length n, accuracy e, and failure probability 5, where for the case of discussion, standard approach for using coresets on insertion-only streams is the merge-and-reduce approach,
omit additional dependencies. A
which partitions the stream into blocks of size S (n, e
2logn' (nly(n) and builds a coreset for each block. Each coreset is then viewed as the leaves of a binary tree with height at most log n, since the binary tree has at most n leaves. Then at each level the binary tree, for each node in the level, a coreset of size S n, n poly(n) is built from the coresets representing the two children of the node. Due to the mergeability property of coresets, the coreset at the root of the tree will be a coreset log
for the entire stream with accuracy
(1 2
(1+ and failure probability 5.
This approach fails for sliding window algorithms because the elements at the beginning of the data stream can expire, and so coresets corresponding to earlier blocks of the stream may no longer accurate, which would result in the coreset at the root of the tree also no longer being accurate. On the
other hand, suppose we partition the stream into blocks consisting of S T1, Flog poly(n) elements as before, but instead of creating offline coreset for each block, for the elements in reverse. That is, since the elements in each block are explicitly stored, we can create offline artificial stream consisting of the elements in the block in reverse and then give the artificial stream as input to the online coreset construction. Note that we also first consider the "latter" coreset when merging two coresets, then this effectively reverses the stream. Moreover, by the correctness of the online coreset, our data structure provides correctness over any prefix of the reversed stream, or equivalently, any suffix of the stream and specifically, correctness over the sliding window. We thus further adapt the merge-and-reduce framework to show that randomized online coresets for problems in clustering can also be used to achieve randomized algorithms for the corresponding problems in the sliding window model. We formalize this approach in Algorithm 2.
create online coreset
......,,2 En be stream of points in [A] = O, and let X (In-W+1, ..... In, be the W most recent points. Suppose there exists a randomized algorithm that with probability at least 1 -- ô, oulputs an online coresel algorithm for a k-clastering problem with S(n, k,,, 8) points. Then there exists a randomized algorithm that with probability at least 5, oulputs a coreset for logn) points.
Theorem 2.3. Let I1,..... .........
the k-clustering problem in the sliding window model with O (s (n, m, k, logn n²
By Theorem 1.3 and Theorem 2.3, we have:
Theorem 2.4. There exists an algorithm that samples minte" .=t+, polylog aA points and with high probability, outputs a (1 + =)-oorestt to (ki 2)-ccutteiing in the sliding window model.
Using an offline algorithm for (k, =eclustern for post-processing after the data stream, we have Theorem 1.1.
3 Experimental Evaluations
In this section, we conduct simple empirical demonstrations as proof-of-concepts to illustrate the benefits of our algorithm. Our empirical evaluations were conducted using Python 3.10 using 64-bit
7

---

Merge-and-reduce framework for randomized algorithms in the sliding window model, using randomized constructions of online coresets
Algorithm 2
Merge-ande
Input:
A clustering function f. set of points 21,..., S R. accuracy parameter > 0, failure probability 8 (0, 1), and window size W >
Output: An approximation of f on the W most recent points
Let CORESET(X, n, d, k, E, 6) be an online coreset construction with S(n, d, k. e, points on
set X C IRd
= 6 log 2: m 0 (n, d. ki logn'
3: Initialize blocks Bo, BI..... Biog f
4: for each point 2, with & E [n] do
5: if Bg does not contain m points then
6: Prepend xe to Bu, ie., Bg {2,) U Bu
7: else
8:
Let é be the smallest index such that B; 0
+ 5 B, + CORESET (Y, n. d, k, logn t n² for Y Bo U ....UUB.. B >Y an ordered set
9:
of weighted points
10:
for j = to j i do B 0
12:
Bo < {mr}
13:
return the ordered set Blog n U... U Bu
operating system an AMD Ryzen 7 5700U CPU, with 8GB RAM and 8 cores with base clock 1.80 GHz. The general approach to our experiments is to produce a data stream S that defines dataset X, whose generation we describe below, well as in Appendix F. We then compare the performance of a simplified version of our algorithm with various state-of-the-art baselines.
Baselines. Our first baseline (denoted off for offline) is the simple Lloyd's algorithm the entire dataset X, with multiple iterations using the k-means++ initialization. This is a standard approach for finding good approximation the optimal clustering cost, because finding the optimal centers requires exponential time. Because this offline Lloyd's algorithm has access to the entire dataset, the expected behavior is that this algorithm will have the best objective, i.e., smallest clustering cost. However, we emphasize that this algorithm requires storing the entire dataset X in memory and thus its input size significantly larger than the sublinear space algorithms.
To compare with the offline Lloyd's algorithm, we run a number sublinear space algorithms. These algorithms generally perform some sort of processing on the datastream X to create coreset C. We normalize the space requirement these algorithms by permitting each algorithm to store m points across specific ranges of m. We then Lloyd's algorithm on the coreset C, with the same number of iterations using the k-means++ initialization.
Our first sublinear space algorithm is uniform sampling on the dataset X. That is, we form C' by uniformly sampling m points from X, before running Lloyd's s algorithm. We use uni to denote this algorithm whose first step is based uniformly sampling. Our second sublinear space algorithm the importance sampling approach used by histogram-based algorithms, e.g., [15, 11, 8]. These algorithms perform importance sampling, i.e., sample points into the coreset C with probability proportional to their distances from existing samples and delete points once the clustering cost of C much higher than the clustering cost of the dataset X. We use hist(ogram) to denote this algorithm that is based on the histogram frameworks for sliding windows.
Our final algorithm is a simplification of our algorithm. As with the histogram-based algorithm, we perform importance sampling on the stream S create the coreset C of size m. Thus we do not implement the ring and group sampling subroutines in our full algorithm. However, the crucial difference compared to the histogram-basse approach is that we forcefully discard points of that have expired. We use imp to denote this algorithm whose first step is based on importance sampling.
Dataset. We first describe the methodology and experimental setup of our empirical evaluation on real-world dataset with amount of synthetic noise before detailing the experimental results. The

---

first component of our dataset consists of the points of the SKIN (Skin Segmentation) dataset X" from the publicly available UCI repository [6], which was also used in the experiments of [8]. The dataset X" consists of 245, 057 points with four features, where each point refers to separate image. such that the first three features are constructed over BGR space, and the fourth feature the label for whether or not the image refers to a skin sample. We subsequently pre-process each dataset to have zero mean and unit standard deviation in each dimension.
We then form our dataset X by augmenting X' with 201 points in four-dimensional space, where 100 of these points were drawn from a spherical Gaussian with unit standard deviation in each direction and centered at (-10, 10, 0, 0) and 100 of these points were drawn from a spherical Gaussian with unit standard deviation each direction and centered at (10, 10, 0, 0). The final point of X was drawn from a spherical Gaussian with unit standard deviation centered at (500, 500, 0,0) Thus our dataset X has dimensions n 245, 258 and d 4. We then create the data stream S by prepending two additional points drawn from spherical Gaussians with standard deviation 2.75 centered at (-10, 10, O, 0) and (-10, - 10, 0, 0) respectively, so that the stream has length 245, 260. We set the window length to be 245, 258 in accordance with the "true" data set, so that the first two points of the stream will be expired by the data stream.
Experimental setup. For each of the instances of Lloyd's algorithm, either on the entire dataset X or the sampled coreset C, we use 10 iterations using the k-means++ initialization. While the offline Lloyd's 's algorithm stores the entire dataset X of 245, 258 points in memory, we only allow each of the sublinear-space algorithms to store a fixed m points. We compare the algorithms across m E {5, 10, 15, 20, 25, 30) and (2, 4,5, 5, 6, 7, 8, 9, 10}. Note that in the original dataset, each of the points has a label for either skin or non-skin, which would be reasonable for k = 2. However, due to the artificial structure possibly induced by the synthetic noise, it also makes sense to other values of k. In particular, preliminary experiments from uniform sampling by the elbow method indicated that ==3 would be a reasonable setting. Thus we fix k = 3 while varying m E {5, 10, 15, 20, 25, 303 and we arbitrarily fix m 25 while varying k E {2, 3, 4, 5, 6, 7, 10
Experimental results. For each choice of m and k; we ran each algorithm 30 times and tracked the resulting clustering cost. Our algorithm demonstrated superior performance than the other sublinear- space algorithms across all values of m (5, 10, 15, 20, 25, 30} and k E {2, 3, 4, 5, 6, 7, 8,9, 9, 10), and was even quite competitive with the offline Lloyd's algorithm, even though our algorithm only used memory size m < 30, while the offline algorithm used memory 245, 258.
Uniform sampling performed well for k 2, which in some case captures the strueture imposed on the data through the skin vs. non-skin label, but for larger k the optimal solutions start placing centers to handle the synthetic noise, which may not be sampled by uniform sampling. Thus uniform sampling performed relatively poorly albeit quite stably for larger k. In contrast, the histogram- based algorithm performed poorly for small i across all our ranges of m, due to sampling the extra points in S X, so that the resulting Lloyd's algorithm on C' moved the centers far away from the optimal centers of X. On the other hand, the histogram-bart based algorithm performed well for larger k. likely due to additional centers that could be afforded to handle the points in S \ X. We plot our results in Figure and defer additional experiments Appendix F.
4 Conclusion
In this paper, we give algorithm outputs a (1 + -pprrxxxmmai to (k, z)-clustering in the sliding window model, while using
& === polylog eA - words of space when the points are from [A] line of work [5, 16, 34, 8, 35], but also nearly matches the
Our algorithm not only improves space used by the offline coreset constructions of [27]. which is known to be near-optimal in light of a a lower bound for the size of an offline coreset [45].
We also give lower bound that shows a logarithmic overhead in the number of points is needed to maintain (1 + e)-online coreset compared to a (1 + correset. That is, we gave in Theorem 1.4 Tn, such that any (1 + e)-oliine coreset for k-means clustering
set X C [A]d of points on X requires Ω ( lo points. However, this does not rule out whether the log overhead is necessary for (k, 2) cluustterg in the sliding window model, since a sliding window algorithm does

---

uniform range
unito range
28
rance evg. hist, errs
2
Histograrr range
avg. hist ers
avg: imp: ems
ofline range
Clusteiigg cost
ofline range
aug imp
221
220
27
2.
6
10
5
10
1.5
25
30
Number of clasters
Number
(a) Comparisons varying
(b) Comparisons for varying m.
Fig. 1: Comparison of average clustering costs made by uniform sampling, histogram- based algorithm, and our coreset-based algorithm across various settings of space allocated to the algorithm, given synthetic dataset. For comparison, also include the offline k-means++ algorithm baseline, though it is inefficient because stores the entire dataset.
not necessarily need to maintain an online coreset. We leave this question as possible direction for future work.
Acknowledgments
David P. Woodruff and Samson Zhou were partially supported by Simons Investigator Award and by the National Science Foundation under Grant No. CCF-1815840, This work was done in part while Samson Zhou was at Carnegie Mellon University, UC Berkeley, and Rice University.
References
[1] Marcel R. Ackermann, Marcus Märtens, Christoph Raupach, Kamil Swierkot, Christianc Lammersen, and Christian Sohler. Streamkm++: A clustering algorithm for data streams. ACM J. Exp. Algorithmics, 17(1), 2012. 2
[2] Miklós Ajtai, Vladimir Braverman, T. S. Jayram, Sandeep Silwal, Alec Sun, David P. Woodruff, and Samson Zhou. The white-box adversarial data stream model. In PODS '22: International Conference on Management of Duta, 2022, pages 15-27, 2022.
[3] Apple.
Diivvcc-Overvie..pdf..
[4] Brian Babcock, Shivnath Babu, Mayur Datar, Rajeev Motwani, and Jennifer Widom. Models and issues in data stream systems. In Proceedings of the Twenty-first ACM SIGACT-SIGMOD- SIGART Symposium on Principles of Database Systems, pages 1-16, 2002. 2
[5] Brian Babcock, Mayur Datar, Rajeev Motwani, and Liadan O' O'Callaghan. Maintaining variance and k-medians over data stream windows. In Proceedings of the Twenty-Secone ACM SIGACT- SIGMOD-SIGART Symposium Principles of Database Systems, pages 234-243, 2003. 2,
[6] Rajen Bhatt and Abhinav Dhall. Skin segmentation dataset. UCI Leamning Repository. 9
[7] Jeremiah Blocki, Seunghoon Lee, Tamalika Mukherjee, and Samson Zhou. Differentially private (2-heavy hitters in the sliding window model. In The Eleventh International Conference on Learning Representations, ICLR, 2023. 2
[8] Michele Borassi, Alessandro Epasto, Silvio Lattanzi, Sergei Vassilvitskii, and Morteza Zadi- moghaddam. Sliding window algorithms for k-clustering problems. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems, NeurIPS, 2020. 2, 5, 8,
10

---

[9] Vladimir Braverman, Petros Drineas, Cameron Musco, Christopher Musco, Jalaj ypadhyay, David P. Woodruff. and Samson Zhou. Near optimal linear algebra in the online and sliding window models. In 6l IEEE Annual Symposium on Foundations of Computer Science, FOCS, pages 517-528, 2020. 2, 21
[10] Vladimir Braverman, Dan Feldman, Harry Lang, Adiel Statman, and Samson Zhou. Efficient coreset constructions via sensitivity sampling. In Asian Conference on Machine Learning, ACML, pages 948-963, 2021. 2,
[11] Vladimir Braverman, Gereon Frahling, Harry Lang, Christian Sohler, and Lin F. Yang. Cluster- ing high dimensional dynamic data streams. In Proceedings of the 34th International Conference on Machine Learning. JCML, pages 576-585, 2017. 2,
[12] Vladimir Braverman, Ran Gelles, and Rafail Ostrovsky. How to catch lz-heavy-hitters on sliding windows. Theor: Comput. Sci., 554:82-94, 2014. 2
[13] Vladimir Braverman, Elena Grigorescu, Harry Lang, David P. Woodruff, and Samson Zhou. Nearly optimal distinct elements and heavy hitters on sliding windows. In Approximation, Ran- domization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM, pages 7:1-7:22, 2018.
[14] Vladimir Braverman, Avinatan Hassidim, Yossi Matias, Mariano Schain, Sandeep Silwal, and Samson Zhou. Adversarial robustness of streaming algorithms through importance sampling. In Advances in Neural Information Processing Systems 34: Annual Conference Neural Information Processing Systems, NeurlPS, pages 3544-3557, 2021.
[15] Vladimir Braverman, Harry Lang. Keith Levin, and Morteza Monemizadeh. Clustering on sliding windows in polylogarithmic space. In 35th IARCS Annual Conference Foundation of Software Technology and Theoretical Computer Science, FSTTCS, pages 350-364, 2015. 2, 8
[16] Vladimir Braverman, Harry Lang, Keith Levin, and Morteza Monemizadeh. Clustering problems on sliding windows. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 1374-1390, 2016. 2, 3, 3,4, 9
[17] Vladimir Braverman, Adam Meyerson, Rafail Ostrovsky, Alan Roytman, Michael Shindler, and Brian Tagiku. Streaming k-means on well-chusterable data. In Proceedings of the Twenty-Second Annual ACM- Symposium on Discrete Algorithms, SODA, pages 20-40, 2011.
[18] Vladimir Braverman and Rafail Ostrovsky. Smooth histograms for sliding windows. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS), Proceedings, pages 283-293, 2007. 2,
[19] Vladimir Braverman, Rafail Ostrovsky, and Carlo Zaniolo. Optimal sampling from sliding windows. J. Comput. Syst. Sci., 7861):260-272, 2012.
[20] Vladimir Braverman, Viska Wei, and Samson Zhou Symmetric norm estimation and regres- sion sliding windows. In Computing and Combinatorics 27th International Conference, COCOON, Proceedings, pages 528-539, 2021. 2
[21] Moses Charikar, Liadan O' O'Callaghan, and Rina Panigrahy. Better streaming algorithms for clus- tering problems. In Proceedings of the 35th Annual ACM Symposium Theory of Computing, pages 30-39, 2003.
[22] Jiecao Chen, Huy L. Nguyen, and Qin Zhang. Submodular maximization over sliding windows. CoRR, abs/1611 0tts/161..01111 1.00129. 2016. 2
[23] Ke Chen. On coresets for k-median and k-means clustering in metric and euclidean spaces and their applications. SIAM J. Comput., 39(3):923 947, 2009. 2
[24] Vincent Cohen-Addad, 2022. Private communication. 17
[25] Vincent Cohen-Addad, Kasper Green Larsen, David Saulpic, and Chris Schwiegelshohn. To- wards optimal lower bounds for k-median and k-means coresets. In STOC '22: 54th Annual ACM SIGACT Symposium Theory of Computing, pages 1038-1051, 2022. 2, 5, 22
11

---

[26] Vincent Cdden-Addad, Kasper Green Larsen, David Saulpic, Chris Schwiegelshohn, and Omar Ali Sheikh-Omar. Improved coresets for euclidean k-means. In NeurlPS, 2022. 3.4 4
[27] Vincent Cohen-Addad, David Saulpic, and Chris Schwiegelshonn. A new coreset framework for clustering. In STOC: 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 169-182, 2021. 2, 3, 4, 5, 9, 16, 17, 19, 24, 25,20 26
[28] Vincent Cohen-Addad, Chris Schwiegelshohn, and Christian Sohler. Diameter and k-center in sliding windows. In 43rd International Colloquium on Automata, Languages, and Programming, ICALP, pages 19:1-19:12, 2016.
[29] Vincent CCohen-Addad David P. Woodruff, and Samson Zhou. Streaming euclidean k-median and k-means with o(log n) space. CoRR, abs/2310.02882,, 2023. 2,
[30] Graham Cormode. The continuous distributed monitoring model. SIGMOD Rec., 42(1):5 14,
2013.
[31] Graham Cormode and Minos N. Garofalakis. Streaming in a connected world: querying and tracking distributed data streams. In EDBT 2008, 11th International Conference on Extending Database Technology, Proceedings, page 745, 2008.
[32] Graham Cormode and S. Muthukrishnan. What's new: finding significant differences in network data streams. 1EEE/ACM Trans. Netw, 13(6):1219-1233) 2005. 2
[33] Mayur Datar, Aristides Gionis, Piotr Indyk, and Rajeev Motwani. Maintaining stream statistics over sliding windows. SIAM J. Comput., 31 (16)) 2002. 2,4 4
[34] Alessandro Epasto, Silvio Lattanzi, Sergei Vassilvitskii, and Morteza Zadimoghaddam, Submod- ular optimization over sliding windows. In Proceedings of the 26th International Conference on World Wide Web, WWW, pages 421 221-430, 2017. 2, 3, 5,9
[35] Alessandro Epasto, Mohammad Mahdian, Vahab Mirrokni, and Peilin Zhong. Improved sliding window algorithms for clustering and coverage via bucketing-based sketches. In Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 3005- 3042, 2022. 2, 3, 4,
[36] Facebook.
2
[37] Dan Feldman and Michael Langberg. A unified framework for approximating and clustering data. In Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC, pages 569-578, 2011 1.11.2 2,
[38] Dan Feldman, Melanie Schmidt, and Christian Sohler. Turning big data into tiny data: Constant- size coresets for k-means, pea, and projective clustering. SIAM J. Comput., 49(3):601-657, 2020. 19
[39] Dan Feldman and Leonard J. Schulman. Data reduction for weighted and ruslier-resistant clustering. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 1343-1354, 2012. 2,
[40] Zhili Feng, Praneeth Kacham, and David P. Woodruff. Strong coresets for subspace approxima- tion and k-median in nearly linear time. CoRR, 12000, 2019. 19
[41] Google. https://polccie.gooogleec gowgiiieessooole...eee com//eechnnoooiiieeeeetttio..... 2
[42] Sudipto Guha, Nina Mishra, Rajeev Motwani, and Liadan O'Callaghan. Clustering data streams. In 41 Annual Symposium on Foundations of Computer Science, FOCS, pages 359-366, 2000.
2
[43] Sariel Har-Peled and Akash Kushal. Smaller coresets for k-median and k-means clustering. Discret. Comput. Geom,, 37(1):3-19, 2007. 2
[44] Sariel Har-Peled and Soham Mazumdar. On coresets for k-means and k-median clustering, In Proceedings of the 36th Annual ACM Symposium on Theory of Computing, pages 291-300, 2004. 2
12

---

[45] Lingxiao Huang, Jian Li, and Xuan Wu. Towards optimal coreset construction for (k, z)- clustering: Breaking the quadratic dependency on k. CoRR, abs/2211.11923, 2022. 2,
[46] Lingxiao Huang and Nisheeth K. Vishnoi. Coresets for clustering euclidean spaces: impor- tance sampling is nearly optimal. In Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC, pages 1416-1429, 2020. 2,
[47] Rajesh Jayaram, David P. Woodruff, and Samson Zhou. Truly perfect samplers for data streams and sliding windows. In PODS '2: International Conference on Management of Data, pages 29-40, 2022. 2
[48] Lap-Kei Lee and H. F. Ting. Maintaining significant stream statistics over sliding windows. In Proceedings of the Seventeenth Annual ACM-SIAM Symposium Discrete Algorithms, SODA, pages 724-732, 2006.
[49] Lap-Kei Lee and H. F. Ting. A simpler and more efficient deterministic scheme for finding frequent items over sliding windows. In Proceedings of the Twenty-Fifth ACM SIGACT- SIGMOD-SIGART Symposium Principles of Database Systems, pages 297,297, 2006. 2
[50] J MacQueen. Classification and analysis of multivariate observations. In 5th Berkeley Symp. Math. Statist. Probability, pages 281-297, 1967.
[51] Konstantin Makarychev, Yury Makarychev, and Ilya P. Razenshteyn. Performance of johnson- lindenstrauss transform for k-means and k-medians clustering. In Proceedings of the 51 Anmual ACM SIGACT Symposium on Theory of Computing, STOC, pages 1027-1038, 2019.
[52] Gurmeet Singh Manku and Rajeev Motwani. Approximate frequency counts over data streams.
Proc. VLDB Endow., 5(12):1699, 2012. 2
[53] Jirí Matousek. On approximate geometric k-clustering. Discret. Comput. Geom., 24(1):61-84
2000. 17
[54] Adam Meyerson. Online facility location. In 42nd Annual Symposium Foundations of Computer Science, FOCS, pages 426-431. IEEE Computer Society, 2001. 15
[55] Shyam Narayanan and Jelani Nelson. Optimal terminal dimensionality reduction in euclidean space. In Proceedings of the 51 Annual ACM SIGACT Symposium on Theory of Computing, STOC, pages 1064-1069, 2019. 20
[56] Miles Osborne, Sean Moran, Richard McCreadie, Alexander von Lünen, Martin D. Sykora, Amparo Elizabeth Cano, Neil Ireson, Craig Macdonald, Iadh Ounis, Yulan He, Tom Jackson, Fabio Ciravegna, and Ann O' Brien.. Real-time detection, tracking, and monitoring of automat- ically discovered events in social media. Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics, ACL, pages 37-42, 2014." 2
[57] Odysseas Papapetrou, Minos N. Garofalakis, and Antonios Deligiannakis. Sketching distributed data streams. VLDB J., 24(3):345-33 368, 2015. 2
[58] Christian Sohler and David P. Woodruff. Strong coresets for k-median and subspace approxi- mation: Goodbye dimension. In 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS, pages 802-813, 2018.
[59] Zhao Song. Lin F. Yang, and Peilin Zhong. Sensitivity sampling over dynamic geometric data streams with applications to k-clustering. CoRR, abbs/882.004455 2018. 2,5
[60] Hugo Steinhaus et al. Sur la division des corps matériels en parties. Bull. Acad. Polon. Sci, (804))801, 1956.
[61] Murad Tukan, Xuan Wu, Samson Zhou, Vladimir Braverman, and Dan Feldman. New coresets for projective clustering and applications. International Conference on Artificial Intelligence and Statistics, A/STATS, pages 5391-5415, 2022. 2
13

---

[62] Zhewei Wei, Xuancheng Liu, Feifei Li. Shuo Shang, Xiaoyong Du, and Ji- RinRong Wen. Matrix sketching over sliding windows. In Proceedings of the 2016 International Conference on Management of Data, SIGMOD Conference, pages 1465-1480. ACM, 2016. 2
[63] David P. Woodruff and Samson Zhou. Tight bounds for adversarially robust streams and sliding windows via difference estimators. 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS. pages 1183-1196, 2021.
14

---

A Preliminaries
For positive integer n,, we use the notation [n] denote the set {I...., n). Similarly, we use [A]d to denote {1..... A]d. We use poly(n) to denote fixed polynomial in with degree determined as necessary by setting the appropriate constants in corresponding variables. Similarly, we use polylog(n) to denote poly(log*) We suppress polylogarithmic dependencies by writing Ô (J(()) =
O (f(+) polylog f()).
For (k; --clustrriggg on a set X = {-,,... ..... En C Id using a set C of k centers and a distance function dist(...). -), we define the notation Cost X, C) Σi= min.ec dist( c)F. We also define the notation (X; = s:jss Cost(X XX, S), so that Cost SISı is the cost of an optimal (k: =)-chestein
Definition A.1 ((a,3)-an -apppoxxxiiiiii We say a set of centers C provides an capprooopoii to the optimal k-means clustering on set X if|C) S 3k and
Cost X, C) aOPT.
Definition A.2 (Coreset). A coreset for (k, cllusteri on an approximation parameter E >> O and a set X of points ; In E R.d with distance function dist is subset S of weighted points of X with weight function w such that for any set C of k points, we have
1
(1 (1-E) E) Σ dist(x,, C)² S Ew(())
w(g) dist(g. 5)² ((++E) Σ dist(r;,C)².
YES
Definition A.3 (Online Coreset). An online coreset for (k, 2)-clsstering on an approximation pa- rameter' ε > and a set X of points ..,..... In E Rd with distance function dist is a subset S of weighted points of X with weight function w such that for any set C of lo points and for any I [m]]. we have
(1 (1-E)
Σ dist 24, C) < Σ w(1) dist(g. S,)²
Σ dist(r; C)*,
gESe
where St SS= = X,), ie.., the subset of S that has arrived at time t.
Theorem A.4 (Bernstein's 's inequality). Let XI...., Xn be independent random variables such that [[X?] < and X, for all E [n]. Let X E. X1 and 7 > 0. Then
-2
Pr 7] S exp
2 2E, E[X?1
f/ - E[X.] S & for all i, then for of E[X?] TE(X)}
Pr 2 E + exp
2 23, o; 2/
Meyerson sketch. We briefly review the Meyerson sketch [54] and the relevant properties that we need from the Meyerson sketch. The Meyerson sketch provides an (a, approrooxinniio [A]" with = 2=+7 and O (22e log n log A).
(k, 2)-
clustering data stream of points ......: Fn Moreover, for our purposes, it provides the crucial property that on the arrival of each point 24 the algorithm irrevocably assigns v; to of the 3k centers. Specifically, the clustering cost at the end of the stream is computed with respect to the center that x; is assigned at time i, which may not be the closest center I because the closer center can be opened
later time.
For the case of discussion, we describe the Meyerson sketch for 2 = 1; the intuition generalizes naturally to other values of 2. The Meyerson sketch performs via a guess-and-double approach, where it first attempts to guess the cost of the optimal clustering cost. Using the guess of the cost, then turns each point into center with probability proportional to the distance of that point from the existing centers. This subroutine is illustrated in Algorithm 3. If too many centers have been opened, then the Meyerson sketch determines that the guess for the optimal clustering cost must have been too low and increases the guess. The overall algorithm is given in Algorithm 4.
We require the following properties from the Meyerson sketch.
15

---

Algorithm 3 High probability MEYERSON(X, OPT, o, 6, A, 2, sketch
Input: Points X -i,-... Rd with aspect ratio A, estimate OPT > 0 such that aOPT S
OPT & OPT for some a E (0, 1), failure probability á E (0, 1)
Output: A coreset for k-clustering X
1: 7 <- 2
2: for E [>] do
3:
for t E [n] do
4:
if
then
5:
Mi + 21, Cju t O, wi(xt) =
6:
else
7:
MM S 4k(1 + log A)
gotz + then
a=
k(I+lor A) dist(zn.M)) ,1). add x to M, with weight 1,
8:
With probability min
OPT
i.e., wi (x))) Otherwise, let 2 = argmin M. dist(r,, v), increment the weight of 2, i.e.,
9:
(2) - w2(2) + 1. and increase Cs. + Cuu dist ()))
Let argmin 4: k.M M a) (+5=++) Cj, be the index of the minimal cost sketch with most 4k:(1 + log A 11: return Uke(s) Ms, Wj, and Caz
2 +1) samples
DReturn FAIL if such j does exist
a²
Algorithm High probability MULTMEYERSON sketch
Input: Points X == Ii....,
,.....,,yg 2n E Rd with aspect ratio A, estimate ÖPT 2 0 such that aOPT S
OPT < OPT for some (0, 1), failure probability å E (0,1)
Output: A coreset for k-means clustering on OPT upper bounds the cost of the optimal clustering
1: 7 + log (A=)
2: for E by] do
3:
Run MEYERSON (X,2,, 1. A, 2, k) in parallel
4: Let j be the minimal index in [?]] such that MEYERSON with input 2 has size smaller than
8k log + log A) (222+3 + 1) and cost smaller than 2*46+3
1 5: return the output for MEYERSON (x,2), a 2: 2,
Theorem 2.1. [8] Given an input stream Ii...., Rd defining a set X C. [A] there exists an online algorithm BOUTMEYYRSSON that with probability least 1 poly(n)'
(1) on the arrival of each point v,, assigns 2; to a center in C through a mapping x X - C, where C contains at most O (22* log log A) centers
(2) ExEx |a, - (I::)ll $ 2 Costis sx(X,
(3) MULTMEYERSON uses O (2 log (ndA)) words of space
B Online (1+5)) +))Corereset
In this section, describe how to construct online (1 + =) coreset for (k, x)-clustering under general discrete metrics. We first describe the offline coreset construction of [27] and then argue that the construction can be adapted to online setting at the cost of logarithmic overheads, which suffice for our purpose.
Let A be an (a, -ppapooxiintoo for (k, =),,zl)luuterri C1,..., Cak be the clusters of X induced by A. Suppose the points of X arrive in data stream For fixed > 0. [27] define the following notions of rings and groups:
an input set X C [A]d and let
16

---

The average cost of cluster C; is denoted by kc. = Cost (C..A)
[0,]
For any i, the ring Ri,j is the set of points C₁ such that
2'kc. S Cos 2 KC.
For any j. R3 RR-
The inner ring Rr(C,) Ujs2s log & Ais the set of points of C, with cost at most ($) KC,, More generally for a solution S, let Ri denote the union of the inner rings induced by S.
The outer ring Ro(C.) = Uy22log? log Rag is the set of points of C with cost at least
(3) 23 RC, More generally for a solution S, let R& denote the union of the outer rings induced by S.
The main ring RM(CC ()) is the set of points of C2 that are not in the inner or outer rings, i.e., (C;) C₁ \ (R, U Ro(C;)
For any j. the group G3,5 consists of the (2h-1 1 + 1) to (2*)- points of each ring Rad that arrive in S.
For any j. we Gj.mi to denote the union of the groups with the smallest costs, i.e.,
2/ x E Raj, Cost Cost(Ri A) 2 Cost (R2, A)
Gj,min
Bk
The outer groups Go partition the outer rings Ry so that
GP = {11 Cs
E
Cost((RO. A) 2 I Cost(Ro(C)))
( ( (E)
Cost (RA))) A).
20+11 s
4z
3k
4=
3k
We define Gonn = UbsoGo and GO max
Ubi5 log 4 Go.
We remark that unlike the definition of [27], Gj.min is subset of the groups Gj.s with b 2 1, but we shall nevertheless show that our sampling procedure preserves the cost contributed by each group. We also require the following slight variation of the definition of A-approximate centroid set from [53] due to [27].
Definition B.1 (A-approximate centroid set). Let X C I.d be a set of points, let k. k, be two positive integers, and let e >> O be accuracy parameter. Given a set A of centers, we say a set C is an A-approximate centroid set for (ki, c)clusterrin on X if for every set of l centers S C Rr. there exists S C Rd k points such that for all x E X with Cost(x, S ($t) Cost(ar, A) or Cost(æ, 8) < Sey A),
|Cost (I., Cost(x,, 5)15 z <lo((//)) (Cost S) - Cost A).
8
The following statement is implied by the proof of Theorem in [27].
Theorem B.2. [27, 24] Let O be constant. Let G for group induced by an (a, B)- bicriteria assignment A. For each cluster C2 with i E [3k], let D, = C. n G. Let C be an A-approximate centroid set for G and let
C Cmax(a² )
log" 1
<llog [C + log log + logn log" 1
1
for some sufficiently large constant C > O. Let min min
Aost(D;,A)
Cost(x,
' logn, Suppose each point E X is sampled and reweighted independently into a set On with probubility Pz, where
Se [Da] Cost(G, A)
n
Co -ry logn.
Px 2 min(Ge + nu. 1). Let 22 = 2o (UN.BBG))U
(Ro(C.) n GO
Suppose Or the set of centers in A, where each center e; with E [3k] has weight wi where w; is
(1 + -)ppprooximation to [Rr(C.)] + IC; GumGgminn + [Ro(C.) n Ginll Then (Ωi \ l2) Ufz
is (1 + e)-coreset for the (k, =)cllsstginng problem with probability pn]y(n)
17

---

We first show that the sampling probabilities for each point in the stream by RINGSAMPLE in Algorithm satisfies the conditions of Theorem B.2. Lemma B.3. Let G for group induced by (a, })-bicriteria assignment A at a time t, with I [n]. For each cluster C, with E [3k], let D; = C2 n G. Let C be an A-approximate centroid set for G and let
C Cmax(a2,a" min .0a)
1
log 8
k |olg [C] + log log + log n
log
for some sufficiently large constant C > 0 Let
Cost(Di..A)
Cost(x, A)
Y logn, n,
nu Cost(G, A) "y log
[1i] Cost A)
Then the probability Pa that RINGSAMPLE (Algorithm 1) samples each point satisfies P2 2 min(S. + ?m 1).
Proof. Suppose that x E Raj and E Gj.b at time I, for some E [3k] in an assignment by A from MUI.MEYN Let u be the time that x arrived the stream. By the properties of the Meyerson sketch, i.e., MULTMEYERSON in Theorem 2.1, is irrevocably assigned to a cluster C with E [3k] at time u. Hence, r must also be assigned to ring Rıg at time u. Moreover, since the stream is insertion-only, then the number of points in all rings R2,; for fixed across all E [3K] is monotonically non-decreasing. Thus z must also be assigned to group Gj,b at time u.
Let Ps be the sampling probability of x by RINGSAMPLE in Algorithm 1 at time u. We have that
P2 min - Fu
4 .loog log nog,,, 1),
where ra is the number of points in Gj.b at time u. Let G/ be the subset of G5.b that have arrived at time u and let G. be the subset of GG that have arrived at time t. Let c be the center assigned to point x, so that Cost(æ, ei) = Cost(z, A) and let c(") be the points assigned to at time u. Similarly, let D(") c(") G (u)
By the definition of Ragj and Gj,b-
j.b
|| - c:ll
2
2 2 25 Tu
Cost(G (u)
j,b A)
(G j,bo A)
Since both the cost group G3,bb and the number of points in D, is monotonically non-decreasing over time, then at time t, we have
Se
(Dss [D,] Cost(G
2| c:112 Cost(G AA
4
y logn n
D.| J.b. Co. AA)
To
Similarly, we have that due to the monotonicity of the cost of group Gj.b over time,
fle
| c/15
| cı15
2
7 log n
Cost(G j.b: A)
Cost(G j,b A)
Tu
Thus for sufficiently large constant C' in the definition of in RINGSAMPLE, we have that
Pz 2 min(Se Muy 1),
since Pa = min (+L y log n, 1).
We next justify the space complexity of Algorithm 1, i.e., showing that with high probability, upper bound of the number of samples can be determined.
Lemma B.4. RINGSAMPLE (Algorithm 1) samples
max(a?, )3
log2 loo |C| + log log 1 + logg log" n log² A logg
1 g
min(s?,e7 g²
points with high probability.
18

---

Proof. Recall that by definition, the groups G partition the points X 21..... 2n S [A] For fixed j and b, let Y be an indicator random variable for whether the i-th point of G2 is sampled by
RINGSAMPLE. Then we have E [Y;] I ! +y log n and similarly E [Y?) I .y log n. By Bernstein's inequality, Theorem A.4, we have that
Pr
Σ Y; 807 log n)
S n
and more generally, we have that Σv 0 (7 log n) with high probability. Thus by a union bound over all and b, we have that the number of sampled points is at most
(min(e imnn(??,e7) E=)
1
log 1
k log [CI + log _ logn log* log A Alog² 1
O (1 log" nlog² A) =0
for maxia" min(s?,e") (-))
a log ! (A: lo: |C| + log log + log m) log 1.
Moreover, note that we can for all [n], we can explicitly track both G and Cost(G A) j.b
the stream is updated, because once the bieriteria algorithm assigns point center in A, the assignment will remain the same for the rest of the stream. Thus, we have the following:
Lemma B.5. For each and b, there exists an algorithm that maintains both G and Cost j,b. A) for all t [n] using O (log(ndA)) space.
Putting things together, we give the full guarantees of RINGS in Algorithm 1. Lemma 2.2. Let C an A-approximate centroid set for a fixed group G. There exists an algorithm RINGSAMPLE that samples
max a²) min(s?,e* log² (I loog |C| + log log
1 + log log* n log² A log² :
points and with high probability, outputs (1 + -onlliee coreset for the k-means clustering problem.
Proof. Consider RINGSAMPLE. Before claiming the algorithm gives an (1 + z)-onlnne coreset, we first consider a fixed time t E [n]. Then correctness at time t follows from applying Theorem B.2, given Lemma B.3 and Lemma B.5. We then observe that once a center is formed by RINGSAMPLE, i.e., once a point is sampled, then it irrevocably remains center in the data structure. Therefore, conditioned on the correctness at time f, then the data structure will always correctly give an (1 + c)- coreset the prefix of points in the stream any later point t' in the stream, t' E [n] with t' > t. It thus suffices to argue correctness over all E [n]] which requires a simple union bound. The space complexity follows from Lemma B.4 and Lemma B.5.
To apply Lemma 2.2, we require upper bounding the term log [C]. To that end, we first require the following definition of doubling dimension.
Definition B.6 (Doubling dimension). The doubling dimension of a metric space X with metric d is the smallest integer such that for any x E X, is possible to cover the ball of radius 2r around with 2 balls of radius r.
Observe that general discrete metric spaces with n points have doubling dimension O (logn) since all points be covered by 21og n balls.
We then recall the following result that upper bounds the size log |C| for metric spaces with doubling dimension d.
Lemma B.7. [27] Given a subset X from a metric space with doubling dimension d, E > O, and an a-approximate solution A with at most is polylog(n) centers, there exists A-approximate centroid set for X of size X| (a) O(d)
is known that the Euclidean space has doubling dimension (d)), which would give a d dependency on our coreset size. However, [38] showed that the d dependency can be replaced with 22 which was subsequently improved by line of works, e.g., [58, 40, 46), ultimately down to dependency of ex log & using the following notion of terminal embeddings:
k
19

---

Level 3:
Level 2:
Level
Stream:
Fig. Merge and reduce framework on a stream of length n. The coresets at level are the entire blocks. The coresets at level for i are each (1 O ( 2log children nodes in level i 1.
-coresets of the coresets their mapping f Rd I. a terminal embedding for all x E X and all y E Rd.
Definition B.8 (Terminal embedding). Let e E (0, and X S IR be a set of points. Then a
(1 - -)=s]|== 2l1a 11](x)) [(w)]l (1 +) -
[55] gave construction of terminal embedding with O (22 logn) that be applied in linear space through exhaustive search when polynomial runtime is not required. Thus Lemma 2.2 nows give the following:
Theorem 1.3. There exists an algorithm that samples m polylog points and with high probability, outputs a (1 + =))-oiie coreset for (k, 2lluuttinn
For the purpose of clarity, we emphasize that the algorithm does the sample complexity is sublinear. Namely, for each stream update, we construct and apply terminal embedding to project each point lower dimension. We then compute the appropriate sampling probability of the projected point, but then sample the original point with the computed sampling probability.
sublinear space, even though
C Sliding Window Model
In this section, describe how our online coreset construction for (k, ->clusterinn general discrete metric spaces can used to achieve near-optimal space algorithms for (k, 2)-clustering in the sliding window model.
We first recall standard approach for using offline coreset constructions for insertion-onl streaming algorithms. Suppose there exists a randomized algorithm that produces an online coreset algorithm that uses S(n, e, 6) points for an input stream of length n, accuracy e, and failure probability where for the ease of discussion, clustering constraint k, the parameter z, or additional parameters for whatever problem the coreset construction may approximate. A standard approach for using coresets insertion-only streams is
omit additional dependencies, such as the dimension d, the
the merge-and-reducc approach, which partitions the stream into blocks of size S f1, 2log poly(n) and builds coreset for each block. Each coreset is then viewed as the leaves a binary tree with height at most log since the binary tree has at most n leaves. Then at each level of the binary tree, for each node in the level, a coreset of size S (n. 2 n poly(n)) is built from the coresets representing the two children of the node. Due the mergeability property of coresets, the coreset log
the root the tree will be a coreset for the entire stream with accuracy (1 2 and failure probability d. We give an illustration of this approach in Figure
I {1++
This approach fails for sliding window algorithms because the elements at the beginning of the data stream expire, and so coresets corresponding to earlier blocks of the stream may longer accurate, which would result the coreset at the root of the tree also no longer being accurate. On the
other hand, suppose we partition the stream into blocks consisting of S n,, 2 2 n poly(n) elements as before, but instead of creating offline coreset for each block,
create online coreset
20

---

for the elements in reverse. That is, since the elements in each block are explicitly stored. we can create offline an artificial stream consisting of the elements the block in reverse and then give the artificial stream as input to the online coreset construction. Note that if we also first consider the "latter" coreset when merging two coresets, then this effectively reverses the stream. Moreover, by the correctness of the online coreset, our data structure provides correctness over any prefix of the reversed stream, or equivalently, any suffix of the stream and specifically, correctness over the sliding window.
Indeed, [9] showed that deterministic online coresets for problems in randomized numerical linear algebra can be used to achieve deterministic algorithms for the corresponding problems in the sliding window model. We thus further adapt the merge-and-rediee online coresets for problems in clustering can also be used to achieve randomized algorithms for the corresponding problems in the sliding window model. We formalize this approach in Algorithm duplicated below:
framework to show that randomized
Algorithm 5 Merge-and -nd-ueducdee framework for randomized algorithms in the sliding window model, using randomized constructions of online coresets
Input: A clustering function /, set of points ;,,..., In Rdd, accuracy parameter & 0, failure probability 8 E (0, 1), and window size W > 0
Output: An approximation of f on the W most recent points
I: Let CORESET(X, n, d, k, 6) be an online coreset construction with S(n, d, k e, points
set X CR.
ش 6 [n,d, log log 72 2: m O ((,(n,,,
3: Initialize blocks Bo, B1..... Blug
4: for each point 24 with & E [n] do
5: if Bo does not contain points then
6:
Prepend xe to Bo, i.e., Bo + [x,} U Bo 7: else
8:
Let be the smallest index such that Bi =
9:
B; + CORESET (Y, d,, k, log no
& ne for Y Bo ...... UB
>Y is an ordered set
of weighted points
for j = to j= 1 do
11:
B, + 0
Bo < {21}
13:
return the ordered set Blog n U...UBo
Theorem 2.3. Let I1,..., In be a stream of points in [A] e >> O, and let X = {xn- +1 n be the W most recent points. Suppose there exists a randomized algorithm that with probability at least 1 - 8, outputs an online coreset algorithm for a k-clustering problem with S(n, d, k, e, 8) points. Then there exists a randomized algorithm that with probability at least
outputs a coreset for the k-clustering problem in the sliding window model with O (s n, d, k. logn 2e log n points.
Proof. Consider Algorithm 2. Let CORESET(X, n, d, k, 8) be a randomized algorithm that, with probability at least - computes an online coreset for k-clustering problem f with S(n, d, k 6) points.
We first claim that for each B, is (1+ = online coreset for 2 points. To that end, observe that B, can only be non-empty if at some time, Bg contains m points and Bı,..., B are all non-empty. By the correctness of the subroutine CORESET, B, a 1 logn online coreset
ing
for the points in Bu U...U B,-1 some point during the stream. Hence by induction, B, is
[
loo coresct for m + | 2 ' = 2 m points.
log
log
Now, because Algorithm 2 inserts the newest points at the beginning of Bo, then the stream is fed in reverse the online coreset k-clustering for the W most recent points in the stream.
procedure. Thus, for any W E ( Bo U...U . B, provides an
21

---

To analyze the probability of failure, we remark that there are at most n points in the stream. For each point, there are at most n coresets constructed by the subroutine CORESET (in fact, the number of coreset constructions is upper bounded by O (log n.). Since each subroutine is called with failure n² then by union bound, the total failure probability is at most 5.
probability
6
To analyze the space complexity, note that there at most O (logn) coreset constructions B,og maintained by the algorithm. Each coreset construction samples S n2, d, k, logn nt points. Hence, the total number of sampled points is O (s (n, d, k, log nz log
By Theorem 1.3 and Theorem 2.3, have:
Theorem 2.4. There exists an algorithm that samples min(s" gattyy polylog nA points and with high probability, outputs a (1 + -)-oresst to (k, cllusstrrinn in the sliding window model.
Using an offline algorithm for (k, z)-clsttering for post-processing after the data stream, we have:
Theorem 1.1. There exists an algorithm that samples min(s polylog ná points and with high probability, outputs a (1 + approxximatii to (k, z)-clustering for the Euclidean distance on [A] in the sliding window model.
D Lower Bounds
In this section, show that any (1 + e)-online coreset for (k, z)-clustering requires 92 ( log n) points. The intuition somewhat straightforward and a black-box manner. [25] showed the existence set of (+) unit vectors such that any sublinear space data structure would not be able to accurately determine Cost x) for set of k unit vectors C. They thus showed that any
offline (1 -coreset construction for (ks, cl-cttstgi required Ω (+* points.
Because an online (1 + e)-coreset must answer queries on all prefixes of the stream, our goal is to essentially embed 12 n) instances of the hard instance of [25] into the stream, which would require 52 [ log n) points. To enforce the data structure to sample f (= points for each of the hard instance, we give each of the instances increasingly exponential weight. That is, we give the points the i-th instance T' weight for some constant 7 > 1, by inserting 7' copies of each of the points. Because the weight of the i-th instance is substantially greater than the sum of the weights of the previous instances, any (1 + eo-online coreset must essentially be a (1 + e)-coreset for the i-th instance, thus requiring 12 k points for the i-th instance. This reasoning extends to all of the 2(log n) instances, thereby giving a lower bound of 52 log n) points.
We first recall the following offline coreset lower bound by [25].
Theorem D.1. [25] For d θ ( let X e1. ea E R2d be the set of elementary vectors.
Let be a constant and let 01. am 2d with corresponding weights wi,..., Wm be weighted set P of points. Then there exists set of k unit vectors C= -i,...., E R2dd such that for m (#)
(1) Cost(C. C) Ed minje(M] |le: c,112 2=/2d 22/2 max(1,2/2) vkk.
(2) Cost(C, P) - w, minje(M) ||a, c, (1= 2d max(1,, (1, 2/2) Vdk).
We remark that the first property is due to Lemma 31 pf [25] and the second property is due to Lemma 33 and Lemma 34 of [25].
Let = θ (log )) Let = θ ( + be the dimension of the hard instance in Theorem D.1 and set d = yd', so that we can partition the space ag into groups of 2d coordinates.
We define stream by creating weighted instances of the hard instance defined in Theorem D.1. Each of the y hard instances will be embedded into a separate partition of 2d' coordinates of 2d Namely, the first instance consists of the vectors Cj,...,ez being inserted into the stream. By Theorem D. any (1 c)-corestt must contain Ω (+) points. The next instance consists of the
22

---

vectors e1-2d',... ......... ezd each being inserted T = 100 times into the stream. That is, after the vector e, arrives the stream from the first hard instance, then copies of 4142 arrive in the stream, followed by then 1 copies of 62+2d', and so forth. Due to the weights of these vectors, any (1 + e) coreset must essentially be a (1 + e--coreset for the second hard instance and thus contain !2 ( points with support in the second group of 2d' coordinates.
More generally, for each i [y]. the stream inserts t' copies of e1+2(i-1)d' followed by r'-1 copies of (2+)( and so on. The main intuition is that due to the weights of the i-th group of d' elementary vectors, an (1 )-noliie coreset must contain a (1 -ccoreset for the i-th hard instance. Moreover, since the (1 + -nnliine coreset must be a coreset for any prefix of the stream, then needs to be (1 E) ccooreset for each of the hard instances. Hence, the online coreset must contain log
7 2
= Ω
points.
log
100. For each integer >> O, let S; be the stream that consists of qi Lemma D.2. Let 1142(i-1j0, followwed by 7' copies of 0242(i-1)d'' and so on. Let be the consecutive copies of stream that consists of S₁ o o..... Then for each i, any (1 + onnoiieee coreset after the arrival of St must consist of i 12 ( points.
Proof. We prove the claim by induction on i. The base case of = follows from Theorem D.I.
Now suppose the claim holds for fixed 1. Let X, be the set of points that have arrived after S,, ie., X; = S1 o... o Sj. Let C,-1 be any (1 + =)-online coreset for S after the arrival of S,-1. Let P. be a set of weighted points sampled during stream S,, so that C, C₃-1 U P.. Since each point in S has weight r', then by scaling the first property of Theorem D.1, we have that there exists a set of l unit vectors U, C1,..n, Ck E IR2d such that
Cost(U,
min (b+2(a-1)) - cyl1 JE(
min ||e42((- - jElR
cyllē
2 (7 (2= - m =1, vdk).
In particular, the unit vectors U, C1,..., Ct have support supportentirelly in the i-th group of 2d coordinates in R.2d, By the same argument, there exists a set U- with the same properties the (i 1) group of 2d' coordinates in gdd
By the correctness of the online coreset, we have
Cost(Ui-1,, s Cost
(1 +
Σ (Ust(U,-
Since U,-1 consists of unit vectors and each substream S, consists of unit vectors, then we have Cost(Ui-1; 2d
Thus for & E 1),
i-1 Cost(U,-1, C-1) $2
Σ 7a) S 8d'
d'''
since 100. On the other hand, since U--1 has support entirely in the (i 1)-th group of 2d' coordinates and S; has support entirely in the i-th group of 2d' coordinates in 2d then
Cost(U:-1, 2 Cost(U;-1, 2 2'
Thus for C, to be a (1+ S-nnine coreset for E (0, 1), C. must sample additional points from X; on top of C,-1. Hence, P. O.
In particular, let P. consist of vectors y/....., .......,, 3m with weights Wi,..., Wm. Since P. * 0, then Cost(U,, C.) Cost(U, C- U.) < Cost(U,
23

---

If [ = 0 (g2), then by the second property of Theorem D.I, we have
Cost(U
Σ
min je[k]
wi 11 c,ll2 < -1 =)) - 20/2 max(1,2/2) vdle..
which together with Equation 1 contradicts the fact that C2 is (1 + e)-online coreset for X;. Therefore, we have |P induction,
2 ) Moreover, since P: has disjoint support from C;-1, then by
k E2
C = CC- = P = i.
Theorem 1.4. Let E (0, 1). For sufficiently large n, d, and A. there exists set X C. [ of points 21,...; En such that any (1 + e)-olinee coreset for k-means clustering on X requires Ω c logn) points.
Proof. Let y O (log /0 For each i [T]. construct the stream S as in the statement of Lemma D.2. Observe that |S,] d' t for 100 and under the settings of the parameter with the appropriate constant, the total length of the stream S = S Moreover, by Lemma D.2, any (1 + onnine coreset must store - ()) = S log n) points for n = (oly
S, is precisely n.
E
On the Proof of Theorem B.2
We remark that Theorem 1 of [27] is stated for sampling fixed number of points with replacement from each group, rather than sampling each point independently without replacement. By contrast, Theorem B.2 is stated for sampling each point independently without replacement. In this section, we briefly outline the proof of Theorem of [27] and how the analysis translates to the statement of Theorem B.2.
At a high level, the coreset construction of [27] first collects rings of an approximate solution of I points into groups, using similar approach to that described in Appendix B with 8 = 1. The algorithm then computes a coreset for each group first using a procedure GROUPSAMPLE and then using procedure SENSITIVITY AAMPLE for some of the points not considered by the first procedure. We briefly describe both procedures, as well as how to adapt them to setting where each point sampled independently and without replacement.
E.1 Adaptation of Group Sampling
The GROUPSAMPLE procedure of [27] samples fixed A₁ number of points from each group G with probability proportional to the contribution of each corresponding cluster of the point to the group. That is, given clusters Ci,..., Cj induced by A G, GroUPSAMPin then performs A rounds of sampling. Each round samples single point, where point p C, is sampled proportional to Cost(Cr..A) and rescaled appropriately. Then GROUPSAMPLE offers the following guarantees:
C.).Cost(GG.A)
Lemma E.1 (Lemma 2 of (271). Let (X, dist) be metric space, k, z be positive integers, G be group of clients and A be an a-approximate solution (k, cllusttrrin on G that:
For every cluster Ò induced by A G, all points of C contribute the same cost A up to factor of
For all clusters Ò induced by A G, we have that Cost(G.A < Cost((,,A) A).
2h
Let be an A-approximate centroid set for (k., cllusstrrinn on G.
Then there exists procedure GROUPSAMPLE that constructs set Ω of size
A 0
max(a², az)) log 20(z 20(zlog=) log min(=?,e*)
log |C] + log log 1
+ log )

---

such that with high probabiliry, it simultaneously holds for all sets S of k centers that [Cost/G, S) - CCost((,, S (a) (Cost(G, Cost(G,,A),
We outline the high-level approach of the proof of Lemma E. and how can can adjusted for an (ar -appppppxi solution A. as well as process that samples each point independently without replacement, rather than using A rounds as GROUPSAMPLE.
The proof of Lemma E.1 involves further partitioning the points of G into three subsets, based on the cost induced by the point. Namely, given set S of k centers, a point p group G is categorized as tiny, interesting, huge, depending have a small overlap to allow slack in the proof). [27] applies standard Chernoff bounds show that the number of sampled points is well-concentrated around its expectation and then applies Bernstein's 's inequality to show that the clustering costs of the tiny points, the interesting points are well-concentrated around their expectations. In particular, they show that the expected number of sampled points from each cluster C2 is
Cost(p, .S) (though the interesting and huge points actually
Ar Cosu(C,, A)
A1
Cost( (
2k
due to the assumption that for all clusters induced by A on G, we have that Cost(G.A) A),
2h
We first remark that if A is an (a, B) approxxmmae solution rather than an a-approximate solution, i.e., if A has Sk centers rather than & centers, then the definition of the rings and groups would instead insist that for all clusters Č induced by A on G, we have that (ost(G.A) 2 I Co, Then by oversampling A by a factor of B, i.e., sampling 3A points would ensure that the expected number of sampled points from each cluster C; would be
BA1 Cost,(ii, Cost(G,,A)
3A
A1
2
2.k
k
It then remains to argue the correctness of sampling each point independently without replacement rather than a fixed BA₁ number of points, which simply holds by adjusting the applications of the Chernoff bounds and Bernstein's inequality so that there is separate random variable for each point in the input rather than for each of the A₁ rounds.
E.2 Adaptation of Sensitivity Sampling
The SENSITIVITYSAMPE procedure of [27] samples a fixed A2 number of points from each group G with probability proportional the contribution of the point. Specifically, SENSITIVITYS, AMPLE then performs A2 rounds of sampling, where each round samples point in the group G with probability (ost(p..A)
proportional to Co and rescales the sampled point appropriately. Then SENSITIVITYSAMPER offers the following guarantee:
Lemma E.2 (Lemma 3 of [27]). Let (X, dist) be a metric space, k, be positive integers, and A be an a-approximate solution to (ks cluuusttri on G. Let C be an A-approximate centroid set for (k, cluusterin G. Let G be either group Go or G Then there exists procedure SENSIIIVIYSAAPPL that constructs a set size
20(alor loR a) "log"""
21
Ao =
lo |C| + log log logn)
e2
such that with high probability, it simultaneously holds for all sets of centers that
[Cot(GG,5) (2, s az log
(Cost + Cost(G, A).
We outline the high-level approach of the proof of Lemma E.2 and how can it can adjusted for an (ox, ap-roopoeee solution A, as well as a process that samples each point independently without replacement, rather than using A2 rounds SENSIIIVITYSAMPLL
25

---

The proof of Lemma E.2 partitions the points of G into two categories, based on the cost induced by the point. Given set S of & centers, the close points are the points p in G that have Cost(p, p. S) - 4 Cost(p, A). The far points are the remaining points in G, i.e. the points p in G with Cost S)
4 Cos A).
[27] applies Bernstein's 's inequality to show that the clustering cost of the close points is well- concentrated around their expectations. We can again adjust the application of Bernstein's 's inequality so that there is a separate random variable for each point in the input rather than for each of the A2 samples.
To handle the far points, [27] again uses Bernstein's 's inequality to show that with high probability, the clustering points of these points with respect to S can be replaced with the distance to the closest center e E A plus the distance from e to the closest center in S. Conditioned on this event, the latter distance can then be charged to the remaining points of the cluster from the original dataset, i.e., the remaining points of the cluster not necessarily restricted to group G, which are significantly more numerous and already paying similar value in S. In particular, Bernstein's inequality utilizes the fact that the second moment of the estimated cost of a cluster C' is at most
Cost Cost(G,A) A) Cost(Cnn,, A) S A2
2k A
(Cost(C
for 3 = 1. Thus for general B, we recover the same guarantee by oversampling A2 by a factor of 3, i.e., sampling BA₂ points would ensure that the second moment would be at most 26 Cost (CnG, A). It x
then remains to argue the correctness of sampling each point independently without replacement rethoettellacceentt rather than fixed BA₂ number of points, which again holds by adjusting the application of Bernstein's inequality so that there is a separate random variable for each point in the input rather than for each of the A2 rounds.
F
Additional Experiments on Synthetic Data
We first describe the methodology and experimental setup of our empirical evaluation on synthetic dataset before detailing the experimental results. To emphasize the benefits of our algorithm against worst-case input, we generate a synthetic dataset that would fully capture the failure cases of previous baselines.
Dataset. We generated our dataset X consisting of 200, 001 points on two-dimensional space so that 100, 000 points were drawn from spherical Gaussian with standard deviation 2.75 centered at (-10, 10) and 100, 000 points were drawn from a spherical Gaussian with standard deviation 2.75 centered at (10,- 10). The final point of X was drawn from a spherical Gaussian with standard deviation 2.75 centered at (100000, 100000). Thus by construction of our synthetic dataset for is = 3, the optimal centers should be close to (-10, 10). (10. 10), and (100000, 100000). We then create the data stream S by prepending two additional points drawn from spherical Gaussians with standard deviation 2.75 centered at (-100000, 100000) and 100000, 100000) respectively. We set the window length to be 200, 001 in accordance with the "true" data set, so that the first two points of the stream of length 200, 003 will be expired by the data stream.
Experimental setup. For each of the instances of Lloyd's algorithm, either on the entire dataset X or the sampled coreset C, we use iterations using the k-means++ initialization. In this case, the offline Lloyd's algorithm requires storing the entire dataset X in memory and thus its input size is 200, 001 points. By comparison, we normalize the space requirement of the sublinear-space algorithms by permitting each algorithm to store m {3, 4, 5, 6, 7, 8, 9, 10, 11, 12) points. Note that since k 3, it would not be reasonable for to have fewer than 3 points. We then run Lloyd's algorithm on the coreset C, with 3 iterations using the k-means++ initialization.
By construction of our dataset, we generally expect the uniform sampling algorithm uni to be stable across the various values of m but perform somewhat poorly, as it will sample points from the large clusters but it will miss the point generated from the Gaussian centered at (100000, 100000). Since in our construction the stream S only contains two more points than the dataset X, the histogram- based algorithm hist will not delete any points. Thus, the resulting coreset C generated by hist is somewhat likely contain the points generated from the Gaussians centered at (-100000, 100000)
26

---

and (-100000, - 1000000) and can perform poorly on the synthetic dataset in these cases. Finally, since we allow the last point of the stream to be the single point of X far from the two large clusters, then the importance sampling based algorithm imp will sample the last point with high probability once any points of C have been expired. Hence by the construction of our stream, we expect imp to perform well.
avg.
10
29
avg.
23
avg
10
2M
Clustering cost
2
Clusteiig cast
1014
avg. hist. errs
uni. errs.
histog range
Imp. erss
10
avg. offl. errs
227
24
28
10
12
Numbar of clustors
Numbar samplas
(a) Comparisons for varying
(b) Comparisons for varying m.
Fig. 3: Comparison of average clustering costs made by uniform sampling, histogram-based algorithm, and our coreset-based algorithm across various settings of space allocated to the algorithm, given a synthetic dataset. For comparison, also include the offline k-means++ algorithm baseline, though it is inefficient because it stores the entire dataset. Ranges are not plotted because they would not be visible.
Experimental results. For each choice of m and k we ran each algorithm 50 times and tracked the resulting clustering cost. As expected by our construction, our algorithm performed significantly better than the other sublinear-space algorithms. In fact, even though our algorithm was only permitted memory size m {3, 4, 5, 6, 7,8, 9, 10, 11, 12). our algorithm was quite competitive with the offline Lloyd's algorithm, which used memory size 200, 001, i.e., the entire dataset. For A 2 uniform sampling performed relatively poorly but quite stably. because although it never managed to sample the point generated from the Gaussian centered (100000, 100000). the two other Gaussian distributions were sufficiently close that any sampled point would serve relatively good center for points generated from the two distributions. Similarly, for fixed k 3 in Figure 3b, the importance sampling approach used by histogram- based algorithms performed the worse, by multiple orders of magnitude. We expect this is because we did not delete the points in S X from C' and thus the resulting Lloyd's algorithm distributions that induced X. A more optimized fine-tuned histogram- based algorithm would have searched for parameters that govern when to delete points from S \ X, which have reduced the algorithm down to our main algorithm. We plot our results in Figure
C' moved the centers far away from the centers of the Gaussian
27


Reviews:
[{"review_id": "1Orc9Si4vx", "reviewer": "Reviewer_8X17", "summary": "The paper proposes an near-optimal algorithm to build (1+$\\epsilon$)-online coreset for k-clustering problem, and apply it to the sliding window model. The (near) optmality is established by a matching lower bound, also proved in the paper.\n\nA coreset is a compression of a dataset, such that any clustering centers will induce similar cost over the coreset and the original dataset. The (insertion-only) online coreset problem aims to build a coreset incrementally for a data stream, such that the coreset property (i.e., cost approximation) holds at any time point\n\nThe main algorithm borrows lots of ideas from paper [24] (\"*A New Coreset Framework for Clustering*\"), which proposes a framework for building (offline) coresets and can be roughly described as follows:\n1. Given a dataset, find a constant-approx clustering solution $A$ on it.\n2. For each cluster induced by $A$, divide it into rings by distance to the center, such that all points in a same ring have roughly the same distance to the center. \n3. Group rings at the same level from each cluster, then do importance sampling on the group. The sampled points (with scaled weights) will be the output coreset.\nFor analysis, [24] shows that: as long as you can find a small \"$A$-approximate centroid\" $C$ (which is essentially something like a $\\epsilon$-net restricted to part of the dataset), then you can have a small coreset.\n\nThe paper essentially adapts the algorithm from [24] to the online setting\n1. To get an constant-approx clustering in the online setting, the paper adopts a bi-criteria variant of Meyerson's algorithm for online facility location. Here the algorithm could produce more than k centers, but this is not an issue for bounding the coreset size since it only adds a constant factor.\n2. The importance sampling step is mostly the same as described before, just in an online fashion. This gives the online coreset construction.\n3. Finally, to apply it in the sliding window model, the paper breaks the input stream into blocks, then apply the online coreset construction in the reverse order on each block, and merge each block's coreset also in the reverse order (and keep only those within the window).\n\nI don't have time to look into the details of the lowerbound construction, however, it appears to be an adaptation of the offline bound from [23] (\"*Towards optimal lower bounds for k-median and k-means coresets*\").\n", "questions": "Some other comments.\n- I would recommend the authors to at least give a sketch of [24]'s idea before describing the RingSample algorithm.\n- I recommend to have \"coreset\" formally defined somewhere.\n- The notation $\\mathrm{Cost}(X,Y)$ is never formally defined in the paper. Although I can guess what it is, it's better to define it somewhere as it is used frequently.\n- line 224: Same as above for $\\mathrm{Cost}_{|S|\\leq k}(X, S)$.\n- line 227-245: Many symbols defined here are not used at all in the main body. Please move them to the supplementary where they are actually used in the proof. Here they only distracts readers' attention.\n- line 233-236: $R_I(C_i)$ and $R_O(C_i)$ have the same definition.\n- line 243: I would write $G_{j, \\mathrm{min}}$ and $G^O_b$ as union of some $R_{i,j}$'s rather than introducing a \"$x$\" there. It feels like you can take some $x$ from a $R_{i,j}$ while in fact it's all-or-nothing.\n- line 248: Lemma 2.2: what is $G$?\n- Section 3 (Experiment): My suggestion to the authors is to throw the experiment section to appendix or simply remove it, so you can have more space to enhance the readability of the theory part.\n", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "I think the main contribution is mostly in the theory side. The problem studied is important and well-motivated. It's nice to see that the result of [23] and [24] can be ported to the online setting. This requires quite some non-trivial work and the paper is able to identify an optimal choice of parameters, which results in an asymptotically optimal algorithm.", "weaknesses": "As mentioned in the Summary, the main idea seems to be an (arguably) straightforward adaptation of [24], which somewhat limits the novelty.\n\nAlso, I feel the experiment section is kinda redundant or even harmful to the paper's contribution. The proposed algorithm is not acutally implemented (in particular, the RingSample Alg, which is a core part of the proposed algorithm). It seems that the performance gain comes only from discarding points outside the sliding window, especially when compared with the histogram-based algorithm.\n- If the authors are able to implement their algorithm in a more meaningful way, and if it indeed produces better result on some realworld dataset, then I would be happy to increase my rating. Otherwise, I feel it's better to just remove the experiment section completely and present the paper as a theoretical contribution.\n\nLastly, I believe the writing can be improved a lot. It seems the draft may have been finalized hastily, with instances of noticeable cutting and pasting to meet the page limit. This renders the main body insufficiently self-contained and challenging for readers unfamiliar with [24] (and not dive into the appendix proof). For example, it's hard to get much intuition why RingSample algorithm (Alg. 1) works unless a reader already knows the result of [24].\n\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> As mentioned in the Summary, the main idea seems to be an (arguably) straightforward adaptation of [24], which somewhat limits the novelty.\n\nOur main algorithm utilizes (1) a framework for sliding window algorithms using a new randomized online coreset construction along the lines of [8], (2) an online version of the coreset construction of [24], and (3) a consistent assignment across all times of the stream through an online facility location argument in the style of [30]. Although none of these steps are particularly complicated, developing the correct variations for each step and putting them together in a non-trivial manner is fairly novel/technical, e.g., the long line of previous work for clustering on sliding windows has missed this approach. \n\n> Also, I feel the experiment section is kinda redundant or even harmful to the paper's contribution. The proposed algorithm is not acutally implemented (in particular, the RingSample Alg, which is a core part of the proposed algorithm). It seems that the performance gain comes only from discarding points outside the sliding window, especially when compared with the histogram-based algorithm. \n\nIndeed, the main focus of our paper should be on the theoretical perspective of the algorithm and thus our experiments serve as a simple proof-of-concept illustrating the advantages of sampling-based algorithms over histogram-based algorithms. We will clarify the purpose of our experiments more clearly in the final version of our paper. \n\n> If the authors are able to implement their algorithm in a more meaningful way, and if it indeed produces better result on some realworld dataset, then I would be happy to increase my rating. Otherwise, I feel it's better to just remove the experiment section completely and present the paper as a theoretical contribution.\n\nWe can move the experiments to the appendix in the full version so that the main body focuses on the theoretical contributions of the paper. \n\n> Lastly, I believe the writing can be improved a lot. It seems the draft may have been finalized hastily, with instances of noticeable cutting and pasting to meet the page limit. This renders the main body insufficiently self-contained and challenging for readers unfamiliar with [24] (and not dive into the appendix proof). For example, it's hard to get much intuition why RingSample algorithm (Alg. 1) works unless a reader already knows the result of [24].\n\nThanks for the feedback. Much of the intuition and formalization for the coreset construction of [24], as well as our modifications, is currently in the appendix. If the paper is accepted, we will rework this intuition and incorporate it into the additional content page that is allowed for the main body of the paper. \n\n> line 248: Lemma 2.2: what is $G$?\n\nWe will clarify $G$ to denote any fixed group, so that the first statement of Lemma 2.2 should read \"Let $C$ be an $A$-approximate centroid set for any fixed group $G$\""}, {"review_id": "ksifrUZ0Y5", "reviewer": "Reviewer_P4Gj", "summary": "This paper studies $k$-means and $k$-median clustering in the sliding window, and proposes an $(1+\\varepsilon$)-approximation algorithm on the top of an coreset maintained through the stream. The space complexity is roughly $k/\\text{poly}(\\varepsilon) \\cdot \\text{poly}\\log n$ where $n$ is the number of points, coming together with an nearly-tight lower bound.", "questions": "- Will the codes be made public?\n\n- Can you add an open problem section?", "limitations": "I would appreciate this as a basically-complete theory work. There are some limitations on the experiments, but not a hurdle on assessing the contribution of this paper.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper is well-written in general, most parts are clear and well-organized.\n- The results are interesting and significant. I did not read the entire proof, but checking the key steps convince me the result should be correct. I am happy to go back to proof details if any concern comes up.\n- It is a plus for a theory paper to have experiments. The space consumption is reduced a lot with some compromise on the clustering performance.", "weaknesses": "- I am confused by line 388 389, it seems that the window size is too close to the stream size. Though theoretically the window size is not an important parameter, but doing this converges back to the streaming model.\n- After staring at it for a while, I do not think either of the algorithm or lower bound applies to the $k$-center clustering. Then is it OK to have $k$-clustering as in the title? The authors can either convince me this result holds / has impact on $k$-center clustering, or show me a bunch of work that does not include $k$-center in $k$-clustering.\n- I think it is good to make clear of the notation, especially when it first appears. In the abstract, maybe clarify what $z, \\Delta$ is. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> I am confused by line 388 389, it seems that the window size is too close to the stream size. Though theoretically the window size is not an important parameter, but doing this converges back to the streaming model.\n\nWe remark that the window size was set rather close to the stream size in our experiments as a simple proof-of-concept where sampling-based algorithms demonstrate better performance than histogram-based algorithms. We believe that more general datasets with different settings for window size and stream size can also be constructed so that sampling-based algorithms demonstrate better performance than histogram-based algorithms.\n\n> After staring at it for a while, I do not think either of the algorithm or lower bound applies to the $k$-center clustering. Then is it OK to have $k$-clustering as in the title? The authors can either convince me this result holds / has impact on $k$-center clustering, or show me a bunch of work that does not include $k$-center in $k$-clustering\n\nExamples of works that do not include $k$-center in $k$-clustering are listed below. Nevertheless for the sake of clarity, we can change the title to \"Near-Optimal Clustering in the Sliding Window Model\" if permitted. \n\nArtur Czumaj, Guichen Gao, Shaofeng H.C. Jiang, Robert Krauthgamer, Pavel Vesely: Fully Scalable MPC Algorithms for Clustering in High Dimension. CoRR abs/2307.07848 (2023)\n\nYecheng Xue, Xiaoyu Chen, Tongyang Li, Shaofeng H.-C. Jiang: Near-Optimal Quantum Coreset Construction Algorithms for Clustering. CoRR abs/2306.02826 (2023)\n\nSayan Bandyapadhyay, Fedor V. Fomin, Tanmay Inamdar: Coresets for Clustering in Geometric Intersection Graphs. SoCG 2023: 10:1-10:16\n\nLingxiao Huang, Shaofeng H.-C. Jiang, Jianing Lou, Xuan Wu: Near-optimal Coresets for Robust Clustering. ICLR 2023\n\nVincent Cohen-Addad, Alessandro Epasto, Vahab Mirrokni, Shyam Narayanan, Peilin Zhong: Near-Optimal Private and Scalable $k$-Clustering. NeurIPS 2022\n\n> I think it is good to make clear of the notation, especially when it first appears. In the abstract, maybe clarify what $z,\\Delta$ is.\n\nThanks for the suggestion. We will clarify in the abstract that $z$ is the power of the distance in the cost function and $\\Delta$ is the length of the grid on which the points lie. \n\n> Will the codes be made public?\n\nYes, we will upload the code to a public repository (and hopefully it should already be accessible in the supplementary material). \n\n> Can you add an open problem section?\n\nYes, we will add a conclusion that both summarizes our contributions, as well as provide directions for future work. \n\n> I would appreciate this as a basically-complete theory work. There are some limitations on the experiments, but not a hurdle on assessing the contribution of this paper.\n\nThanks for the feedback! We can move the experiments to the appendix in the full version so that the main body focuses on the theory aspects of the paper. "}, {"review_id": "Cch0WUMKjd", "reviewer": "Reviewer_YLu7", "summary": "This paper studies the $k$-clustering problem in sliding window model. In sliding window model, a window of size $W$ is given to capture the most recent $W$ updates in the stream, where good clustering approximation should be maintained in the window with small space complexity. In previous work, in order to achieve an $(1+\\epsilon)$ approximation for $(k,z)$-clustering problem in sliding window, a space complexity of $\\frac{kd+d^{Cz}}{\\epsilon^3}polylog(W,\\Delta,\\frac{1}{\\epsilon})$ for some constant $C \\ge 7$. In this work, the authors propose a coreset-based method, which gives an $(1+\\epsilon)$-approximation for the $(k,z)$-clustering problem in sliding window model with space complexity $\\frac{k}{min(\\epsilon^4,\\epsilon^{2+z})}polylog(\\frac{n\\Delta}{\\epsilon})$, which is independent of the window size and nearly matches the lower bound of the space used by the offline coreset construction.", "questions": "1. It seems that the $O(log\\Delta)$ dependence on the space complexity comes from the Meyerson approach (for obtaining the consistent approximation), where a guess-and-double process is used to obtain an estimation of the cost of an optimal solution. Is the $O(log\\Delta)$ term necessary in the proposed method and is there any other method that can avoid guessing $O(log\\Delta)$ times for the optimal clustering cost (for example by calling a single-criteria approximation algorithm with large approximation ratio to serve as the upper bound for optimal clustering cost)? \n\n2. Can the authors explain more about the challenges when directly applying the reduce and merge method for each block of the divided data points in a stream without using an \"inverse\" operation?\n\n3. I am curious about whether, in the sliding window model, the space complexity is more critical to consider compared to the time complexity. As I am not very familiar with this model, I would appreciate some insights on this matter.", "limitations": "Since this is mainly a theoretical work, I don't think there is potential negative societal impact of this work. ", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. The presented result significantly improves the space complexity of previous work with $(1+\\epsilon)$-approximation guarantee on the clustering quality in sliding window model. Besides, this is the first approximation result that can achieve a space complexity independent of the window size $W$. In practical settings, since $\\Delta$ is usually assumed to be bounded by $poly(n)$, the presented result can nearly match the lower bound space complexity required for any $(1+\\epsilon)$-online coreset construction for $(k,z)$-clustering problem.\n\n2. The extensive experimental results on real world datasets show that the proposed method is more efficient than previous ones.", "weaknesses": "1. The techniques used in this paper seem to rely heavily on the current SOTA method for offline coreset construction [1] (using ring structures and independent sampling method) and the consistent approximation scheme proposed by Meyerson et al. [2].\n\n2. The challenges for merge and reduce operations is not discussed comprehensively in the literature.\n\n[1] Adam Meyerson. Online facility location. In 42nd Annual Symposium on Foundations of Computer Science, FOCS, pages 426–431. IEEE Computer Society, 2001.\n\n[2] Vincent Cohen-Addad, Kasper Green Larsen, David Saulpic, and Chris Schwiegelshohn. Towards optimal lower bounds for k-median and k-means coresets. In STOC ’22: 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 1038–1051, 2022.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> The techniques used in this paper seem to rely heavily on the current SOTA method for offline coreset construction [1] (using ring structures and independent sampling method) and the consistent approximation scheme proposed by Meyerson et al. [2].\n\nOur main algorithm utilizes (1) a framework for sliding window algorithms using a new randomized online coreset construction along the lines of [8], (2) an online version of the coreset construction of [24], and (3) a consistent assignment across all times of the stream through an online facility location argument in the style of [30]. Although none of these steps are particularly complicated, we believe that developing the correct variations of each step and putting them together in the correct manner is fairly novel/technical, e.g., the long line of previous work for clustering on sliding windows has missed this approach. \n \n> It seems that the $O(log\\Delta)$ dependence on the space complexity comes from the Meyerson approach (for obtaining the consistent approximation), where a guess-and-double process is used to obtain an estimation of the cost of an optimal solution. Is the $O(log\\Delta)$ term necessary in the proposed method and is there any other method that can avoid guessing $O(log\\Delta)$ times for the optimal clustering cost (for example by calling a single-criteria approximation algorithm with large approximation ratio to serve as the upper bound for optimal clustering cost)? \n\nWhile our lower bound shows that an $\\Omega(\\log n)$ dependence is necessary for any online coreset, it is indeed unclear whether an $O(\\log\\Delta)$ dependence is necessary. We leave this as a great question for future work. \n\n> The challenges for merge and reduce operations is not discussed comprehensively in the literature...Can the authors explain more about the challenges when directly applying the reduce and merge method for each block of the divided data points in a stream without using an \"inverse\" operation?\n\nThe main barrier is that existing merge-and-reduce frameworks using coresets do not handle the implicit deletions of the sliding window model. Thus we instead show that the existing coreset construction of [1] can be modified in an online manner, and then show that there exists a corresponding merge-and-reduce framework for online coresets.\n\n> I am curious about whether, in the sliding window model, the space complexity is more critical to consider compared to the time complexity. As I am not very familiar with this model, I would appreciate some insights on this matter.\n\nYes, in the sliding window model, including the more specific streaming model, the main quantity of interest in previous work is the space complexity, though considerations for time complexity should be optimized as much as possible. Towards that end, we remark that the calculations of the sampling probailities of our algorithm only require computing the distance of each point to a number of centers, as well as tracking the number of points in each ring/group so far. Thus, our algorithm can be efficiently implemented, and has a small polynomial running time. "}, {"review_id": "ZiCK6H51yJ", "reviewer": "Reviewer_o3G5", "summary": "This paper proposes the first near-optimal $(1+\\varepsilon)$-approximation algorithm for $(k, z)$-clustering problem in the sliding window model. The core part is the $(1+\\varepsilon)$-coreset of $(k, z)$-clustering in the sliding window model which is based on an online coreset algorithm for $k$-clustering problem. This paper gives strict proof for the proposed algorithm and experimental results manifest its efficiency. In short, the theory aspect of this paper is solid enough. ", "questions": "In Line 92-93, Theorem 1.1 presents the word space $\\frac{k}{\\min(\\varepsilon^4, \\varepsilon^{2+z})} \\text{poly} \\log \\frac{n \\Delta}{\\varepsilon}$. For $k$-median and $k$-means, $z$ is equal to $1$ and $2$ respectively. No matter $z$ is $1$ or $2$, the space should be $\\frac{k}{\\varepsilon^4} \\text{poly} \\log \\frac{n \\Delta}{\\varepsilon}$ since $\\varepsilon \\in (0, 1)$. How can you achieve $\\frac{k}{\\varepsilon^2} \\text{poly} \\log \\frac{n \\Delta}{\\varepsilon}$? In addition, for $(k, z)$-clustering, $z=1$ does not correspond to $k$-median when $\\mathrm{dist}$ represents the Euclidean distance, since $k$-median is $\\ell_1$-norm. ", "limitations": "See Weaknesses and Questions. ", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "(1) This paper gives the first $(1+\\varepsilon)$-approximation algorithm for $(k, z)$-clustering in the sliding window, which improves the existing results in two aspects including accuracy and space.  \n(2) The space $\\frac{k}{\\min (\\varepsilon^4, \\varepsilon^{2+z}) }$ of $(1+\\varepsilon)$-coreset for $(k, z)$-clustering in the sliding window almost matches the lower bound $\\Omega \\left(\\frac{k}{\\varepsilon^2} \\log{n}\\right)$.  \n(3) Strict proof is provided and experimental results are sufficient.  \n(4) The paper is well-written and well-organized. ", "weaknesses": "(1) Some symbol is not explained, like $[ \\Delta ]^d$.  \n(2) The merge-and-reduce framework lacks some citations. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> Some symbol is not explained, like $[\\Delta]^d$.\n\nWe will clarify that $[\\Delta]^d$ means that each of the $d$ coordinates of each point must lie within $\\{1,\\ldots,\\Delta\\}$. \n\n> The merge-and-reduce framework lacks some citations.\n\nWe will add references to previous work that use the merge-and-reduce framework. \n\n> No matter $z$ is $1$ or $2$, the space should be $\\frac{k}{\\varepsilon^4}\\text{poly} \\log\\frac{n\\Delta}{\\varepsilon}$\nsince $\\varepsilon\\in(0,1)$. How can you achieve $\\frac{k}{\\varepsilon^2}\\text{poly} \\log\\frac{n\\Delta}{\\varepsilon}$?\n\nWe emphasize that our results do not claim to achieve $\\frac{k}{\\varepsilon^2}\\text{poly} \\log\\frac{n\\Delta}{\\varepsilon}$ words of space but rather $\\frac{k}{\\varepsilon^{z+2}}\\text{poly} \\log\\frac{n\\Delta}{\\varepsilon}$ words of space. Moreover, in light of an $\\Omega\\left(\\frac{k}{\\varepsilon{2+z}}\\log n\\right)$ lower bound by [41], it is not possible to achieve $\\frac{k}{\\varepsilon^2}\\text{poly} \\log\\frac{n\\Delta}{\\varepsilon}$. \n\n> In addition, for $(k,z)$-clustering, $z=1$ does not correspond to $k$-median when $\\text{dist}$ represents the Euclidean distance, since $k$-median is $\\ell_1$-norm.\n\nSince $(k,z)$-clustering is a general definition that is the sum of the $z$-th power of the distances, then $k$-median with the Euclidean distance is the sum of the Euclidean distances. Nevertheless, $k$-median is also well-defined when the underlying distance is the Manhattan distance, though this setting is beyond the current scope of our paper. "}]

Author rebuttal:
We thank the reviewers for their thoughtful comments and valuable feedback. We appreciate the positive remarks, such as

- The problem studied is important and well-motivated. (Reviewer 8X17)
- It's nice to see that the result of [23] and [24] can be ported to the online setting. (Reviewer 8X17)
- The paper is able to identify an optimal choice of parameters, which results in an asymptotically optimal algorithm. (Reviewer 8X17)
- The paper is well-written in general, most parts are clear and well-organized. (Reviewer P4Gj)
- The results are interesting and significant...checking the key steps convince me the result should be correct. (Reviewer P4Gj)
- It is a plus for a theory paper to have experiments. The space consumption is reduced a lot with some compromise on the clustering performance. (Reviewer P4Gj)
- The presented result significantly improves the space complexity of previous work with $(1+\epsilon)$-approximation guarantee on the clustering quality in sliding window model. (Reviewer YLu7)
- In practical settings, since $\Delta$ is usually assumed to be bounded by $\text{poly}(n)$, the presented result can nearly match the lower bound space complexity required for any $(1+\epsilon)$-online coreset construction for $(k,z)$-clustering problem. (Reviewer YLu7)
- The extensive experimental results on real world datasets show that the proposed method is more efficient than previous ones. (Reviewer YLu7)
- The space $\frac{k}{\min(\varepsilon^4,\varepsilon^{2+z})}$ of $(1+\varepsilon)$-coreset for $(k,z)$-clustering in the sliding window almost matches the lower bound $\Omega\left(\frac{k}{\varepsilon^2}\log n\right)$. (Reviewer o3G5)
- Strict proof is provided and experimental results are sufficient. (Reviewer o3G5)
- The paper is well-written and well-organized. (Reviewer o3G5)

We provide our responses to the initial comments of each reviewer below. We hope our answers resolve any remaining questions, and we would be happy to participate in any conversations during the discussion phase. 

Meta-review: All reviewers appreciate the important problem of k-clustering in a natural setting: streaming with sliding windows. The paper gives a new algorithm with improved memory bound and fast runtime. Additionally the algorithm performs well in experiments.
Decision: Accept (poster)