# _k_-Center Clustering with Outliers in Sliding Windows
### Our Contribution  
We present approximation algorithms for the \(k\)-center with \(z\) outliers in the sliding window setting, which feature constant approximation ratios and small working memory requirements and update times. As is customary for clustering in the big data realm, our algorithms hinge on the maintenance of a _coreset_, that is, a small subset of representative points of the current window from which an accurate solution can be extracted. Crucial to the effectiveness of our approach is the introduction of _weights_ for coreset points, where the weight of a point is (an estimate of) the number of window points it represents. To efficiently maintain the weights, we employ a succinct data structure inspired by the smooth histograms of [27], which enable considerable space savings if some slackness in the account of outliers is permitted. As an interesting by-product, we also devise an algorithm that employs our coresets to approximate the \(\alpha\)-effective diameter of the current window \(W\).  
The analysis of our algorithms is carried out as a function of two design parameters, \(\delta\) and \(\lambda\), which control, respectively, the level of accuracy and the slackness in the account of outliers, and as a function of a number of characteristics of the stream \(S\), namely, the values \(d_{\min}\) and \(d_{\max}\), representing the minimum and the maximum distance of two distinct points of \(S\) and the doubling dimension \(D\) of \(S\).  
Our main results are listed below.  
* A sliding window algorithm for general metric spaces that, at any time, is able to return a set of centers covering all but at most \(z(1+\lambda)\) points of the current window \(W\), within a radius that is an \(O(1)\) factor larger than the optimal radius for \(z\) ouliers. The algorithm requires a working memory of size \(O\left(\log(d_{\max}/d_{\min})(k+z)\log_{1+\lambda}(|W|)\right)\) and processes each point in time linear in the working memory size. By setting \(\lambda=1/(2z)\), the number of uncovered points becomes, at most, \(z\);
* An improved algorithm with the same coverage guarantee as above, featuring a radius that is only a factor \((3+O(\delta))\) larger than the optimal radius, at the expense of an extra \(O((c/\delta)^{D})\) factor in both the working memory size and update time, for a suitable constant \(c\);
* A sliding-window algorithm for streams of bounded doubling dimension that, starting from a (possibly crude) lower bound on the ratio between the \(\alpha\)-effective and the full diameter of the window \(W\), returns upper and lower upper bounds to the \(\alpha\)-effective diameter of \(W\). The algorithm features accuracy-space tradeoffs akin to those of the improved algorithm for 1-center with \(z=0\) outliers;
* Experimental evidence that both the improved \(k\)-center and the effective diameter algorithms feature a good performance and provide accurate solutions.  
It is important to remark that our algorithms are _fully oblivious_ to the metric parameters \(d_{\min}\), \(d_{\max}\), and \(D\), in the sense that the actual values of these parameters only influence the analysis but are not needed for the algorithms to run. This is a very desirable feature, since, in practice, these values are difficult to estimate.  
Compared to the algorithm of [23] for \(k\)-center with \(z\) outliers, our algorithms feature a considerably lower update time, which makes them practically viable. Moreover, in the case of noisy streams for which \(z=\Omega(\log|W|)\), our algorithms require considerably less working memory, as long as some slackness in the number of outliers can be tolerated. Finally, whereas the algorithm of [23] requires the knowledge of \(d_{\min}\) and \(d_{\max}\), our algorithms are oblivious to these values.