# _k_-Center Clustering with Outliers in Sliding Windows
## 3 \(k\)-Center with \(z\) Outliers
### Weighted Coreset Construction
#### 3.1.1 Algorithm
Moreover, we set \(\eta=1/(2R)\) as it lower bounds the ratio between the effective diameter and the diameter. We report the results for window size \(N=10^{5}\), since a similar pattern emerges for other values of \(N\). Indeed, as Table 7 shows, the memory usage is, in practice, almost constant across all values of \(\eta\). \begin{table}
\begin{tabular}{c c c c c c c} \hline \multirow{2}{*}{**Dataset**} & \multirow{2}{*}{**Algorithm**} & \multicolumn{3}{c}{**Update Time (ms)**} & \multicolumn{3}{c}{**Query Time (s)**} \\ \cline{3-6}  & & \multicolumn{3}{c}{**Window Size**} & \multicolumn{3}{c}{**Window Size**} \\ \cline{3-6}  & & \(\mathbf{10^{4}}\) & \(\mathbf{10^{5}}\) & \(\mathbf{10^{6}}\) & \(\mathbf{10^{4}}\) & \(\mathbf{10^{5}}\) & \(\mathbf{10^{6}}\) \\ \hline \multirow{2}{*}{Higgs-eff} & eff-sliding & \(3.63\pm 3.76\) & \(2.53\pm 1.57\) & \(3.33\pm 1.16\) & \(0.05\pm 0.01\) & \(0.77\pm 0.16\) & \(7.41\pm 0.57\) \\  & eff-sequential & \(0\pm 0\) & \(0\pm 0\) & \(0\pm 0\) & \(9.26\pm 1.23\) & \(994.81\pm 38.63\) & - \\ \hline \end{tabular}
\end{table} 
Table 6: Effective diameter: comparison between update times and between query times. \begin{table}
\begin{tabular}{c c c c c c c c} \hline \multirow{2}{*}{**Dataset**} & \multirow{2}{*}{**Algorithm**} & \multicolumn{3}{c}{**Diameter Ratio**} & \multicolumn{3}{c}{**Memory (\(\times 10^{6}\) floats)**} \\ \cline{3-6}  & & \multicolumn{3}{c}{**Window Size**} & \multicolumn{3}{c}{**Window Size**} \\ \cline{3-6}  & & \(\mathbf{10^{4}}\) & \(\mathbf{10^{5}}\) & \(\mathbf{10^{6}}\) & \(\mathbf{10^{4}}\) & \(\mathbf{10^{5}}\) & \(\mathbf{10^{6}}\) \\ \hline \multirow{2}{*}{Higgs-eff} & eff-sliding & \(1\pm 0\) & \(1\pm 0\) & \(1\pm 0\) & \(0.52\pm 0.36\) & \(0.41\pm 0.23\) & \(0.53\pm 0.1\) \\  & eff-sequential & \(0.991\pm 0.019\) & \(0.992\pm 0.009\) & - & \(0.07\pm 0\) & \(0.7\pm 0\) & \(7\pm 0\) \\ \hline \end{tabular}
\end{table} 
Table 5: Effective diameter: comparison between estimates and between working memory requirements. ## 6 Conclusions

In this paper, we have presented coreset-based streaming algorithms for the \(k\)-center problem with \(z\) outliers and for the estimation of the \(\alpha\)-effective diameter under the sliding window setting. Our algorithms require a working memory that is considerably smaller than the window size, and, with respect to the state-of-the-art sequential algorithms executed on the entire window, they are up to orders of magnitude faster while achieving a comparable accuracy. The effectiveness of our approach has been confirmed by a set of proof-of-concept experiments on both real-world and synthetic datasets. Based on the theoretical analysis conducted in the paper, the space and time required by our algorithms to attain a high accuracy seem to grow steeply (in fact, exponentially) with the doubling dimension of the stream. An interesting, yet challenging, research avenue is to investigate whether this steep dependence can be ameliorated by means of alternative techniques (e.g., the use of randomization). In addition, it would be interesting to incorporate some notion of local density in the clustering quality measure; for example, by using a robust distance measure, such as the one proposed in [29]. Conceptualization: P.P., A.P. and G.P. ; formal analysis and investigation: P.P., A.P. and G.P. ; writing--original draft preparation: P.P. ; writing--review and editing: A.P. and G.P. All authors have read and agreed to the published version of the manuscript. This research was funded in part by MIUR, the Italian Ministry of Education, University and Research, under PRIN Project n. 20174 LF3T8 AHeAD (Efficient Algorithms for Harmessing Networked Data), and grant L. 232 (Dipartimenti di Eccellenza), and by the University of Padova under project \"SID 2020: Resource-Allocation Tradeoffs for Dynamic and Extreme Data\". Not applicable. The source code and the datasets used in our experiments are provided on GitHub at github.com/[PERSON]/OutliersSlidingWindows, (accessed on 10 January 2022).