The Expiration Streaming Model: Diameter, $k$-Center, Counting, Sampling, and Friends

The first problems we consider in the general expiration model are some fundamental streaming problems that are standard building blocks for solving many other problems, thereby gaining a better understanding of the challenges when designing algorithms in our new model. We start with counting, which formally asks for the number of active $1$’s in a stream of items from the universe $U=\{0,1\}$. For exact counting, $\mathrm{\Omega }(n)$ bits of space are required, even in the consistent expiration model; which follows from the known bound for the sliding-window model [19], in contrast with insertion-only streams, where $𝒪(\log n)$ bits clearly suffice.¹¹1An alternative definition, which asks to count the total number of active items, exhibits strict separation between the sliding-window and expiration models. In the sliding-window model (without blank time steps), the answer is always $w$ and thus $𝒪(1)$ space suffices, whereas with expirations, even consistent ones, the lower bound of $\mathrm{\Omega }(n)$ bits still holds. Due to these lower bounds, we turn to approximate counting. We design two randomized streaming algorithms, one achieves $\epsilon$-additive error using $𝒪({\epsilon }^{-1})$ space, and the other $\epsilon$-relative error using $\widetilde{𝒪}({\epsilon }^{-1}\log (\epsilon n))$ space,²²2Throughout, the notation $\widetilde{𝒪}(f)$ hides logarithmic factors in $f$. by employing powerful tools of insertion-only streams, like quantile sketches. Moreover, we show that these space bounds are tight. Approximate counting is a useful primitive when designing other algorithms. We demonstrate this by designing a Count-Min sketch [18], which solves frequency estimation (aka point queries) with $\epsilon$-additive error, and thus also ${\mathrm{\ell }}_1$-heavy-hitters, using $𝒪({\epsilon }^{-2})$ space.

Another fundamental problem is to sample $k$ items uniformly from the stream. In insertion-only and sliding-window streams, this can be done via reservoir sampling [34, 5]. We build on this technique to present an algorithm for the expiration model that uses $𝒪(k\log n)$ space, and further present extensions to two more challenging tasks: sampling without replacement, and weighted sampling, where each item is sampled with probability proportional to its weight. Sampling tasks are useful primitives, and we indeed use them to design other algorithms, e.g., for approximate quantiles with $\epsilon$-additive error using $𝒪({\epsilon }^{-2}\log n)$ space. We also use them for geometric problems, such as range counting, logistic regression, and kernel density estimation (KDE); here, items are points in ${ℝ}^d$, and our algorithms use space $𝒪({\epsilon }^{-2}\log n)$, assuming for simplicity that parameters such as $d$ and the VC-dimension are $𝒪(1)$. Moreover, these sampling methods apply to matrix-approximation problems, where each stream item is a row vector in ${ℝ}^d$, including rank-$k$ approximation and $\epsilon$-covariance error.

Technically, these results are less involved and build heavily on prior work. They also leave several questions for further investigation. For example, our algorithms often use more space than the analogous ones for insertion-only and turnstile streams, and thus may possibly be improved, e.g., better dependence on $\epsilon$. Note that for frequency estimation in sliding-window streams, near-optimal bounds are known [8]. Furthermore, our techniques do not yield Count-Sketch-type bounds [15] for ${\mathrm{\ell }}_2$-point queries and ${\mathrm{\ell }}_2$-heavy-hitters, which are known for sliding-window streams [8, 24]. We are also not aware of any strict separation (in space complexity) between consistent and general expirations.

Our main results (which are technically more challenging) are for the diameter and $k$-center problems in a general metric space $ℳ$, where $d_{ℳ}$ denotes its distance function and the subscript may be omitted when clear from the context. In the streaming setting, the metric $ℳ$ is fixed in advance and each item $x$ contains a data point $p(x)\in ℳ$, and recall that we may identify $p(x)$ with $x$ and write $x\in ℳ$. To avoid precision issues, we assume that $d_{ℳ}(x,y)\in [1,\mathrm{\Delta }]$ for all distinct $x,y\in ℳ$.³³3Our results hold even if we allow $d_{ℳ}(x,y)=0$, i.e., $ℳ$ is a pseudometric. In fact, the same point may arrive multiple times, possibly with different expirations.

