# _k_-Center Clustering with Outliers in Sliding Windows
## 3 \(k\)-Center with \(z\) Outliers
### Weighted Coreset Construction
#### 3.1.1 Algorithm
Let \(p_{1},p_{2},\ldots\) be an enumeration of all points of the stream \(S\) based on their arrival times. For \(t>k+z\), let \(d_{t}\) be the minimum pairwise distance between the last \(k+z+1\) points of the stream \((p_{t-k-z},\ldots,p_{t-1},p_{t})\). Let also \(D_{t}\) be the maximum distance between \(p_{1}\) and any \(p_{i}\) with \(i\leq t\), and note that, by the triangle inequality, the maximum pairwise distance among the first \(t\) points of \(S\) is upper bounded by \(2D_{t}\). It is easy to argue that \(d_{t}/2\leq r_{k+z}^{*}(W)\leq r_{k,z}^{*}(W)\leq 2D_{t}\). By storing \(p_{1}\) and the last \(k+z+1\) points of the stream, the values \(d_{t}\) and \(D_{t}\) can be straightforwardly maintained by the algorithm with \(O\big{(}(k+z)^{2}\big{)}\) operations per step. We define

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

Suppose that, at any time \(t\), the algorithm maintains the sets \(A_{\gamma}\), \(R_{\gamma}\) and \(O_{\gamma}\), and the histograms for the points in \(R_{\gamma}\cup O_{\gamma}\), only for \(\gamma\in\Gamma_{t}\), and assume that the properties stated in Lemmas 1 and 2 hold for every \(\gamma\in\Gamma_{t}\) and \(r\in R_{\gamma}\cup O_{\gamma}\). Then, by running procedure extractCoreset and limiting the search for \(\hat{\gamma}\) to the set \(\Gamma_{t}\), we still obtain a \(4(1+\beta)\)-coreset for the current window. To see this, we first note that, based on the previous observation, \(\Gamma_{t}\) definitely includes a value \(\gamma\) with \(r_{k+z}^{*}(W)\leq\gamma\leq(1+\beta)r_{k+z}^{*}(W)\). By repeating the same argument used in the proof of Theorem 1, we can show that, for such a value of \(\gamma\), we have that \(|A_{\gamma}|\leq k+z\), and that the inner for loop of extractCoreset computes a set \(C\) of, at most, \(k+z\) points. This immediately implies that extractCoreset determines a guess \(\hat{\gamma}\leq(1+\beta)r_{k+z}^{*}(W)\) and that the returned coreset \(T=R_{\hat{\gamma}}\cup O_{\hat{\gamma}}\) is a \(4(1+\beta)\)-coreset. We now show how to modify the algorithm described in the previous subsections (referred to as _full algorithm_ in what follows) to maintain, without the knowledge of \(d_{\min}\) and \(d_{\max}\), the sets \(A_{\gamma}\), \(R_{\gamma}\), and \(O_{\gamma}\) and the required histograms, for every guess \(\gamma\in\Gamma_{t}\). Suppose that this is the case up to some time \(t-1>k+z\), and consider the arrival of \(p_{t}\). Before invoking update\((p_{t},t)\), the algorithm executes the operations described below. First, the new values \(d_{t}\) and \(D_{t}\) are computed, and all sets relative to values of \(\gamma\in\Gamma_{t-1}-\Gamma_{t}\) are removed. If \(d_{t}<d_{t-1}\), then, for each \(\gamma\in\Gamma_{t}\) with \(\gamma<\min\{\gamma^{\prime}\in\Gamma_{t-1}\}\leq d_{t-1}/2\), the algorithm sets \(A_{\gamma}=\{p_{t-k-z-1},\ldots,p_{t-1}\}=R_{\gamma}\) and \(O_{\gamma}=\emptyset\). Moreover, for each \(p_{\tau}\in R_{\gamma}\), it sets \(L_{p_{\tau}}=\{(\tau,1)\}\), as each point represents itself only. Since any two points in \(A_{\gamma}\) are at a distance of at least \(d_{t-1}>2\gamma\), it is easy to see that these newly created data structures coincide with the ones that the full algorithm would store at time \(t-1\) (for the same \(\gamma\)'s) if the stream started at time \(t-(k+z+1)\); hence, they satisfy the properties of Lemmas 1 and 2. If \(D_{t}>D_{t-1}\), then for each \(\gamma\in\Gamma_{t}\) with \(\gamma>\max\{\gamma^{\prime}\in\Gamma_{t-1}\}\), the algorithm sets \(A_{\gamma}=\{p_{t-|W|}\}\), \(R_{\gamma}=\{p_{t-1}\}\) and \(O_{\gamma}=\emptyset\). It is easy to see that these newly created sets coincide with the ones that the full algorithm would store at time \(t-1\) (for the same \(\gamma\)'s) if the stream started at time \(t-|W|\); hence, they satisfy the properties of Lemma 1.