# _k_-Center Clustering with Outliers in Sliding Windows
## 3 \(k\)-Center with \(z\) Outliers
### Weighted Coreset Construction
#### 3.1.1 Algorithm
For a stream \(S\) of doubling dimension \(D\), suitable data structures can be maintained, from which, at any time \(t\), a weighted \(\delta\)-coreset \(T\) of size \(O((c/\delta)^{D}(k+z))\) for a fixed constant \(c\) can be extracted such that, for each \(p\in W\), there exists a proxy \(\pi(p)\in T\) with_

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

_Moreover, for each \(r\in T\), an approximate weight \(\tilde{w}(r)\) can be computed, with \(w(r)/(1+\lambda)\leq\tilde{w}(r)\leq w(r)\), where \(w(r)=|\{p\in W:\pi(p)=r\}|\). The data structures require a working memory of size \(O\big{(}(c/\delta)^{D}(k+z)\log(d_{\max}/d_{\min})\log_{1+\lambda}(|W|)\big{)}\)._

The analysis in [22] implies that the constant \(c\) can be fixed arbitrarily close to 32. We remark that the construction described in Section 3.1 cannot return \(\delta\)-coresets with \(\delta\leq 4\), whereas the result of Lemma 5 yields \(\delta\)-coresets for any \(\delta>0\). To obtain the desired solution at any time \(t\), we first compute a \(\delta\)-coreset \(T\) satisfying the properties stated in the above lemma. Then, analogously to computeSolution, we run \(\textsc{outliersCluster}(T,k,\rho,\delta)\) for a geometric sequence of values of \(\rho\) of step \(1+\beta\) between \(d_{\min}\) and \(d_{\max}\), stopping at the minimum value \(\rho_{min}\) for which, if \((X,T^{\prime})\) is the output of \(\textsc{outliersCluster}(T,k,\rho_{min},\delta)\), then the aggregate approximate weight of set \(T^{\prime}\) is at most \(z\). The algorithm returns \(X\) as the final set of (at most) \(k\) centers. By choosing \(\beta=\delta/(3+4\delta)\), we obtain the the following result:

Theorem 3.1: _Let \(\delta,\lambda>0\) be two design parameters and consider a stream of doubling dimension \(D\). There exists a sliding window algorithm that, at any time \(t\), returns a set of, at most, \(k\) centers \(X\subseteq W\), such that at least \(|W|-(1+\lambda)z\) points of \(W\) are at a distance of, at most, \((3+6\delta)r_{kz}^{*}(W)\) from \(X\). For a suitable constant \(c>0\), the algorithm makes use of a working memory of size \(O\big{(}(c/\delta)^{D}(k+z)\log(d_{\max}/d_{\min})\log_{1+\lambda}(|W|)\big{)}\). In addition, the algorithm requires time_

\[O\left(\log_{1+\beta}(d_{\max}/d_{\min})\cdot(k+z)^{2}\right).\]1to update the data structures after each point arrival, and time_

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

_to compute the final solution, with \(\beta=\delta/(3+4\delta)\)._

Proof. : By reasoning as in the proof of Lemma 3, we can show that, by executing \(\textsc{outliersCluster}(T,k,\rho,\delta)\), with any \(\rho\geq r_{k,z}^{*}(W)\), the set of uncovered points at the end of the execution has an aggregate approximate weight of, at most, \(z\). This immediately implies that \(\rho_{min}\leq(1+\beta)r_{k,z}^{*}(W)\). Let \((X,T^{\prime})\) be the output of \(\textsc{outliersCluster}(T,k,\rho_{min},\delta)\), and let \(W^{\prime}\) be the set of points of \(W\) whose proxies are in \(T^{\prime}\). We have that, for each \(p\in W-W^{\prime}\), \(\operatorname{dist}(\pi(p),X)\leq(3+4\delta)\rho_{min}\leq(3+4\delta)(1+ \beta)r_{k,z}^{*}(W)\). Since \(T\) is an \(\delta\)-coreset, we conclude that, for every \(p\in W-W^{\prime}\),

\[O\left(\log_{1+\beta}(d_{\max}/d_{\min})\cdot(k+z)^{2}\right).\]3 \[O\left(\log_{1+\beta}(d_{\max}/d_{\min})\cdot(k+z)^{2}\right).\]4 \[O\left(\log_{1+\beta}(d_{\max}/d_{\min})\cdot(k+z)^{2}\right).\]5

where the last inequality uses the fact that \(\beta=\delta/(3+4\delta)\). Moreover, we also have that \(|W^{\prime}|\leq(1+\lambda)\sum_{r\in T^{\prime}}\bar{w}(r)\leq(1+\lambda)z\). Finally, the bound on the working memory follows from Lemma 5, whereas the time bounds for updating the data structures and extracting the solution from the coreset are obtained by adapting the arguments used to prove Theorems 2 and 3. The following corollary is the counterpart of Corollary 1 for the dimension-sensitive algorithm developed in this section.