# _k_-Center Clustering with Outliers in Sliding Windows
## 3 \(k\)-Center with \(z\) Outliers
### Weighted Coreset Construction
#### 3.1.1 Algorithm
The arrival of a new point \(p\) at time \(t\) is handled by the main Procedure \(\texttt{update}(p,t)\) (Algorithm 1), which, for every guess \(\gamma\), invokes, in turn, Procedure \(\texttt{insertAttraction}(p,\gamma)\) (Algorithm 2) when \(p\) must be added to \(A_{\gamma}\), or Procedure \(\texttt{updateHistrograms}(L_{p,\gamma})\) (Algorithm 3) when \(p\) becomes a new representative of some existing point of \(A_{\gamma}\). To extract the weighted coreset, Procedure \(\texttt{extractCoreset}()\) (Algorithm 4) is executed. ```
1 foreach\(\gamma\in\Gamma\)do
2 foreach\(p\in A_{\gamma}\)do
3\(A_{\gamma}\gets A_{\gamma}\setminus\{p\}\)
4 Move \(r_{\gamma}(p)\) from \(R_{\gamma}\) to \(O_{\gamma}\)
5 foreach\(r\in O_{\gamma}\)do
6 if\(r\) is expiredthen
7 Remove \(r\) (and its histogram) from \(O_{\gamma}\)
8 Remove from \(L_{r,\gamma}\) the entry (if any) with timestamp \(t-|W|\)
9\(x\leftarrow\text{argmin}_{q\in A_{\gamma}}\text{dist}_{(p,q)\leq 2\gamma}\text{TTL}(q)\)
10 if\(x==null\)then
11 insertAttraction(\(p,\gamma\))
12\(L_{p,\gamma}\leftarrow\{(t,1)\}\)
13 else
14 Move the content of \(L_{r_{\gamma}(x),\gamma}\) to \(L_{p,\gamma}\)
15 updateHistogram(\(L_{p,\gamma}\))
16 Set



#### 3.1.2 Analysis

The following two technical lemmas state important properties of the sets \(A_{\gamma}\), \(O_{\gamma}\), and \(R_{\gamma}\), and of the histograms maintained by the algorithm. **Lemma 1**. : _At any time \(t\), the following properties hold for every \(\gamma\in\Gamma\):_

1. _If_ \(|A_{\gamma}|\leq k+z\)_, then_ \(\max_{q\in W}\operatorname{dist}(q,\pi_{\gamma}(q))\leq 4\gamma\)_._
2. \(|A_{\gamma}|,|R_{\gamma}|,|O_{\gamma}|\leq k+z+1\)_._

Proof. : In order to prove the lemma, it suffices to show that, if the properties hold after the processing of the \((t-1)\)-th point, they are inductively maintained after the invocation of update\((p,t)\). The proof makes use of essentially the same arguments employed in [21][Lemmas 7, 8], straightforwardly adapted to account for the fact that, in our algorithm, each new point that does not become an attraction point is made representative of a single attraction point, whereas, in [21], it would be made representative of all attraction points at a distance of, at most, \(2\gamma\). Recall that, at any time \(t\) and for any guess \(\gamma\), the histogram \(L\), associated with each point \(r\in R_{\gamma}\cup O_{\gamma}\) is a list of pairs \((t_{r,i},c_{r,i})\) indicating that there are currently \(c_{r,i}\) points that have arrived after time \(\geq t_{r,i}\), whose proxy is \(r\), for \(i=1,2,\ldots\). We have:

**Lemma 2**. : _For any time \(t\), guess \(\gamma\), and \(r\in R_{\gamma}\cup O_{\gamma}\), the following properties hold for \(L_{r}\)._

1. _For every_ \(1\leq i\leq|L_{r}|\)_,_ \(c_{r,i}\leq|W|\)_;_
2. _For every_ \(1\leq i\leq|L_{r}|-1\)_,_ \(c_{r,i}\leq(1+\lambda)c_{r,i+1}\) _or_ \(c_{r,i}=1+c_{r,i+1}>(1+\lambda)c_{r,i+1}\)_;_
3. _For every_ \(1\leq i\leq|L_{r}|-2\)_,_ \(c_{r,i}>(1+\lambda)c_{r,i+2}\)_;_
4. \(|L_{r}|\in O\big{(}\log_{1+\lambda}|W|\big{)}\)_._

Proof. : First, observe that Property 4 is an immediate consequence of Properties 1 and 3. Hence, we are left with proving Properties 1, 2, and 3. The properties clearly hold when the histogram \(L_{r}\) is first created (Line 12 of update); thus, we only need to show that ifthey hold prior to an invocation of updateHistogram(\(L_{r}\)), they continue to hold for the histogram \(M\) created by updateHistogram(\(L_{r}\)), which becomes the new \(L_{r}\) at the end of the procedure. Property 1 holds since the weights are updated only as long as \(a_{\gamma}(r)\), the oldest point accounted for in the histogram, is active; hence, weights always represent sizes of subsets of points of the same window, and thus they never exceed \(|W|\). Consider now Properties 2 and 3. Let \(L_{r}^{\prime}\) denote the histogram \(L_{r}\) after the execution of Line 4 of updateHistogram(\(L_{r}\)) (i.e., after the increment of the weights and the addition of \((t,1)\) at the end of the list).