# _k_-Center Clustering with Outliers in Sliding Windows
## 3 \(k\)-Center with \(z\) Outliers
### Weighted Coreset Construction
#### 3.1.1 Algorithm
The triangle inequality ensures that, for every pair \((p,q)\in W\times W\), if \(\operatorname*{dist}(p,q)\leq d\), then \(\operatorname*{dist}(\pi(p),\pi(q))\leq d+2\hat{d}\). Thus, when \(|\{(p,q)\in W\times W:\operatorname*{dist}(p,q)\leq d\}|\geq\alpha|W|^{2}\), we must also have \(|\{(p,q)\in W\times W:\operatorname*{dist}(\pi(p),\pi(q))\leq d+2\hat{d}\}| \geq\alpha|W|^{2}\). Consequently,

\[\Delta_{W}^{\alpha} =\operatorname*{argmin}_{d}\left\{|\{(p,q)\in W\times W: \operatorname*{dist}(p,q)\leq d\}|\geq\alpha|W|^{2}\right\}\] \[\geq\operatorname*{argmin}_{d}\left\{|\{(p,q)\in W\times W: \operatorname*{dist}(\pi(p),\pi(q))\leq d+2\hat{d}\}|\geq\alpha|W|^{2}\right\}\] \[=\operatorname*{argmin}_{d}\left\{\sum_{ \begin{subarray}{c}r_{1} r_{2}\in T:\\ \operatorname*{dist}(r_{1}r_{2})\leq d+2\hat{d}\end{subarray} }w(r_{1})w(r_{2}) \geq\alpha|W|^{2}\right\}-2\hat{d}\] \[=\Delta_{T,W}^{\alpha}-2\hat{d}\geq\Delta_{T,W}^{\alpha}- \varepsilon\Delta_{W}^{\alpha}.\]Recall now that, for every coreset point \(r\in T\), only an approximation \(\tilde{w}(r)\) to the actual weight \(w(r)\) is available, with \(w(r)/(1+\lambda)\leq\tilde{w}(r)\leq w(r)\). We define the approximate counterpart of \(\Delta^{\alpha}_{T,W}\) as

\[\tilde{\Delta}^{\alpha}_{T,W}=\underset{d\text{ dist}(r_{1},r_{2})\leq d}{\sum_{r_{1},r_{2}\in T:}}\tilde{w}(r_{1})\tilde{w}(r_{2}) \geq\alpha|W|^{2}.\]

Our approximation algorithm returns \((1/(1+\epsilon))\tilde{\Delta}^{\alpha/(1+\lambda)^{2}}_{T,W}\) and \((1/(1-\epsilon))\tilde{\Delta}^{\alpha}_{T,W}\) as the lower and upper estimates, respectively, of the true effective diameter \(\Delta^{\alpha}_{W}\). The following theorem establishes the tightness of these estimates and the space and time performance of the algorithm. Theorem 4.1: _Consider a stream \(S\) of doubling dimension \(D\), and a value \(\alpha\in(0,1)\). Suppose that a value \(\eta<1\) is known such that, for every window \(W\), \(\Delta^{\alpha}_{W}\geq\eta\Delta_{W}\). For any \(\varepsilon,\lambda>0\), there exists a sliding window algorithm that, at any time \(t\), is able to compute a weighted coreset \(T\) of size \(O((c^{\prime}/(\varepsilon\eta))^{D})\), such that_

\[\frac{1}{1+\varepsilon}\tilde{\Delta}^{\alpha/(1+\lambda)^{2}}_{T,W}\leq \Delta^{\alpha}_{W}\leq\frac{1}{1-\varepsilon}\tilde{\Delta}^{\alpha}_{T,W},\]

_where \(W\) is the current window and \(c^{\prime}>0\) is a suitable constant. The algorithm makes use of a working memory of size \(O\big{(}(c^{\prime}/(\varepsilon\eta))^{D}\log(d_{\max}/d_{\min})\log_{1+ \lambda}(|W|)\big{)}\). In addition, the algorithm requires time_

\[O\Big{(}\log_{1+\beta}(d_{\max}/d_{\min})\cdot\big{(}(c^{\prime}/(\varepsilon \eta))+\log_{1+\lambda}(|W|)\big{)}\Big{)}\]

_to update the data structures after each point arrival, where \(\beta=\delta/(3+4\delta)\). The lower and upper estimates to \(\Delta^{\alpha}_{W}\) can be computed from \(T\) in time \(O\big{(}|T|^{2}\big{)}=O\big{(}(c^{\prime}/(\varepsilon\eta))^{2D}\big{)}\)._

Proof: We first prove that

\[\tilde{\Delta}^{\alpha/(1+\lambda)^{2}}_{T,W}\leq\Delta^{\alpha}_{T,W}\leq \tilde{\Delta}^{\alpha}_{T,W}.\]

Then, the stated approximation interval will immediately follow by Lemma 6. Let us first prove the leftmost inequality. From Lemma 5 we have that, for every \(r\in T\), \(\tilde{w}(r)\geq w(r)/(1+\lambda)\). Hence, for any \(d\) such that

\[\sum_{ \begin{subarray}{c}r_{1},r_{2}\in T:\\ \text{dist}(r_{1},r_{2})\leq d\end{subarray} }w(r_{1})w(r_{2})\geq\alpha|W|^{2},\]

we have that

\[\sum_{ \begin{subarray}{c}r_{1},r_{2}\in T:\\ \text{dist}(r_{1},r_{2})\leq d\end{subarray} }\tilde{w}(r_{1})\tilde{w}(r_{2}) \geq\frac{\alpha}{(1+\lambda)^{2}}|W|^{2},\]

which implies \(\tilde{\Delta}^{\alpha/(1+\lambda)^{2}}_{T,W}\leq\Delta^{\alpha}_{T,W}\). The righmost inequality is proved in a symmetrical fashion. Again, from Lemma 5, we have that, for every \(r\in T\), \(w(r)\geq\tilde{w}(r)\). Hence, for any \(d\) such that

\[\sum_{ \begin{subarray}{c}r_{1},r_{2}\in T:\\ \text{dist}(r_{1},r_{2})\leq d\end{subarray}