# _k_-Center Clustering with Outliers in Sliding Windows
## 3 \(k\)-Center with \(z\) Outliers
### Weighted Coreset Construction  
#### 3.1.1 Algorithm  
The proposed coreset construction hinges upon the approach by [21] for \(k\)-center without outliers, with major extensions introduced to maintain weights. Let \(d_{\min}\) and \(d_{\max}\) denote, respectively, the minimum and maximum distances between any two distinct points of the stream. For a user-defined constant \(\beta\in(0,1]\), let  
\[\Gamma=\{(1+\beta)^{i}:\lfloor\log_{1+\beta}d_{\min}\rfloor\leq i\leq\lceil \log_{1+\beta}d_{\max}\rceil\},\]The values in \(\Gamma\) will be used as guesses of the optimal radius \(r_{k+z}^{*}(W)\) of a \((k+z)\)-center clustering without outliers of the current window (recall that \(r_{k+z}^{*}(W)\) is a lower bound to the optimal radius \(r_{k,z}^{*}(W)\) for the problem with \(z\) outliers), and the algorithm will maintain suitable data structures capable of identifying the right guess. For ease of presentation, we assume for now that \(d_{\min}\) and \(d_{\max}\) are known to the algorithm. In Section 3.3, we will show how the assumption can be removed by maintaining estimates of the two values. For each guess \(\gamma\), the algorithm maintains three sets of active points, namely \(A_{\gamma}\), \(R_{\gamma}\), and \(O_{\gamma}\), and the coreset is extracted from these sets. \(A_{\gamma}\) is a small set of active points, called _attraction points_, such that, for any two distinct \(a_{1},a_{2}\in A_{\gamma}\), \(\operatorname{dist}(a_{1},a_{2})>2\gamma\). At every time \(t\), the arrival of a new point \(p\) is handled as follows, for every guess \(\gamma\). If there exist attraction points \(a\) such that \(\operatorname{dist}(p,a)\leq 2\gamma\), we define \(a_{\gamma}(p)\) as the one with minimum TTL, and say that \(p\)_is attracted by \(a_{\gamma}(p)\)_. Otherwise, \(p\) becomes a new attraction point in \(A_{\gamma}\), and we let \(a_{\gamma}(p)=p\) (i.e., \(p\) is attracted by itself). Set \(R_{\gamma}\) maintains, for each \(a\in A_{\gamma}\), one _representative_\(r_{\gamma}(a)\), defined as the most recent point attracted by \(a\). Note that, whereas \(a_{\gamma}(p)\) is fixed at \(p\)'s arrival, the representative \(r_{\gamma}(a)\) may change with time. When an attraction point \(a\) expires, its representative \(r_{\gamma}(a)\) becomes an _orphan_ and is moved to the set \(O_{\gamma}\). Since the pairwise distance between the points of \(A_{\gamma}\) is \(>2\gamma\), if \(|A_{\gamma}|\geq k+z+1\), it is clear that \(\gamma<r_{k+z}^{*}(W)\), and, as will be seen below, the points in \(A_{\gamma}\cup R_{\gamma}\cup O_{\gamma}\) will not be used to extract the coreset. Therefore, to save memory, we set \(k+z+1\) as a threshold for \(|A_{\gamma}|\): when \(|A_{\gamma}|=k+z+1\) and the newly arrived point qualifies to be an attraction point, the algorithm discards the point \(a\in A_{\gamma}\) with minimum TTL, and moves its representative \(r_{\gamma}(a)\) to \(O_{\gamma}\). As further space saving, all points in \(O_{\gamma}\) older than \(a\) are discarded, since throughout their residual lifespan, \(|A_{\gamma}|\geq k+z+1\), and hence they cannot contribute to a valid coreset. At any time \(t\), the coreset for the \(k\)-center problem with \(z\) outliers, w.r.t. the current window \(W\), is obtained as \(T=R_{\hat{\gamma}}\cup O_{\hat{\gamma}}\), where \(\hat{\gamma}\) is the smallest guess such that: (i) \(|A_{\hat{\gamma}}|\leq k+z\); and (ii) by running the simple greedy strategy of [13], reviewed in Section 2.1, a set \(C\) of \(k+z\) points can be selected from \(A_{\hat{\gamma}}\cup R_{\hat{\gamma}}\cup O_{\hat{\gamma}}\), such that any other point in this set is at a distance of, at most, \(2\hat{\gamma}\) from a selected point. To ensure that an accurate solution to the \(k\)-center problem with \(z\) outliers can be extracted from the coreset \(T\), we need to weigh each point \(p\in T\) with (a suitable accurate estimate of) the number of window points for which \(p\) can act as a _proxy_.