In the diameter problem, the goal is to compute $\mathrm{diam}(X):=\max \{d(x,y)\mid x,y\in X\}$ for the set $X\subset ℳ$ of active items. We devise an algorithm for this problem in the expiration model; it significantly extends the previously known algorithm, that works in the more restricted sliding-window model [17], while achieving the same approximation factor and space complexity. We prove the following in Section 3.

Our approximation factor is almost tight, as even in the sliding-window model, achieving a $(3-\epsilon )$-approximation for the diameter for any fixed $\epsilon >0$ requires $\mathrm{\Omega }(\sqrt[3]{n})$ space [17].⁴⁴4It is easy to see that $𝒪(1)$-approximation requires space complexity $\mathrm{\Omega }(\log \mathrm{\Delta })$ already in sliding-window streams, e.g., consider the one-dimensional input where the $i$-th point is either $2^i$ or $0$ [23].

We further improve the approximation factor to $1+\sqrt{3}+ϵ\approx 2.73$ when the metric space $ℳ$ is Euclidean, regardless of the dimension (we only require that each point can be stored in a machine word). Previously, an approximation factor below $3$ was not known for the Euclidean case, even in sliding-window streams.

Finally, we turn to the $k$-center problem, where the goal is to compute

where $d(x,C):={\min }_{c\in C}d(x,c)$ is the distance from a point $x$ to its closest point in a set $C$.

We present an algorithm for the expiration model that achieves a $(6k+2)(1+\epsilon )$-approximation using $𝒪({\epsilon }^{-1}{k}^2\log \mathrm{\Delta })$ words of space. In comparison, previous work achieved $(6+\epsilon )$-approximation using $𝒪({\epsilon }^{-1}k\log \mathrm{\Delta })$ words in the significantly more restricted sliding-window model [17]. We prove the following in Section 4.

For $k=1$, we use our diameter algorithm to achieve an improved approximation factor of $4+\epsilon$ in a general metric (Theorem 3.2) and $1+\sqrt{3}+\epsilon$ in Euclidean space (Theorem 3.6). All our algorithms report not only an objective value but also a feasible solution, i.e., a pair of points (that is approximately the farthest) or a set of $k$ center points. Table 1 lists the known approximation factors for diameter and $1$-center in high-dimensional Euclidean space under different streaming models, including our new expiration model, and two more restricted ones of sliding-window and insertion-only streams. (We restrict the table to $k=1$ and the Euclidean case to minimize clutter.)

Many results and proofs are omitted from this version due to space constraints. They can be found in the full version.

In the study of dynamic data structures, the semi-online model allows for insertions and deletions where the time of deletion is provided at the time of insertion. Here, unlike the sketches we study, no approximation is generally allowed, and the focus is instead on reducing the running time of various operations. In particular, Dobkin and Suri [22] employed the method of Bentely and Saxe [6] under a data structure that can be constructed in time $P(n)$ and can handle queries in time $Q(n)$, in order to handle insertions and deletions in this semi-online model in $𝒪(\log n)$ time while increasing the query time to $𝒪((P(n)/n+Q(n))\log n)$. Several linear and near-linear space algorithmic improvements followed, where the focus is primarily on exact methods and improved update times. Notably, Chan [12] provided improvements for several problems in computational geometry, including discrete $1$-center in $2$ dimensions with slightly sublinear updates.

The database community studied persistent sketches (for streaming), where queries may be restricted to subsets of data in certain time windows [36]. Within this setting, Shi, Zhao, Peng, Li, and Phillips [33] considered at-the-time persistence (ATTP) and back-in-time persistence (BITP) models, where the time window of a query must include the first or last time, respectively (in other words, queries about any prefix or any suffix of the streams). Notably, the BITP model can be interpreted as a sliding-window query that specifies the window size $w$ at query time (rather than in advance). This is closely related to consistent expirations, especially if all expirations occur after all relevant insertions. All methods we are aware of for the consistent expiration model should work for this BITP model.

