# _k_-Center Clustering with Outliers in Sliding Windows
## 3 \(k\)-Center with \(z\) Outliers
### Weighted Coreset Construction
#### 3.1.1 Algorithm
The running times reveal that, by virtue of the coreset-based approach, our-sliding features a query time that is much smaller than the one of charikar and samp-charikar. The update times for our-sliding, although not negligible, are three orders of magnitude smaller than the query times. The experiments for \(z=50\) show that, whereas the working memory requirements and running times increase with \(z\), for reasonably large values of \(N\), our-sliding still exhibits a much lower memory footprint than charikar and still returns solutions of comparable quality. \begin{table}
\begin{tabular}{c c c c c c c c} \hline \hline  & & \multicolumn{3}{c}{**Obj. Ratio**} & \multicolumn{3}{c}{**Memory (\(\times 10^{6}\) Floats)**} \\ \cline{3-8}
**Dataset** & **Algorithm** & \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} } & Our-sliding & \(1\pm 0\) & \(1\pm 0\) & \(1\pm 0\) & \(0.13\pm 0.01\) & \(0.27\pm 0.02\) & \(0.42\pm 0.02\) \\  & charikar & \(1.02\pm 0.05\) & \(0.99\pm 0.04\) & - & \(0.07\pm 0\) & \(0.7\pm 0\) & \(7\pm 0\) \\  & samp-charikar & \(1.07\pm 0.05\) & \(1.43\pm 0.23\) & \(2.74\pm 0.7\) & \(0.07\pm 0\) & \(0.7\pm 0\) & \(7\pm 0\) \\  & gon & \(1.18\pm 0.12\) & \(1.17\pm 0.08\) & \(1.05\pm 0.03\) & \(0.07\pm 0\) & \(0.7\pm 0\) & \(7\pm 0\) \\ \hline \multirow{4}{*}{\begin{tabular}{c} Higgs \\ (z = 50) \\ \end{tabular} } & Our-sliding & \(1\pm 0\) & \(1\pm 0\) & \(1\pm 0\) & \(0.26\pm 0.01\) & \(0.65\pm 0.03\) & \(1.25\pm 0.02\) \\  & charikar & \(1.02\pm 0.04\) & - & - & \(0.07\pm 0\) & \(0.7\pm 0\) & \(7\pm 0\) \\  & samp-charikar & \(1.04\pm 0.06\) & \(1.14\pm 0.08\) & \(1.59\pm 0.15\) & \(0.07\pm 0\) & \(0.7\pm 0\) & \(7\pm 0\) \\  & gon & \(1.54\pm 0.19\) & \(1.5\pm 0.15\) & \(1.19\pm 0.06\) & \(0.07\pm 0\) & \(0.7\pm 0\) & \(7\pm 0\) \\ \hline \multirow{4}{*}{\begin{tabular}{c} Cover \\ (z = 10) \\ \end{tabular} } & Our-sliding & \(1\pm 0\) & \(1\pm 0\) & \(0.72\pm 0.18\) & \(2.06\pm 0.13\) & \\  & charikar & \(0.97\pm 0.17\) & \(1.02\) * & \(0.55\pm 0\) & \(5.5\pm 0\) & \\  & samp-charikar & \(0.96\pm 0.17\) & \(0.98\pm 0.18\) & \(0.55\pm 0\) & \(5.5\pm 0\) & \\  & gon & \(1.1\pm 0.17\) & \(0.94\pm 0.15\) & \(0.55\pm 0\) & \(5.5\pm 0\) & \\ \hline \multirow{4}{*}{\begin{tabular}{c} Cover \\ (z = 50) \\ \end{tabular} } & Our-sliding & \(1\pm 0\) & \(1\pm 0\) & \(1.83\pm 0.22\) & \(5.38\pm 0.22\) & \\  & charikar & \(0.98\pm 0.09\) & - & \(0.55\pm 0\) & \(5.5\pm 0\) & \\  & samp-charikar & \(0.99\pm 0.1\) & \(1.04\pm 0.2\) & \(0.55\pm 0\) & \(5.5\pm 0\) & \\  & gon & \(1.13\pm 0.11\) & \(1.02\pm 0.17\) & \(0.55\pm 0\) & \(5.5\pm 0\) & \\ \hline \multirow{4}{*}{\
\begin{tabular}{c} Higgs+ \\ (z = 10) \\ \end{tabular} } & Our-sliding & \(1\pm 0\) & \(1\pm 0\) & \(1\pm 0\) & \(0.12\pm 0.01\) & \(0.26\pm 0.02\) & \(0.43\pm 0.02\) \\  & charikar & \(0.98\pm 0.18\) & \(0.97\pm 0.04\) & - & \(0.07\pm 0\) & \(0.7\pm 0\) & \(7\pm 0\) \\  & samp-charikar & \(1.09\pm 0.17\) & \(1.61\pm 0.2\) & \(3.03\pm 0.51\) & \(0.07\pm 0\) & \(0.7\pm 0\) & \(7\pm 0\) \\  & gon & \(1.63\pm 0.29\) & \(1.3\pm 0.16\) & \(1.4\pm 0.02\) & \(0.07\pm 0\) & \(0.7\pm 0\) & \(7\pm 0\) \\ \hline \multirow{4}{*}{
\begin{tabular}{c} Cover+ \\ (z = 10) \\ \end{tabular} } & Our-sliding & \(1\pm 0\) & \(1\pm 0\) & \(0.65\pm 0.17\) & \(1.93\pm 0.21\) & \\  & charikar & \(0.99\pm 0.15\) & \(1.02\) * & \(0.55\pm 0\) & \(5.5\pm 0\) & \\  & samp-charikar & \(0.97\pm 0.14\) & \(0.96\pm 0.15\) & \(0.55\pm 0\) & \(5.5\pm 0\) & \\  & gon & \(3.07\pm 2.02\) & \(1.44\pm 0.22\) & \(0.55\pm 0\) & \(5.5\pm 0\) & \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Comparison between clustering radii and between working memory requirements. We also tested the sensitivity of our algorithm's performance to the \(\lambda\) parameter, making it range in \([0,1]\).