# _k_-Center Clustering with Outliers in Sliding Windows
## 3 \(k\)-Center with \(z\) Outliers
### Weighted Coreset Construction
#### 3.1.1 Algorithm
}\tilde{w}(r_{1})\tilde{w}(r_{2}) \geq\alpha|W|^{2},\]

we have that

\[\sum_{ \begin{subarray}{c}r_{1},r_{2}\in T:\\ \text{dist}(r_{1},r_{2})\leq d\end{subarray} }w(r_{1})w(r_{2})\geq\alpha|W|^{2},\]

which implies \(\Delta^{\alpha}_{T,W}\leq\tilde{\Delta}^{\alpha}_{T,W}\). The bounds on the working memory and on the update time follow directly from Theorem 4 and from the choice of \(k=1\) and \(z=0\). Finally, the estimates\(\tilde{\Delta}_{T,W}^{\alpha/(1+\lambda)^{2}}\) and \(\tilde{\Delta}_{T,W}^{\alpha}\) can be computed from \(T\) in time \(O\big{(}|T|^{2}\big{)}=O\big{(}(c^{\prime}/(\varepsilon\eta))^{2D}\big{)}\) using a simple strategy based on binary search. The theorem implies that by setting \(\varepsilon\) and \(\lambda\) sufficiently small, we can obtain tight estimates for \(\Delta_{W}^{\alpha}\) for all windows for which the value of the \(\alpha\)-effective diameter behaves smoothly in an interval to the left of \(\alpha\). Finally, we remark that the algorithm is fully oblivious to \(D\), \(d_{\min}\), and \(d_{\max}\). Moreover, while the theoretical space bound exhibits a dependency on \((1/\eta)^{D}\), in the next section, we provide experimental evidence of a much lesser impact of \(\eta\) for datasets where outliers represent true noise, proving that the working space requirements exhibit a milder dependence on the crudeness of the lower bound \(\eta\). ## 5 Experiments

We implemented the algorithms for \(k\)-center with \(z\) outliers and for the estimation of the effective diameter presented in Sections 3 and 4. For what concerns \(k\)-center with \(z\) outliers, we implemented the dimensionality-sensitive algorithm of Section 3.4, which offers a wider spectrum of performance-accuracy tradeoffs. We ran proof-of-concept experiments aimed at testing the algorithms' behavior against relevant competitors in terms of approximation, memory usage, and running time for processing each point arrival (_update time_) and for computing a solution for the current window whenever needed (_query time_). All tests were executed using Java 13 on a Windows machine running on an AMD FX8320 processor with 12 GB of RAM, with the running times measured using System.nanoTime, and with the points to the algorithms being fed through the file input stream. ### \(k\)-Center with Outliers

Along with our algorithm (dubbed our-sliding), we implemented the sequential 3-approximation by [7] (dubbed charikar) to be run on the entire window \(W\), consisting of a search for the minimum \(\rho\) such that outliersCluster\((W,k,\rho,0)\), run with unit weights, ends with, at most, \(z\) uncovered points. We chose this sequential benchmark over the existing LP-based 2-approximation algorithms since these latter algorithms do not seem to admit practical implementations. Since charikar itself is plagued by a superquadratic complexity, which makes it unfeasible for larger windows, we also devised a sampled version (dubbed samp-charikar) where the center selection in each call to outliersCluster examines only a fixed number of random candidates, rather than all window points. We deemed it unnecessary to perform a comparison of our algorithm with the one in [23], since, as mentioned in the introduction, this latter algorithm needs to run an instance of outliersCluster for each update operation, and would thus prove to be a poor competitor of our strategy, where the execution of this expensive sequential procedure is confined only to the query operation. Also, to assess the importance of using a specialized algorithm to handle outliers, we compared the quality of our solution against the one returned by the algorithm of [12] for \(k\)-center without outliers (dubbed gon), where the radius is computed excluding the \(z\) largest distances from the centers.