In this context, Shi et al. [33] studied a variety of problems related to weighted counting and sampling, where each item $x_i$ is associated with a weight $w_i$ (it could be uniform), and the desired error bound is an additive $\epsilon W$ where $W={\sum }_i{w}_i$ is the total weight. This setting is very useful in standard sketching bounds for frequency estimation, quantiles, approximate range counting, kernel density estimates, and matrix-covariance sketching, which we study as well. In particular, they show that a random sample of size $k$ can be maintained in $𝒪(k\log n)$ expected space with $𝒪(\log k)$ expected amortized update time. If the items are selected at random proportionally to their weight and the weights are in the range $[1,U]$, then the expected space is $𝒪(k\log (nU))$. Their methods for BITP use a sampling-in-reverse analysis, which was discovered earlier by Braverman et al. [7] in the context of sliding-window linear-algebra problems, and also used later for sampling Lewis weights in sliding-window streams [37]. Moreover, they show that for mergeable sketches [1] of size $s(\epsilon )$, a BITP sketch of size $𝒪({\epsilon }^{-1}\log n\cdot s(\epsilon ))$ can be maintained.

Our results extend these ideas to the general expiration model, and formalize the proofs in the full version of this paper. Dealing with general expirations requires finding the relevant tools (in prior literature) and additional ideas, to manage samples that expire in a completely different order than their arrivals.

The sliding-window model has been studied extensively, including for frequency and counting problems, maintaining aggregate statistics, and for geometric and graph problems. An extremely popular technique for designing sliding-window streaming algorithms is the smooth-histogram framework of Braverman and Ostrovsky [10]. For monotone functions $f$ that satisfy a certain smoothness property, they show how to convert an algorithm that estimates $f$ in insertion-only streams into an algorithm that estimates $f$, using slightly more space, in sliding-window streams. This framework has been successfully employed for many different problems, from counting and frequency problems to graph problems, but not for geometric problems, which are often not smooth, e.g., $k$-median and $k$-means clustering [9]. Krauthgamer and Reitblat [31] defined a relaxation of this smoothness property, called almost-smoothness, which is still sufficient to convert algorithms from insertion-only to sliding-window streams, albeit with a bigger loss in the approximation factor. It is not difficult to see that the diameter problem, in a general metric space, is $2$-almost-smooth, and since it admits a folklore $2$-approximation in insertion-only streams, the conversion of [31, Theorem 1.7] also implies an $(8+\epsilon )$-approximation in sliding-window streams. Although immediate, this bound is worse than the known $(3+\epsilon )$-approximation for diameter [17]. Unfortunately, this entire framework seems inapplicable to general expirations.

Clustering problems have been studied extensively in the streaming model. The metric $k$-center problem was studied in insertion-only streams, culminating in a $(2+\epsilon )$-approximation [14, 32, 25], and further extensions to $k$-center with outliers. In Euclidean space of high dimension $d$, i.e., when the space bound is restricted to be polynomial in $d$, better approximation factors are known, particularly for $k=1$ and for diameter [38, 3, 13, 29, 26], and for small $k$ [30]; see Table 1 for the precise constants. These results were extended to sliding-window streams in [17, 35] as mentioned above. However, they usually do not extend to dynamic streams, which seem harder.

In low Euclidean dimension, i.e., when allowing a space bound that grows exponentially with $d$, several results achieve a $(1+ϵ)$-approximation for $k$-center [2, 11]. These results often extend to dynamic and sliding-window streams, and to handle outliers [21, 20]. Some of the above references prove near-matching lower bounds, but usually for algorithms that must store input points [25, 3, 20], i.e., these are not bit-complexity bounds for general algorithms.

Let $p$ and $q$ be items of the stream. We say that $p$ is dominated by $q$ if and $E(p)\le E(q)$, i.e., for the entire time that $p$ is active, $q$ is active as well. An item that is not dominated by any other item is called long. See Figure 1 for illustration. Note that it is easy to decide with $𝒪(1)$ words of space whether an arriving item is dominated or long, by keeping track of the latest expiration time among all the items that have arrived so far.

