Clustering with Outliers on Sliding Windows

We study sliding window algorithms for $(k,z)$-clustering with $m$ outliers in Euclidean spaces, and focus on constructing $ϵ$-coresets, which is a powerful notion of data reduction for clustering. Our main result is an algorithm that maintains an $ϵ$-coreset of size $\tilde{O}(k/\min \{{ϵ}^4,{ϵ}^{2+z}\}+2^{O(z\log (z+1))}(d^z+kd)m/ϵ)$, and this readily yields a $(1+ϵ)$-approximate solution center set. We evaluate our algorithm for $k$-means with outliers on five real data sets with injected outliers, the experiment result shows that it has lower empirical cost than uniform sampling and coreset for vanilla $k$-means at every tested coreset size.