# _k_-Center Clustering with Outliers in Sliding Windows
## 3 \(k\)-Center with \(z\) Outliers
### Weighted Coreset Construction
#### 3.1.1 Algorithm
It is easy to argue that Properties 2 and 3 continue to hold for \(L_{r}^{\prime}\). Let us now show that they also hold for histogram \(M\) at the end of the procedure. As for Property 2, consider two adjacent pairs \((t_{r,j},c_{r,j})\) and \((t_{r,j+1},c_{r,j+1})\) in \(M\), with \(c_{r,j}>(1+\lambda)c_{r,j+1}\). Then, two pairs with the same timestamps and weights must exist in \(L_{r}^{\prime}\), and we can argue that these two pairs must be adjacent in \(L_{r}^{\prime}\), and hence their weights must differ by 1, since Property 2 holds for \(L_{r}^{\prime}\). Indeed, if the two pairs were not adjacent in \(L_{r}^{\prime}\), then at least one pair with a timestamp between \(t_{r,i}\) and \(t_{r,j+1}\) must have been removed in the for loop of updateHistogram(\(L_{r}\)). However, this is not possible, because, due to the way the loop operates, this would ensure that \(c_{r,j}\leq(1+\lambda)c_{r,j+1}\). Finally, Property 3 is enforced by the for loop of updateHistogram(\(L_{r}\)). The following theorem states the main properties of the weighted coreset \(T\) computed by our algorithm. Theorem 4.1: _At any time \(t\), the weighted coreset \(T\) returned by extractCoreset(\()\) is a \(4(1+\beta)\)-coreset of size \(O(k+z)\) for the current window \(W\) w.r.t. the \(k\)-center problem with \(z\) outliers. Moreover, for each point \(r\in T\), we have \(w(r)/(1+\lambda)\leq\bar{w}(r)\leq w(r)\)._

Proof. : Recall that \(T=R_{\hat{\gamma}}\cup O_{\hat{\gamma}}\), where \(\hat{\gamma}\) is the minimum guess for which the following two conditions are verified: \(|A_{\hat{\gamma}}|\leq k+z\), and the greedy selection strategy of [13] applied to \(A_{\hat{\gamma}}\cup R_{\hat{\gamma}}\cup O_{\hat{\gamma}}\) returns a set \(C\) of \(k+z\) points such that \(\text{dist}(p,C)\leq 2\hat{\gamma}\), for every \(p\in A_{\hat{\gamma}}\cup R_{\hat{\gamma}}\cup O_{\hat{\gamma}}\). It is easy to see that these two conditions are surely verified for any \(\gamma\geq r_{k+z}^{*}(W)\). Therefore, considering the density of the guesses in \(\Gamma\), we must have \(\hat{\gamma}\leq(1+\beta)r_{k+z}^{*}(W)\). By Lemma 1, we have \(|T|=O(k+z)\) and \(\max_{p\in W}\text{dist}(p,T)\leq 4\hat{\gamma}\), which implies \(\max_{p\in W}\text{dist}(p,T)\leq 4(1+\beta)r_{k+z}^{*}(W)\leq 4(1+\beta)r_{k,z}^{*}(W)\). We now show the relation concerning the approximate weights \(\bar{w}(r)\). Recall that, for each \(r\in T\), the value \(\bar{w}(r)\) is set equal to \(c_{L_{r}}\), which is the weight component of the pair in \(L_{r}\) with the smallest timestamp \(\geq t-|W|+1\). Let \((t_{r,i},c_{r,i})\) be the pair of \(L_{r}\) such that \(c_{r,i}=c_{L_{r}}\). If \(i>1\), then the relation \(c_{r,i}\leq w(r)\leq c_{r,i-1}\) must hold, and Property 2 of Lemma 2 ensures that \(c_{r,i-1}\leq c_{r,i}(1+\lambda)\) or \(c_{r,i-1}=c_{r,i}+1\). In the former case, we have \(w(r)/(1+\lambda)\leq c_{r,i}=c_{L_{r}}\leq w(r)\), whereas, in the latter case, it is easy to see that \(c_{L_{r}}=w(r)\). If, instead, \(i=1\), it is easy to see that \(c_{L_{r}}=w(r)\), since the first pair of the histogram is always relative to the arrival of the attraction point \(a_{\gamma}(r)\), and hence the weight of such pair accounts for all points assigned to it. The following theorem analyzes the space and time performance of our coreset construction strategy. Theorem 4.2: _The data structures used by our coreset construction strategy require a working memory of size \(O\left(\log_{1+\beta}(d_{\max}/d_{\min})\cdot(k+z)\cdot\log_{1+\lambda}(|W|)\right)\). Moreover, Procedure update can be implemented to run in time_

\[O\left(\log_{1+\beta}(d_{\max}/d_{\min})\cdot\left((k+z)+\log_{1+\lambda}(|W|) \right)\right),\]

_whereas Procedure extractCoreset can be implemented to run in time_

\[O\left(\log_{1+\beta}(d_{\max}/d_{\min})\cdot(k+z)^{2}\right).\]_If binary search is used to find the value \(\hat{\gamma}\), the running time of extractCoreset decreases to_

\[O\Big{(}\log(\log_{1+\beta}(d_{\max}/d_{\min}))\cdot(k+z)^{2}\Big{)}.\]

Proof.