Consider first the substream consisting of all long items, and notice that its expirations are consistent. It is easy to show that the sliding-window algorithm of [17] generalizes to the consistent expiration case, and so we can use it as a subroutine for the long items. For an item $q$ that is not long, suppose that it is geometrically close to some long item $p$ that dominates it. Then we can simply ignore $q$ and use $p$ as a proxy for it: geometrically, they are close, and timewise, $p$ is active whenever $q$ is active. In the other case, i.e., if $q$ is far from $p$, then the pair $p,q$ may be a candidate for the diameter as long as $q$ is active, and thus we need to keep track of such pairs.

More precisely, for a dominated item $q$, let us assign one long item that dominates $q$ as its parent. Again, this is easy to implement, as soon as $q$ arrives, using $𝒪(1)$ words of space. Now there can be two cases:

1. (a)

   Every dominated point is close to its parent (say up to a small constant fraction of the diameter). In this case, the diameter of the long items is a constant-factor approximation to the diameter of all items (by simple triangle-inequality arguments).

2. (b)

   At least one dominated point is far from its parent. To keep track of this scenario, we store an array $A$, where each entry $A[j]$ maintains a pair of points, namely, a dominated point $p$ and its parent $q$, selected as follows: from all such pairs where also $d(p,q)\in [{(1+\epsilon )}^j,{(1+\epsilon )}^{j+1})$, select the pair for which the expiration time of $p$ is the latest. The size of this array is only $𝒪((1/\epsilon )\log \mathrm{\Delta })$.

The above reasoning suffices to obtain a constant-factor approximation of the diameter in the general expiration model, however it does not match the approximation factor $3+\epsilon$ that is known for the sliding-window setting.

To improve the constant, we replace the black-box subroutine for consistent expirations that is used to handle the long items. Our redesigned subroutine is conceptually different from the sliding-window algorithm of [17] and allows for a tighter integration with the array $A$, which seems not possible using the algorithm of [17]. If space complexity is not a concern, then long items can be handled by simply having every long point $p$ track the maximum distance to any point inserted after it and not dominated by it, which we call the radius of $p$. From this information, we can retrieve the exact diameter of the long items. The main insight to achieve the claimed space bound is that if a long point $p$ is “sandwiched” between two points with a similar radius, one inserted before $p$ and the other after, then we can discard $p$ while only losing a constant factor in the approximation guarantee.

In addition, we again store an array $A$ that captures the distances of dominated items to long items. In contrast to the above, we do not assign a particular parent to each dominated point $p$. Rather, when $p$ arrives, we consider its distance to all stored long items that dominate $p$. A more involved analysis shows that this improves the approximation factor to $3+\epsilon$, matching the best approximation factor known also for the sliding-window model, while using the same space bound.

An additional advantage of our new subroutine for the consistent expiration case is that it admits further improvements in the Euclidean space. In general metric space, the algorithm stores a radius $r$ for every stored long item $p$ to bound the distance between $p$ and the set $S$ of points that are inserted after $p$ and are not dominated by $p$. In Euclidean space, the algorithm additionally stores for every $p$ a carefully chosen point $\tilde{p}$, whose distance to points in $S$ is at most $r$ as well. Hence, $S$ lies in the intersection of two balls of radius $r$, instead of only one ball of radius $r$. Since the distance between $p$ and $\tilde{p}$ is bounded, we can further improve the approximation factor for both consistent and general expirations. In fact, this is strictly better than the best approximation known (and possible) for general metrics, even in the sliding-window model. See Section 3 for details.

We define $D_1$ as the substream containing all long points $p$, as well as each point $q$ that is geometrically close to a long point $p$ in $D_1$ that dominates it. If a point $q$ is not geometrically close to any long point in $D_1$ that dominates it, then $q$ is fed to the second substream $D_2$. All points passed on to $D_2$ are then processed in the same manner as for $D_1$, and the residual points not handled by $D_2$ are again passed to the next layer, etc. If a point is rejected from the final substream $D_k$, it is discarded. If each substream is allowed to use unlimited space, then there is no need to discard any long items and we can show that $k$ substreams are sufficient. If a point $q$ is rejected from all $k$ substreams $D_1,\mathrm{\dots },D_k$, then there is a sequence of points $p_1,\mathrm{\dots },p_k$ such that

1. (i)

   $p_i$ belongs to the $i$th substream,

2. (ii)

   these $k$ points (as well as $q$) are pairwise geometrically far away from each other,

