# _k_-Center Clustering with Outliers in Sliding Windows
## 3 \(k\)-Center with \(z\) Outliers
### Weighted Coreset Construction
#### 3.1.1 Algorithm
\begin{table}
\begin{tabular}{c c c c c c c c} \hline \multirow{2}{*}{**Dataset**} & \multirow{2}{*}{**Algorithm**} & \multicolumn{4}{c}{**Clustering Radius**} & \multicolumn{4}{c}{**Memory (\(\times 10^{6}\) Floats)**} \\ \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\) & \(2.826\pm 0.178\) & \(4.289\pm 0.162\) & - & \(0.53\pm 0.04\) & \(4.85\pm 0.96\) & - \\  & \(\lambda=0.1\) & \(2.826\pm 0.178\) & \(4.289\pm 0.162\) & \(5.981\pm 0.124\) & \(0.15\pm 0.01\) & \(0.36\pm 0.03\) & \(0.6\pm 0.02\) \\  & \(\lambda=0.5\) & \(2.808\pm 0.195\) & \(4.297\pm 0.165\) & \(6.031\pm 0.027\) & \(0.13\pm 0.01\) & \(0.27\pm 0.02\) & \(0.42\pm 0\) \\  & \(\lambda=1\) & \(2.812\pm 0.178\) & \(4.281\pm 0.176\) & \(6.031\pm 0.021\) & \(0.12\pm 0.01\) & \(0.24\pm 0.02\) & \(0.37\pm 0\) \\ \hline \multirow{4}{*}{
\begin{tabular}{c} Cover \\ (z = 10) \\ \end{tabular} } & \(\lambda=0\) & \(1177.56\pm 400.03\) & \(1976.02\pm 150.66\) & & \(0.75\pm 0.17\) & \(2.3\pm 0.15\) & \\  & \(\lambda=0.1\) & \(1177.56\pm 400.03\) & \(1973.31\pm 149.53\) & & \(0.74\pm 0.17\) & \(2.23\pm 0.14\) & \\ \cline{1-1}  & \(\lambda=0.5\) & \(1177.56\pm 400.03\) & \(1954.08\pm 145.71\) & & \(0.72\pm 0.18\) & \(2.06\pm 0.13\) & \\ \cline{1-1}  & \(\lambda=1\) & \(1180.44\pm 405.86\) & \(1967.02\pm 150.61\) & & \(0.71\pm 0.18\) & \(2\pm 0.12\) & \\ \hline \end{tabular}
\end{table} 
Table 3: Sensitivity of our-sliding to \(\lambda\): clustering radii and working memory requirements. The results of these experiments are reported in Tables 5 and 6. Table 5 reports the ratio between the effective diameter computed by eff-sequential and the (conservative) upper estimate \(\tilde{\Delta}_{T,W}^{\alpha}\) computed by eff-sliding, as well as the average number of floats maintained in memory by the algorithms. As shown in the table, the solution returned by eff-sliding is almost indistinguishable from the one returned by eff-sequential for those window sizes for which eff-sequential, whose complexity grows quadratically, could be executed within reasonable times. On the other hand, the memory usage of eff-sliding grows very slowly with \(N\), and, thus, for large enough window sizes, becomes lower than the one of eff-sequential. Table 6 reports the update and query times for the two algorithms. Due to the reduced coreset size, the query times of eff-sliding are orders of magnitude lower than those of eff-sequential, and the updated times of eff-sliding, although not negligible, are significantly smaller than the query times. Finally, we tested on tailor-made artificial datasets the impact of the parameter \(\eta\), which is a (possibly crude) lower bound on the ratio between the effective diameter and the diameter. In fact, the theoretical bounds on the coreset size embody a factor proportional to \((1/\eta)^{D}\), which could lead to a severe deterioration of the performance indicators for low (i.e., conservative) values of \(\eta\). In reality, for datasets where the discrepancy between the diameter and effective diameter is caused by few distant outliers (noisy points), since the balls centered on coreset points have radius \(O(\epsilon\eta\Delta_{W})=O(\epsilon\Delta_{W}^{\alpha})\) and since most of the points will be contained in a ball of radius \(O\big{(}\Delta_{W}^{\alpha}\big{)}\), with only a few outliers at distance \(O(\Delta_{W})\), the actual number of points maintained in the coreset should not really depend on \(\eta\). To test this intuition, we created artificial datasets by generating random points in a ball of unit radius with a few outliers (one every 1000 points, on average) on the surface of a ball of radius \(R\) for values of \(R\) in \(\{10,100,1000\}\). We set \(\alpha=0.9\) as before, and ran our algorithm with \(\epsilon=10/3\) and \(\lambda=0.5\).