# _k_-Center Clustering with Outliers in Sliding Windows
## 3 \(k\)-Center with \(z\) Outliers
### Weighted Coreset Construction
#### 3.1.1 Algorithm
Corollary 2: _Let \(\lambda=1/(2z)\). At any time \(t\), the algorithm is able to compute a set \(X\subseteq W\) of, at most, \(k\) centers, such that at least \(|W|-z\) points of \(W\) are at a distance of, at most, \((3+6\delta)r_{k,z}^{*}(W)\) from \(X\). For a fixed constant \(c>0\), the algorithm requires a working memory of size \(O\big{(}(c/\delta)^{D}z(k+z)\log(d_{\max}/d_{\min})\log(|W|)\big{)}\) and runs in time_

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

_with \(\beta=\delta/(3+4\delta)\)._

It is important to remark that the algorithm in [22] that we have built upon is _fully oblivious_ to \(D\), \(d_{\max}\), and \(d_{\min}\). Its augmentation discussed above inherits the obliviousness to \(D\) straightforwardly, whereas the obliviousness to \(d_{\max}\) and \(d_{\min}\) is inherited through the technique described in Section 3.3. ## 4 Effective Diameter Estimation

Consider a stream \(S\) of doubling dimension \(D\). Building on the improved coreset construction of Lemma 5, we now outline an algorithm that, at any time \(t\), is able to compute lower and upper estimates of the \(\alpha\)-effective diameter \(\Delta_{W}^{\alpha}\) of the current window \(W\). The algorithm requires the knowledge of a (possibly crude) lower bound \(\eta\in(0,1)\) on the ratio between \(\Delta_{W}^{\alpha}\) and the diameter \(\Delta_{W}\) (i.e., \(\Delta_{W}^{\alpha}\geq\eta\Delta_{W}\)). For a given \(\varepsilon>0\), let \(T\) be a weighted \(\delta\)-coreset for \(W\) computed with the properties stated in Lemma 5, with \(\delta=\varepsilon\eta/2\), \(k=1\) and \(z=0\). Hence, \(|T|=O((c^{\prime}/(\varepsilon\eta))^{D})\), with \(c^{\prime}=2c\), where \(c\) is the same constant appearing the statement of the lemma. Assume for now that, for each \(r\in T\), the true weight \(w(r)=|\{p\in W:\pi(p)=r\}|\) is known. (Later, we will discuss the distortion introduced by using the approximate weights \(\bar{w}(r)\).) An approximation to \(\Delta_{W}^{\alpha}\) can be computed on the coreset through the following quantity:\[\Delta_{T,W}^{\alpha}=\operatorname*{argmin}_{d}\left\{\sum_{ \begin{subarray}{c}r_{1}r_{2}\in T:\\ \operatorname*{dist}(r_{1}r_{2})\leq d\end{subarray} }w(r_{1})w(r_{2})\geq \alpha|W|^{2}\right\}.\]

Lemma 6: \((1-\varepsilon)\Delta_{W}^{\alpha}\leq\Delta_{T,W}^{\alpha}\leq(1+\varepsilon) \Delta_{W}^{\alpha}\)_._

Proof: Let \(\hat{d}=\max\{\operatorname*{dist}(p,\pi(p)):p\in W\}\). Recall that the \(\delta\)-coreset \(T\) was computed with \(k=1\) and \(z=0\); hence, using the properties of \(T\) and the fact that \(\Delta_{W}^{\alpha}\geq\eta\Delta_{W}\), we have that

\[\hat{d}\leq\delta r_{1}^{*}(W)\leq(\varepsilon\eta/2)\Delta_{W}\leq( \varepsilon/2)\Delta_{W}^{\alpha}.\]

Using the triangle inequality, for any \(d\) and any pair \((p,q)\in W\times W\), we have that, if \(\operatorname*{dist}(\pi(p),\pi(q))\leq d-2\hat{d}\), then \(\operatorname*{dist}(p,q)\leq d\). Thus, when \(|\{(p,q)\in W\times W:\operatorname*{dist}(\pi(p),\pi(q))\leq d-2\hat{d}\}| \geq\alpha|W|^{2}\), we must also have \(|\{(p,q)\in W\times W:\operatorname*{dist}(p,q)\leq 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\}\] \[\leq\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\}\] \[=\operatorname*{argmin}_{d}\left\{\sum_{ \begin{subarray}{c}r_{1} r_{2}\in T:\\ \operatorname*{dist}(r_{1}r_{2})\leq d\end{subarray} }w(r_{1})w(r_{2})\geq\alpha|W |^{2}\right\}+2\hat{d}\] \[=\Delta_{T,W}^{\alpha}+2\hat{d}\leq\Delta_{T,W}^{\alpha}+\varepsilon \Delta_{W}^{\alpha},\]

thus proving the first stated inequality. The proof of the other inequality is accomplished with a symmetrical argument.