3. (iii)

   the points are nested timewise, i.e., $p_{i+1}$ is dominated by $p_i$ and $q$ is dominated by $p_k$.

As long as $q$ is not expired, then all points $p_1,\mathrm{\dots },p_k$ are also active, which provides a certificate that any solution for $k$-center must have a large value with respect to $\gamma$. Thus, there is no need to keep $q$, and more generally, to maintain more than $k$ substreams.

To bound the space within each substream, a naive approach would be to apply the algorithm of [17] to each substream independently. However, because the pruning of long items is not coordinated between the substreams, it becomes impossible to maintain conditions (ii) and (iii) simultaneously. Consider three points $p_i$, $p_j$, $p_{\mathrm{\ell }}$ with such that $p_i$ is discarded between the insertions of $p_j$ and $p_{\mathrm{\ell }}$. Then the algorithm cannot check whether $p_{\mathrm{\ell }}$ is geometrically close to $p_i$, so condition (ii) may be violated. If $p_i$ is replaced with another point $p_i^{\prime }$ from $D_i$, then it cannot be guaranteed that $p_i^{\prime }$ dominates $p_j$, so condition (iii) may be violated. Thus, a more coordinated approach is needed.

Our goal is to maintain a set of points $p_1,\mathrm{\dots },p_k$ that satisfy conditions (i)–(iii), while bounding the space usage of the algorithm within each substream and the total number of substreams. If we define $p_i$ as the longest-living point in $D_i$, then this set of points satisfies conditions (i) and (iii). To restore condition (ii), we discard points from $D_i$ if they are geometrically close to points from substreams $D_j$ with that are inserted later. This provides the coordination between the different substreams that was lacking in the naive approach, but it creates two new issues.

The first issue arises when our algorithm does not store a point $p$ in substream $D_i$ because it is close to another point $p_i^{\prime }$ in $D_i$ (in which case we consider $p$ to be covered by $p_i^{\prime }$ in $D_i$). Later on, we may have to discard $p_i^{\prime }$ to ensure condition (ii) because it is close to another point $p_j^{\prime }$ from a substream $D_j$ with . We then consider $p$ to be covered by $p_j^{\prime }$ instead, but this increases the distance between $p$ and the point that covers it by a constant factor. Because $p_j^{\prime }$ may itself be discarded later on to ensure condition (ii), this effect can cascade up to $k$ times, which increases the approximation guarantee to $𝒪(k)$.

The second issue is that the longest-living point from a substream $D_i$ may need to be discarded to restore condition (ii), and this can in turn cause condition (iii) to be violated because the points $p_1,\mathrm{\dots },p_k$ are no longer nested. We restore the condition by moving the longest-living point among all substreams $D_j$ with $j>i$ to $D_i$. Note that this may potentially violate condition (ii) again. However, we show that a single sweep over all substreams suffices to restore both conditions. For a more detailed overview of the algorithm, see Section 4.

Each time an item $(p,S,E)$ is inserted, we use Algorithm 1 to update the data structure. If the item is long, we store it. Line 5 ensures that for each stored (long) item $q_i$, the radius $r_i$ is correct: if $q_i$ does not dominate the new item $p$ and the distance from $q_i$ to $p$ is larger than $r_i$, we update the radius to be this distance. Otherwise, if $q_i$ dominates $p$, then for the value of $j$ such that their distance is in $[{(1+\epsilon /3)}^j,{(1+\epsilon /3)}^{j+1})$, the algorithm updates $A[j]$ to $\max \{A[j],E(p)\}$ (lines 7–8).

To achieve our bound on the number $k$ of the stored items, we further discard all stored items that are inserted between two stored items with a similar radius. In particular, if $q_i$ and $q_j$ with $i\le j$ are two stored points such that $(1+\epsilon /3)\cdot r_j>r_i$, then we discard all items $q_t$ with $t\in \{i+1,\mathrm{\dots },j-1\}$. Finally, at the end of the update procedure of adding an item, we reindex the stored items starting from $1$, keeping their order.

As long as at least two items are stored, the algorithm maintains the invariant that for the current time step $T$. In the time step $T=E(q_2)$, the algorithm discards $q_1$ from the data structure along with its radius $r_1$. The remaining items are reindexed starting from $1$, keeping their order. As all stored items are long, at each time step at most one stored item expires.

