$k$-Center Clustering with Outliers in the Sliding-Window Model

Clustering is one of the most important tools to analyze large data sets. A well-known class of clustering algorithms is formed by centroid-based algorithms, which include $k$-means clustering, $k$-median clustering and $k$-center clustering. The latter type of clustering is the topic of our paper. In the $k$-center problem one is given a set $P$ of points from a metric space and a parameter $k$, and the goal is to find $k$ congruent balls balls (that is, balls of equal radius) that together cover the points from $P$ and whose radius is minimized. Note that the special case $k=1$ corresponds to the minimum-enclosing ball problem. Data sets in practice often contain outliers, leading to the $k$-center problem with outliers. Here we are given, besides $P$ and $k$, a parameter $z$ that indicates the allowed number of outliers. Thus the radius of the balls in an optimal solution is given by

$\mbox{{\sc opt}}_{k,z}(P)$ := the smallest radius $\rho$ such that we can cover all points from $P$, except for at most $z$ outliers, by $k$ balls of radius $\rho$.

In this paper we study the $k$-center problem with outliers in data streams, where the input is a possibly infinite stream $P=\langle p_{1},p_{2},\ldots\rangle$ of points. The goal is to maintain a solution to the $k$-center problem as the points arrive over time, without any knowledge of future arrivals and using limited (sub-linear) storage. Since we cannot store all the points in the stream, we cannot expect to maintain an optimal solution. Hence, the two main quality criteria of a streaming algorithm are its approximation ratio and the amount of storage it uses. We will study this problem in the sliding-window model. In this model we are given a window length $W$ and we are, at any time $t$, only interested in the points that arrived in the time window $(t-W,t]$. Working in the sliding-window model is often significantly more difficult than working in the standard (insertion-only) streaming model.

The above results are for general metric spaces. In spaces of bounded doubling dimension¹¹1The doubling dimension of a space $X$ is the smallest number $d$ such that any ball $B$ in the space can be covered by $2^{d}$ balls of radius $\operatorname{radius}(B)/2$. better bounds are possible. Indeed, Ceccarello, Pietracaprina and Pucci [DBLP:journals/pvldb/CeccarelloPP19] gave a $(3+\varepsilon)$-approximation algorithm for the $k$-center problem with $z$ outliers, thus improving the approximation ratio $(4+\varepsilon)$ for general metrics. Their algorithm requires $O((k+z)(1/\varepsilon)^{d})$ storage, where $d$ is the doubling dimension of the underlying space (which is assumed to be a fixed constant).

The algorithms mentioned so far are deterministic. Charikar, O’Callaghan, and Panigrahy [DBLP:conf/stoc/CharikarOP03] and Ding, Yu and Wang [DBLP:conf/esa/DingYW19] studied sampling-based streaming algorithms for the Euclidean $k$-center problem with outliers, showing that if one allows slightly more than $z$ outliers then randomization can reduce the storage requirements. Our focus, however, is on deterministic algorithms.

For the $k$-center problem in the sliding-window model, the only result we are aware of is due to Cohen-Addad, Schwiegelshohn and Sohler [DBLP:conf/icalp/Cohen-AddadSS16]. They deal with the $k$-center problem in general metric spaces, but without outliers, and they propose a $(6+\varepsilon)$-approximation algorithm using $O((k/\varepsilon)\log\sigma)$ storage, and a $(4+\varepsilon)$-approximation for the special case $k=2$. Here $\sigma:=\max_{q,q^{\prime}\in X}\operatorname{dist}(q,q^{\prime})/\min_{q,q^{\prime}\in X}\operatorname{dist}(q,q^{\prime})$ denotes the spread of the underling space $X$, and it is assumed that the values $\max_{q,q^{\prime}\in X}\operatorname{dist}(q,q^{\prime})$ and $\min_{q,q^{\prime}\in X}\operatorname{dist}(q,q^{\prime})$ are known to the algorithm. They also prove that any algorithm for the $2$-center problem with outliers in general metric spaces that achieves an approximation ratio of less than $4$ requires $\Omega(W^{1/3})$ space, where $W$ is the size²²2Here the window size $W$ is defined in terms of the number of points in the window, that is, the window consists of the $W$ most recent points. We define the window in a slightly more general manner, by defining $W$ to be the length (that is, duration) of the window. Note that if we assume that the $i$-th point arrives at time $t=i$, then the two models are the same. of the window. Table 1 gives an overview of the known results on the $k$-center problem in the insertion-only and the sliding-window model.

While our main interest is in the $k$-center problem for $k>1$, we will automatically obtain a result for the 1-center problem. Hence, we also briefly discuss previous results for the 1-center problem.

