# _k_-Center Clustering with Outliers in Sliding Windows
## 3 \(k\)-Center with \(z\) Outliers
### Weighted Coreset Construction
#### 3.1.1 Algorithm
eff-sequential computes all \(N^{2}\) distances in the window \(W\) and, to avoid storing all of them, only keeps track of how many distances lay in each interval \([d_{\text{min}}\cdot(1+\rho)^{i},d_{\text{min}}\cdot(1+\rho)^{i+1}]\), for \(i\geq 0\), by maintaining the appropriate counters. We set \(\rho=0.01\) so that the error due to this discretization is minimal. After all distances have been computed, the algorithm sweeps the counters and returns the minimum value \(d_{\text{min}}\cdot(1+\rho)^{i}\) for which at least \(\lceil a|W|^{2}\rceil\) distances fall below that value. This same procedure, adapted to account for weights, is also used in eff-sliding to compute the solution on the weighted coreset. We experimented on the Higgs-eff dataset, which is another artificially inflated version of the Higgs dataset where a true outlier (i.e., a random point whose norm is 100 times the diameter of the original dataset) is injected, on average, every 1000 points. In the experiment, we set \(\alpha=0.9\). Since, for every tested window size \(N\), \(\alpha N^{2}\ll(N-N/1000)^{2}\), we expect, in this controlled experiment, the \(\alpha\)-effective diameter of each window of Higgs-eff to be close to the diameter of the non-outlier points in the window. For our algorithm, we set \(\epsilon=5/3\) and \(\lambda=\beta=0.5\). Moreover, we set \(d_{\text{min}}=0.01\) and \(d_{\text{max}}=10^{4}\). Finally, we set \(\eta=1/1000\), which is a very conservative lower bound to the ratio between the effective diameter and the diameter of the dataset for any window \(W\). \begin{table}
\begin{tabular}{c c c c c c c c} \hline \multirow{2}{*}{**Dataset**} & \multirow{2}{*}{**Algorithm**} & \multicolumn{4}{c}{**Update Time (ms)**} & \multicolumn{4}{c}{**Query Time (s)**} \\ \cline{3-8}  & & \multicolumn{3}{c}{**Window Size**} & \multicolumn{3}{c}{**Window Size**} \\ \cline{3-8}  & & \(\mathbf{10^{4}}\) & \(\mathbf{10^{5}}\) & \(\mathbf{10^{6}}\) & \(\mathbf{10^{4}}\) & \(\mathbf{10^{5}}\) & \(\mathbf{10^{6}}\) \\ \hline \multirow{4}{*}{\
\begin{tabular}{c} Higgs \\ (z = 10) \\ \end{tabular} } & \(\lambda=0\) & \(3.49\pm 0.69\) & \(35.18\pm 21.11\) & - & \(2.49\pm 1.16\) & \(5.91\pm 0.74\) & - \\  & \(\lambda=0.1\) & \(0.72\pm 0.38\) & \(1.56\pm 0.53\) & \(2.58\pm 0.41\) & \(2.47\pm 1.18\) & \(5.88\pm 0.89\) & \(8.88\pm 0.47\) \\  & \(\lambda=0.2\) & \(0.57\pm 0.12\) & \(1.39\pm 0.42\) & \(2.06\pm 0.67\) & \(2.46\pm 1.19\) & \(5.82\pm 0.91\) & \(7.74\pm 0.25\) \\  & \(\lambda=1\) & \(0.57\pm 0.1\) & \(1.32\pm 0.36\) & \(1.99\pm 0.32\) & \(2.47\pm 1.2\) & \(5.81\pm 0.92\) & \(7.77\pm 0.15\) \\ \hline \multirow{4}{*}{
\begin{tabular}{c} Cover \\ (z = 10) \\ \end{tabular} } & \(\lambda=0\) & \(1.12\pm 0.38\) & \(3.75\pm 0.32\) & & \(12.44\pm 2.38\) & \(90.65\pm 51.26\) & \\  & \(\lambda=0.1\) & \(1.33\pm 0.69\) & \(3.72\pm 0.53\) & & \(12.31\pm 1.92\) & \(90.36\pm 51.44\) & \\ \cline{1-1}  & \(\lambda=0.2\) & \(1.27\pm 0.5\) & \(3.57\pm 0.25\) & & \(12.41\pm 2.19\) & \(90\pm 51.14\) & \\ \cline{1-1}  & \(\lambda=1\) & \(1.21\pm 0.5\) & \(4.29\pm 2.28\) & & \(12.32\pm 2.17\) & \(90.34\pm 50.61\) & \\ \hline \end{tabular}
\end{table} 
Table 4: Sensitivity of our-sliding to \(\lambda\): update and query times.