At time $T$, we report $r=\max \{r_2\}\cup \{{(1+\epsilon /3)}^j\mid A[j]>T\}$ as an approximation to the diameter if $q_2$ exists. Otherwise, there are no active points in the stream at time $T$. We show that this is a $(3+\epsilon )$-approximation.

Because $q_{i-1}$ and $q_i$ are consecutive, any long item that was inserted between them has been discarded. If no such long item exists, then the claim follows because there is no item $p$ with and . Otherwise, let $T$ be the time at which the last long item between $q_{i-1}$ and $q_i$ is discarded. Denote with $r_{i-1}^T$ (resp. $r_i^T$) the radius stored at time $T$ for the point which is now $q_{i-1}$ (resp. $q_i$). Then, holds due to line 11. In particular, for every item $p$ with and , it holds that $d(q_{i-1},p)\le r_{i-1}^T\le (1+\epsilon /3)\cdot r_i^T$. The radius corresponding to point $q_i$ can only increase afterwards, so the claim follows. $◀$

To show that the algorithm achieves $(3+\epsilon )$-approximation, we analyze different cases based on the insertion and expiration times of the items that realize the diameter.

By lines 11–13 of Algorithm 1, it holds that $(1+\epsilon /3)\cdot r_{i+2}\le r_i$ for each $i\in [k-2]$. Therefore, $k\in 𝒪({\log }_{1+\epsilon /3}\mathrm{\Delta })$. The size of the array $A$ is in $𝒪({\log }_{1+\epsilon /3}\mathrm{\Delta })$. The space bound follows, since $𝒪({\log }_{1+\epsilon /3}\mathrm{\Delta })=𝒪((1/\epsilon )\log \mathrm{\Delta })$.

Let $T$ be the current time. If there does not exist a stored point $q_2$, then all long items are expired at time $T$. Therefore, all items are also expired and there are no active items at time $T$. Otherwise, let $j$ be the maximum value such that $A[j]>T$. Then, the query algorithm at time $T$ returns $r=\max \{r_2,{(1+\epsilon /3)}^j\}$. By our invariant, $q_2$ has not yet expired at time $T$. As $r_2$ is the radius corresponding to $q_2$ and $q_2$ is still active, there exists an item $p$ with $S(p)\ge S(q_2)$ and $E(p)>E(q_2)$ such that $d(p,q_2)=r_2$. Similarly, if $j$ exists, there exist two items $p$ and $p^{\prime }$ with $E(p^{\prime })\ge E(p)=A[j]>T$ such that $d(p,p^{\prime })\ge {(1+\epsilon /3)}^j$. Hence, the diameter at time $T$ is at least $r$. It remains to prove that the diameter is at most $(3+\epsilon )r$. We first show that the following holds for every item $p$ that is active at time $T$:

1. (1)

   If $S(p)\le S(q_2)$, then $d(p,q_1)\le (1+\epsilon /3)r$ by Lemma 3.1.

2. (2)

   If $S(p)\ge S(q_2)$, then $d(p,q_2)\le (1+\epsilon /3)r$: If , then we have $d(q_2,p)\le r_2\le r$, since $r_2$ is the radius of the smallest ball centered at $q_2$ that contains all items that were inserted after $q_2$ and expire after $q_2$. Otherwise, we have and by the definition of $A[j]$.

Now, let $p$ and $p^{\prime }$ with $S(p)\le S(p^{\prime })$ be the items that realize the diameter at time $T$. As all stored items are long and , it holds that . We consider the following three cases to prove that $d(p,p^{\prime })\le (3+\epsilon )r$.

1. a)

   If then $d(p,p^{\prime })\le d(p,q_1)+d(q_1,p^{\prime })\le (2+\epsilon )r$ by (1).

2. b)

   If then $d(p,p^{\prime })\le d(p,q_1)+d(q_1,q_2)+d(q_2,p^{\prime })\le (3+\epsilon )r$ by (1), (2).

3. c)

   Otherwise $S(p)\ge S(q_2)$. Then $d(p,p^{\prime })\le d(p,q_2)+d(q_2,p^{\prime })\le (2+\epsilon )r$ by (2).

