# _k_-Center Clustering with Outliers in Sliding Windows
## 3 \(k\)-Center with \(z\) Outliers
### Weighted Coreset Construction
#### 3.1.1 Algorithm
This requires maintaining additional information with the points of the various sets \(R_{\gamma}\) and \(O_{\gamma}\), as explained below. For each guess \(\gamma\) and each active point \(p\in W\), we define its proxy \(\pi_{\gamma}(p)\in R_{\gamma}\cup O_{\gamma}\) as the most recent active point \(r\) such that both \(p\) and \(r\) are attracted by \(a_{\gamma}(p)\). (Note that \(r\) may be an orphan if \(a_{\gamma}(p)\) was discarded from \(A_{\gamma}\).) Thus, \(\pi_{\gamma}(p)=r_{\gamma}(a_{\gamma}(p))\). Therefore, at any time \(t\), the proxy function \(\pi_{\gamma}(\cdot)\) defines a mapping between active points and points of \(O_{\gamma}\cup R_{\gamma}\), and, for every \(r\in O_{\gamma}\cup R_{\gamma}\) we define its _weight_\(w_{\gamma}(r)=|\{p\in W\ :\ \pi_{\gamma}(p)=r\}|\). For each \(r\in R_{\gamma}\cup O_{\gamma}\), our algorithm maintains a _histogram_\(L_{r,\gamma}=\{(t_{r,1},c_{r,1}),(t_{r,2},c_{r,2}),\ldots\}\), which is a list of pairs (timestamp, weight) such that there are \(c_{r,j}\) points \(p\) assigned to \(r\) (i.e., for which \(\pi_{\gamma}(p)=r\)) that arrived at or after time \(t_{r,j}\). When a point \(p\) arrives at time \(t\), the histograms are updated as follows (for the sake of readability, from now on, we drop the subscript \(\gamma\) from histograms and weights, when clear from the context.). If \(p\) becomes a new attraction point (hence, \(p=a_{\gamma}(p)=r_{\gamma}(p)\)), a new histogram \(L_{p}=\{(t,1)\}\) is created and is assigned to \(p\). If, instead, \(p\) is attracted by some \(a\in A_{\gamma}\), then \(p\) becomes the representative \(r_{\gamma}(a)\) and inherits the histogram from the previous representative, modified by increasing all weights by \(1\) and adding the new pair \((t,1)\). In addition, all histogram entries with timestamp \(t-|W|\) are discarded, since they refer to the point that expired at time \(t\). The pairs in each histogram are naturally sorted by an increasing order of timestamps and decreasing order of weight. Observe that, when a representative \(r\) becomes an orphan, and hence is moved from \(R_{\gamma}\) to \(O_{\gamma}\), its histogram \(L_{r}\) does not acquire new entries until \(r\) expires. At any time \(t\), for a histogram \(L_{r}\), we denote by \(c_{L_{r}}\) the weight of the pair in \(L_{r}\) with the smallest timestamp (which is greater than or equal to \(t-|W|+1\) by virtue of the elimination of the old entries described above). It is easy to see that \(c_{L_{r}}=w(r)\), that is, the number of points \(p\) for which \(r\) is the proxy. Unfortunately, keeping the full histogram \(L_{r}\) for each \(r\in R_{\gamma}\cup O_{\gamma}\) requires a working memory of size \(\Theta(|W|)\), which is far beyond the space bound targeted by sliding window algorithms. Therefore, taking inspiration from the smooth histograms of [27], we maintain in \(L_{r}\) only a trimmed version of the full list, which, however, ensures that \(c_{L_{r}}\) is an estimate of \(w(r)\) with a controlled level of accuracy. Specifically, let \(\lambda>0\) be a user-defined accuracy parameter. Every time a histogram \(L_{r}\) is updated, a scan of the pairs is performed that implements the following trimming:  
* The first pair \((t,c)\) is kept in the histogram;
* If a pair \((t,c)\) is kept in the histogram, all subsequent pairs \((t^{\prime},c^{\prime})\) with \(t^{\prime}>t\) and \(c\leq(1+\lambda)c^{\prime}\) are deleted, except for the last such pair, if any. At any time \(t\), the weighted coreset that will be used to solve the \(k\)-center problem with \(z\) outliers for the current window \(W\) consists of the set \(T=R_{\hat{\gamma}}\cup O_{\hat{\gamma}}\), where the guess \(\hat{\gamma}\) is computed as described above, and each \(r\in T\) is assigned weight \(\widehat{w}(r)=c_{L_{r}}\). As will be shown in the next subsection, the \(\widehat{w}(r)\)s are good approximations of the true weights \(w(r)\)s, and this will provide good bi-criteria approximation quality for the returned solution. The pseudocode detailing the algorithm is provided below.