# _k_-Center Clustering with Outliers in Sliding Windows
## 3 \(k\)-Center with \(z\) Outliers
### Weighted Coreset Construction
#### 3.1.1 Algorithm
The algorithms were tested on the following datasets, often used in previous works [8]: the Higgs dataset ([[http://archive.ics.uciedu/ml/datasets/HIGGS](http://archive.ics.uciedu/ml/datasets/HIGGS)]([http://archive.ics.uciedu/ml/datasets/HIGGS](http://archive.ics.uciedu/ml/datasets/HIGGS))), (accessed on 10 January 2022), which contains 11 million seven-dimensional points representing high-energy particle features generated through Monte-Carlo simulations; and the Cover dataset ([[https://archive.ics.uci.edu/ml/datasets/covertype](https://archive.ics.uci.edu/ml/datasets/covertype)]([https://archive.ics.uci.edu/ml/datasets/covertype](https://archive.ics.uci.edu/ml/datasets/covertype))), (accessed on 10 January 2022), which contains 581,012 55-dimensional points from geological observations of US forest biomes, and was employed as a stress test for our dimensionality-sensitive algorithm. We also generated inflated versions of the original datasets, dubbed Higgs+ and Cover+, by artificially injecting a new true outlier point after each original point with probability \(p\), where the new point has a norm 100 times the diameter of the original dataset (e.g., as if produced by a malfunctioning sensor). The probability \(p\) was chosen to yield \(z/2\) true outliers per window, in expectation. We performed tests for \(k=10\), \(z=10,50\), and window sizes \(|W|=N\in\{10^{4},10^{5},10^{6}\}\) using Euclidean distance. For our-sliding, we set \(\delta=2/3\), \(\beta=0.5\), and \(\lambda=0.5\); moreover, we set \(d_{\min}=0.01\) and \(d_{\max}=10^{4}\), which are conservative lower and upper estimates of the clustering radii for all windows and all datasets. The implementations of charikar and samp-charikar execute, for a window \(W\), a search for a minimum \(\rho\) such that \(\textsc{outliersCluster}(W,k,\rho,0)\) with unit weights ends with \(\leq z\) uncovered points. For samp-charikar, outliersClusters has been modified so that each new center is selected among a set of random window points of expected size 1000. Tables 1 and 2 detail the full results of the experiments on \(k\)-center clustering with \(z\) outliers. All quantities are provided as one-sigma confidence intervals, based on 10 windows sampled every \(10^{4}\) timesteps after the first \(N\) insertions. Starred results are based on a single sample due to the excessively high running time. Table 1 reports the average ratio between the clustering radius obtained by each tested algorithm and the one obtained by our-sliding, as well as the average number of floats maintained in memory by the algorithms. (All radii have been computed with respect to the entire window, excluding the \(z\) largest distances from the centers.) As shown in the table, our-sliding is always within a few percentage points from the radius of the solution of charikar (which did not finish in reasonable time for \(N=10^{6}\)). On the other hand, the quality of the solution of samp-charikar degrades as the window size grows, since the fraction of center candidates decreases. Moreover, as expected, gon yields a poorer performance, especially in the presence of true outliers, as these are mistakenly selected as centers instead of being disregarded. Hence, gon is not considered in the successive experiments. Figure 1 plots the memory usage (in floats) of the algorithms for Higgs, confirming that the working memory required by our-sliding grows sublinearly with \(N\), and it is much smaller than the one required by charikar and samp-charikar, which is linear in \(N\). Table 2 reports update times (in milliseconds) and query times (in seconds). For our-sliding, the update time is the time required to process any newly arrived point, whereas the query time includes the time to extract the coreset and compute the final solution on the coreset. For charikar and samp-charikar, the update time is null, whereas the query time is the time taken to extract the solution from the whole window.