$◀$

The same algorithm approximates also the minimum enclosing ball.

Let $r$ be the returned radius at time $T$, i.e., $r=\max \{r_2\}\cup \{{(1+\epsilon /3)}^j\mid A[j]>T\}$. By construction of $r_2$ and $A$, it holds that there are two items that are active and have distance at least $r$. Hence, the diameter is at least $r$ at time $T$. Let $p$ and $p^{\prime }$ with be the items that realize the diameter at time $T$. Similarly to the proof of Theorem 1.1, we consider different cases for the values of $S(p)$ and $S(p^{\prime })$.

1. a)

   If $S(p)\ge S(q_2)$, then $d(p,p^{\prime })\le 2r$, by the same arguments as in the proof of Theorem 1.1.

2. b)

   If , then $d(p,p^{\prime })\le d(q_1,p)+d(q_1,p^{\prime })\le (2+\epsilon )d({\tilde{q}}_2,q_2)\le (2+\epsilon )r$ by Lemma 3.3.

3. c)

   Otherwise, . Then, it holds that $d(p,p^{\prime })\le d(p,q_1)+d(q_1,p^{\prime })$.

For Case c), we show that $d(q_1,p^{\prime })\le (\sqrt{3}+\epsilon )r$. Note that since and , a long item was inserted between $q_1$ and $q_2$ but is not stored at time $T$. Hence, it holds that $q_2\ne {\tilde{q}}_2$. Let $\tilde{r}=d(q_2,{\tilde{q}}_2)$. By Lemma 3.3, it holds that $d(q_1,q_2)\le (1+\epsilon /3)\tilde{r}$ and $d(q_1,{\tilde{q}}_2)\le (1+\epsilon /3)\tilde{r}$ , i.e., $q_1\in B(q_2,(1+\epsilon /3)\tilde{r})\cap B({\tilde{q}}_2,(1+\epsilon /3)\tilde{r})$. We assume that $d({\tilde{q}}_2,p^{\prime })\le d(q_2,p^{\prime })$ as the other case follows analogously. To prove $d(q_1,p^{\prime })\le (\sqrt{3}+\epsilon )r$, we distinguish between three cases (see Figure 3).

1. i)

   If $d(q_2,p^{\prime })\le \tilde{r}$, then it follows that $d({\tilde{q}}_2,p^{\prime })\le d(q_2,p^{\prime })\le \tilde{r}$. Hence, we have $p^{\prime }\in B(q_2,\tilde{r})\cap B({\tilde{q}}_2,\tilde{r})$. By Lemma 3.4 it holds that $d(q_1,p^{\prime })\le (\sqrt{3}+\epsilon /\sqrt{3})\tilde{r}\le (\sqrt{3}+\epsilon /\sqrt{3})r$.

Otherwise, define $c$ to be the point on $\overline{q_2{p}^{\prime }}$ with $d(c,q_2)=\tilde{r}$.

1. ii)

   If $d(c,{\tilde{q}}_2)\le \tilde{r}$, then $d(q_1,c)\le (\sqrt{3}+\epsilon /\sqrt{3})\tilde{r}$ by Lemma 3.4. Hence,

   	$d(q_1,p^{\prime })$	$\le d(q_1,c)+d(c,p^{\prime })=d(q_1,c)+d(q_2,p^{\prime })-d(q_2,c)$
   		$\le (\sqrt{3}+\epsilon /\sqrt{3})\tilde{r}+r-\tilde{r}\le (\sqrt{3}+\epsilon /\sqrt{3})r.$