For the 1-center problem in $d$-dimensional Euclidean space, streaming algorithms that maintain an $\varepsilon$-kernel give a $(1+\varepsilon)$-approximation. An example is the algorithm of Zarabi-Zadeh [z-cpa-08] which maintains an $\varepsilon$-kernel of size $O(1/\varepsilon^{(d-1)/2}\log(1/\varepsilon))$. Moreover, using only $O(d)$ storage one can obtain a 1.22-approximation for the 1-center problem without outliers [DBLP:journals/algorithmica/AgarwalS15, cp-sdameb-14]. For the 1-center problem with outliers, one can obtain a $(1+\varepsilon)$-approximation algorithm that uses $z/\varepsilon^{O(d)}$ storage using the technique of Agarwal, Har-Peled and Yu [DBLP:journals/dcg/AgarwalHY08]. Zarrabi-Zadeh and Mukhopadhyay  [DBLP:conf/cccg/Zarrabi-ZadehM09] studied the $1$-center problem with $z$ outliers in high-dimensional Euclidean spaces, where $d$ is not considered constant, giving a $1.73$-approximation algorithm that requires $O(d^{3}z)$ space. Recently, Hatami anad Zarrabi-Zadeh [DBLP:journals/comgeo/HatamiZ17] extended this result to $2$-center problem with $z$ outliers, obtaining a $(1.8+\varepsilon)$-approximation using $O(d^{3}z^{2}+dz^{4}/\varepsilon)$ storage. None of the 1-center algorithms discussed above works in the sliding-window model.

As problem that is closely related to the 1-center problem is the diameter problem, where the goal is to maintain an approximation of the diameter of the points in the stream. This problem has been studied in the sliding-window model by Feigenbaum, Kannan, Zhang [DBLP:journals/algorithmica/FeigenbaumKZ04] and later by Chan and Sadjad [cs-gosw-06], who gave a $(1+\varepsilon)$-approximation for the diameter problem (without outliers) in the sliding window model, using $O((1/\varepsilon)^{(d+1)/2}\log(\sigma/\varepsilon))$ storage.

As in the previous papers on the $k$-center problem (or the diameter problem) in the sliding-window model [cs-gosw-06, DBLP:conf/icalp/Cohen-AddadSS16, DBLP:journals/algorithmica/FeigenbaumKZ04], we assume that the values $\max_{q,q^{\prime}\in X}\operatorname{dist}(q,q^{\prime})$ and $\min_{q,q^{\prime}\in X}\operatorname{dist}(q,q^{\prime})$ are known to the algorithm. A typical example is when the input consists of points in $d$-dimensional Euclidean space with integer coordinates in a given range $\{0,1,\ldots,U\}$. In this example, the spread is $\Theta(U)$.

Let $P:=\langle p_{1},p_{2},\ldots\rangle$ be a possibly infinite stream of points from a metric space $X$ of doubling dimension $d$ and spread $\sigma$, where $d$ is considered to be a fixed constant. We denote the arrival time of a point $p_{i}$ by $\and(p_{i})$. We say that $p_{i}$ expires at time $t_{\mathrm{exp}}(p_{i}):=\and(p_{i})+W$, where $W$ is the given length of the time window. To simplify the exposition, we assume that all arrival times and departure times (that is, times at which a point expires) are distinct. For a time $t$ we define $P(t)$ to be the set⁴⁴4We allow the same point from $X$ to occur multiple times in the stream, so $P(t)$ is actually a multi-set. Whenever we refer to “sets” in the remainder of the paper we mean “multi-sets”. of points currently in the window. In other words, $P(t):=\{p_{i}:\and(p_{i})\leqslant t<t_{\mathrm{exp}}(p_{i})\}$. For a point $q\in X$ and a parameter $r\geqslant 0$, use $\operatorname{ball}(q,r)$ to denote the ball with center $q$ and radius $r$.

In the following we show how to maintain a sketch $\Gamma(t)$ of $P(t)$ for the $k$-center problem with outliers. We first present a sketch for a decision version of the problem. (Actually our sketch is a bit more powerful than a decision algorithm, as explained below.) Given this sketch, it will be easy to develop a sketch for the optimization version of the problem.

We presented the first sketch for the $k$-center problem with outliers in the sliding-window model. We assumed that the points in the stream come from a finite space $X$ of bounded doubling dimension and spread $\sigma$, such as points in $\mathbb{R}^{d}$ with integer coordinates from the set $\{0,\ldots,U\}$ with $U:=\lfloor\sigma/\sqrt{d}\rfloor$. Alternatively, we can assume that we are given a range $[\mbox{{\sc opt}}_{\min},\mbox{{\sc opt}}_{\max}]$ of possible values for $\mbox{{\sc opt}}_{k,z}(P(t))$. Assuming we also have a subroutine available to compute (a $(1+\varepsilon)$-approximation of) $\mbox{{\sc opt}}_{k,z}(S)$ for any given static set $S$, we can then decide if $\mbox{{\sc opt}}_{k,z}(P(t))\in[\mbox{{\sc opt}}_{\min},\mbox{{\sc opt}}_{\max}]$, and, if so, give a $(1+\varepsilon)$-approximation of $\mbox{{\sc opt}}_{k,z}(P(t))$. The storage will be as stated in Theorem 2.6, with $\sigma:=\mbox{{\sc opt}}_{\max}/\mbox{{\sc opt}}_{\min}$.

Our sketch has low storage when $z$, the number of outliers, is not too large. It would be interesting to see if the dependency on $z$ in the storage requirements reduced. A first step would be to see if it is possible to refine our approach to obtain a sketch with $O((k+z)/\varepsilon^{d})$ storage, saving a factor $z$. Reducing the dependency on $z$ to sublinear may be possible using a random-sampling approach, if one is willing to allow slightly more than $z$ outliers. Another challenging open problem is to develop a sketch whose storage is only polynomially dependent on the doubling dimension $d$.