# _k_-Center Clustering with Outliers in Sliding Windows
## 3 \(k\)-Center with \(z\) Outliers
### Weighted Coreset Construction
#### 3.1.1 Algorithm
The results for Higgs are shown in Figure 2 and in Tables 3 and 4. Specifically, Table 3 reports on the sensitivity of the clustering radius and of the memory requirements, whereas Table 4 reports on the sensitivity of the update and query times. The experiments were run on Higgs and Cover, with \(k=z=10\), setting, as before, \(\delta=2/3\), \(\beta=0.5\), \(d_{\min}=0.01\), \(d_{\max}=10^{4}\). For \(\lambda\), we used the values: \(0,0.1,0.5,1\). As shown in Figure 2, setting \(\lambda=0\) (i.e., maintaining the full histograms) leads to an unbearable increase in memory usage, and, hence, in execution times. With approximate histograms (i.e., \(\lambda>0\)), the memory usage decreases as \(\lambda\) increases, with a significant drop already for \(\lambda=0.1\). While \(\lambda=0\) yields the solution with the best approximation, in our tests, we often obtained the same solution using \(\lambda=0.1\). Most importantly, the degradation of the clustering radius never exceeded \(1\%\), even for \(\lambda=1\). \begin{table}
\begin{tabular}{c c c c c c c c} \hline \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 Higgs & our-sliding & \(0.66\pm 0.17\) & \(1\pm 0.44\) & \(1.98\pm 0.7\) & \(2.52\pm 1.22\) & \(5.5\pm 0.87\) & \(8.2\pm 0.42\) \\ (\(z=10\)) & chairkar & \(0\pm 0\) & \(0\pm 0\) & \(0\pm 0\) & \(24.88\pm 2.52\) & \(3080.8\pm 160.8\) & - \\  & samp-charikar & \(0\pm 0\) & \(0\pm 0\) & \(0\pm 0\) & \(2.51\pm 0.26\) & \(31.5\pm 1.34\) & \(297.8\pm 30.9\) \\ \hline Higgs & our-sliding & \(1.24\pm 0.66\) & \(4.03\pm 0.53\) & \(5.39\pm 1.14\) & \(10.51\pm 0.76\) & \(93.22\pm 24.76\) & \(75.99\pm 10.38\) \\ (\(z=50\)) & chairkar & \(0\pm 0\) & \(0\pm 0\) & \(0\pm 0\) & \(27.97\pm 2.68\) & – & – \\  & samp-charikar & \(0\pm 0\) & \(0\pm 0\) & \(0\pm 0\) & \(2.87\pm 0.24\) & \(47.95\pm 2.11\) & \(384.4\pm 90.92\) \\ \hline Cover & our-sliding & \(1.05\pm 0.46\) & \(3.74\pm 0.57\) & & \(12.85\pm 2.59\) & \(87.82\pm 46.08\) & \\ (\(z=10\)) & chairkar & \(0\pm 0\) & \(0\pm 0\) & & \(314.93\pm 55.21\) & \(5\cdot 10^{4}\) * & \\  & samp-charikar & \(0\pm 0\) & \(0\pm 0\) & & \(32.1\pm 5.25\) & \(400.81\pm 66.89\) & \\ \hline Cover & our-sliding & \(3.31\pm 0.8\) & \(11.22\pm 1.28\) & & \(44.06\pm 6.88\) & \(892.82\pm 654.3\) & \\ (\(z=50\)) & chairkar & \(0\pm 0\) & \(0\pm 0\) & & \(310.87\pm 43.6\) & - & \\  & samp-charikar & \(0\pm 0\) & \(0\pm 0\) & & \(31.06\pm 3.05\) & \(431.18\pm 28.42\) & \\ \hline Higgs+ & our-sliding & \(0.65\pm 0.26\) & \(1.22\pm 0.37\) & \(1.89\pm 0.42\) & \(0.92\pm 0.93\) & \(5.28\pm 1.82\) & \(8.37\pm 0.31\) \\ (\(z=10\)) & chairkar & \(0\pm 0\) & \(0\pm 0\) & \(0\pm 0\) & \(27.53\pm 3.53\) & \(3224.2\pm 252.4\) & – \\  & samp-charikar & \(0\pm 0\) & \(0\pm 0\) & \(0\pm 0\) & \(2.7\pm 0.22\) & \(35.34\pm 3.14\) & \(328.1\pm 36.08\) \\ \hline Cover+ & our-sliding & \(1.21\pm 0.5\) & \(3.14\pm 0.6\) & & \(7.08\pm 6.54\) & \(51.22\pm 39.68\) & \\ (\(z=10\)) & chairkar & \(0\pm 0\) & \(0\pm 0\) & & \(402.32\pm 71.95\) & \(4\cdot 10^{4}\) * & \\  & samp-charikar & \(0\pm 0\) & \(0\pm 0\) & & \(41.47\pm 9.44\) & \(418.03\pm 47.58\) & \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Comparison between update times and between query times. Figure 2: Our-sliding: sensitivity to \(\lambda\) (Higgs, \(z=10\)). Overall, the experiments confirm that our-sliding is able to achieve a precision comparable to the sequential algorithms at a fraction of their memory/time requirements. ### Effective Diameter

We compared our algorithm for estimating the effective diameter described in Section 4 (dubbed eff-sliding) against the following sequential baseline (dubbed eff-sequential).