2. iii)

   Otherwise, it holds that $d(c,{\tilde{q}}_2)>\tilde{r}$. Then, consider the plane containing $q_2$, ${\tilde{q}}_2$ and $p^{\prime }$. Let $s$ be the point in this plane with $d(q_2,s)=d({\tilde{q}}_2,s)=\tilde{r}$ that is closest to $p^{\prime }$ (see Figure 4). Then, $d(q_1,s)\le (\sqrt{3}+\epsilon /\sqrt{3})\tilde{r}$ by Lemma 3.4. We use Lemma 3.5 to obtain a bound on $d(s,p^{\prime })$. Let $\alpha$ be the angle at $s$ in the triangle spanned by the points $q_2$, $p^{\prime }$, and $s$. Further, let $L$ denote the perpendicular bisector of $\overline{q_2{\tilde{q}}_2}$ and let $\beta$ be the smaller angle between the line $L$ and the line containing $q_2$ and $s$ denoted by $K$. We have $\beta =\pi /6$ because the triangle spanned by $q_2$, ${\tilde{q}}_2$ and $s$ is equilateral with angle $2\beta$. Because $d(c,{\tilde{q}}_2)>\tilde{r}=d(c,q_2)$, it follows that $c$ and $q_2$ lie on the same side of $L$, which implies that $p^{\prime }$ lies on the same side of the line $K$ as $c$. On the other hand, $p^{\prime }$ lies on the same side of $L$ as ${\tilde{q}}_2$ because $d({\tilde{q}}_2,p^{\prime })\le d(q_2,p^{\prime })$. Hence, $p^{\prime }$ lies in the sector spanned by $K$ and $L$ at $s$ away from $q_2$ (colored in purple in Figure 4). Therefore, it follows that $\alpha \ge \pi -\beta =(5/6)\pi$. Hence, by Lemma 3.5 we have $d(s,p^{\prime })\le \sqrt{3}d(c,p^{\prime })$ and thus

   $$d(q_1,p^{\prime })\le d(q_1,s)+d(s,p^{\prime })\le (\sqrt{3}+\epsilon /\sqrt{3})\tilde{r}+\sqrt{3}d(c,p^{\prime })\le (\sqrt{3}+\epsilon /\sqrt{3})r.$$

Therefore, in Case c) it holds that $d(p,p^{\prime })\le d(p,q_1)+d(q_1,p^{\prime })\le (1+\sqrt{3}+\epsilon )r$. $◀$

Again, the same algorithm can be used to approximate the minimum enclosing ball in Euclidean space ${ℝ}^d$.

The algorithm maintains the following invariants at all times.

1. (1)

   For all $i\in [K]$, it holds that $e_i=0$ if $A_i\cup R_i\cup O_i=\mathrm{\varnothing }$, and $e_i=\max \{E(p)\mid p\in A_i\cup R_i\cup O_i\}$ otherwise.

2. (2)

   It holds that $e_1\ge e_2\ge \mathrm{\cdots }\ge e_K$.

3. (3)

   For all $a\in {\bigcup }_{i\in [K]}{A}_i$, it holds that $d(a,R(a))\le 2\gamma$.

4. (4)

   For all distinct $a,a^{\prime }\in {\bigcup }_{i\in [K]}{A}_i$, it holds that $d(a,a^{\prime })>2\gamma$.

5. (5)

   For all distinct $q_i\in R_i\cup O_i$ and $q_j\in R_j\cup O_j$ with $i\le j$ and $E(q_i)\ge E(q_j)$, it holds that $d(q_i,q_j)>2\gamma$.

The data structures are initialized as follows.

• $\mathrm{■}$

  $A_i,R_i,O_i\leftarrow \mathrm{\varnothing }$ for all $i\in [K]$,

• $\mathrm{■}$

  $e_i,t_i\leftarrow 0$ for all $i\in [K]$, and

• $\mathrm{■}$

  $\widehat{t}\leftarrow 0$.

When a point $p$ is added to the stream, Algorithm 3 is called. We iterate over the different substreams with index $i=1$ to $K$ until we find a substream to which $p$ can be added. If a point $q=R(a)$ in $R_i\cup O_i$ exists that expires later than $p$ or at the same time as $p$ and has distance at most $2\gamma$ to $p$, then $p$ is added to substream with index $i$ and $p$ is covered by $q$. Note that as $p$ expires not later than $q$, we do not have to update $R(a)$ and we do not store $p$. Further, if an attraction point $a\in A_i$ exists with $d(a,p)\le 2\gamma$, we add $p$ to substream $i$ and $p$ gets covered by $a$ and check whether we have to update the representative point $R(a)$. To maintain Invariant 5 when the representative point $R(a)$ is updated, we run DiscardCoveredPoints.