Streaming Diameter of High-Dimensional Points

In the streaming model, the input data is assumed to be vast and must be processed using limited memory in one or a few passes. Therefore, streaming algorithms “sketch” the input, yielding a small data structure that still accurately preserves desired properties. The research on streaming algorithms has been remarkably fruitful and we now have optimal or near-optimal algorithms for counting distinct elements, frequency moments, quantiles and a plethora of other problems (see [14] for a comprehensive exposition).

We focus on high-dimensional geometric streams, where the input $S$ consists of points in ${ℝ}^d$ for $d$ large, a topic of recent interest, e.g., [28, 17, 26, 15, 25, 11, 10, 12, 23]. Extent measures, such as the Diameter or the Minimum Enclosing Ball, are fundamental statistics of a set of points, having a body of work in both streaming and non-streaming settings [2, 22, 19, 3, 8, 7].

In an influential work, Agarwal and Sharathkumar [5] gave a streaming algorithmic framework for several high-dimensional extent problems. Their Blurred Ball Cover data structure maintains a collection of $𝒪(\frac{1}{{\epsilon }^2}\log (\frac{1}{\epsilon }))$ balls, whose union approximately covers the input $S$. It was then used to approximate a number of high-dimensional extent problems. The claim is that each ball is represented by a coreset of $𝒪(\frac{1}{\epsilon })$ points of $S$, for a total space of $𝒪(\frac{1}{{\epsilon }^3}\log (\frac{1}{\epsilon }))$ points. It appears though that a somewhat higher space bound is needed for the claimed approximations; see Appendix A.

We give a modified data structure, Guarded Ball Cover, building on [5]. It allows for both a simpler and more complete treatment, and also results in the smaller space bound of $𝒪(\frac{1}{{\epsilon }^2}\log (\frac{1}{\epsilon }))$ points. The improved space bound extends to all four applications: approximate Farthest Neighbor queries and for maintaining approximate Farthest Pair (providing an estimate for Diameter), Minimum Enclosing Ball, and Coreset for Minimum Enclosing Ball. This is feasible by storing only a single point per ball, along with its center and radius. Correctness arguments are simplified by also storing the first point of $S$ as a proxy for all points deleted later from memory. We retain the approximation guarantees of all four applications, as in [5]: $1.22+\epsilon$ for Minimum Enclosing Ball and $\sqrt{2}+\epsilon$ for each of Diameter, Farthest Neighbor Queries, and Coreset for Minimum Enclosing Ball.

We also show that $\mathrm{\Omega }({\epsilon }^{-1})$ points need to be stored for a comparable $(\sqrt{2}+\epsilon )$-approximation of Farthest Neighbor queries and also for maintaining $(\sqrt{2}+\epsilon )$-approximate Farthest Pair. This applies to a computational model where the algorithm must return an input point upon a query and the space is determined by the number of points stored; crucially, once a point is deleted from memory, it cannot be retrieved.

Let $S$ be a multiset of points in ${ℝ}^d$ that arrive sequentially in a stream. Upon arrival, each point $p\in S$ is either stored in memory (and, possibly, deleted later) or irrevocably discarded. We assume one-pass streaming algorithms in the insertion-only setting. By $\epsilon \in (0,1]$ we denote an error parameter and by $\alpha >1$ an approximation guarantee.

An extent measure of a set of points computes certain statistics of either this set or a geometric shape enclosing it [2]. Let $\Vert pq\Vert$ denote the Euclidean distance between points $p\in {ℝ}^d$ and $q\in {ℝ}^d$. The Diameter is the maximum Euclidean distance between any pair of points in $S$ and the Farthest Pair $\text{FP}(S)$ is a pair of points of $S$ having Euclidean distance equal to the Diameter. The Farthest Neighbor of a point $q$ is a point $p$ of the largest Euclidean distance from $q$. An $\alpha$-farthest-neighbor $\alpha$-$\text{FN}(q)$ of a query point $q\in {ℝ}^d$ is a point $x\in S$ such that for every $p\in S$ it is $\Vert qp\Vert \le \alpha \cdot \Vert xq\Vert$.

By $B(c(B),r(B))$ we denote a ball centered at point $c(B)$ with radius $r(B)$. The $(1+\epsilon )$-expansion of $B(c,r)$ is defined as $B(c,(1+\epsilon )r)$. The Minimum Enclosing Ball $\text{MEB}(S)$ is the ball of minimum radius containing all points of $S$. A ball $B$ is $\alpha$-$\text{MEB}(S)$ if $r(B)\le \alpha r(\text{MEB}(S))$ and each point of $S$ is within Euclidean distance $r(B)$ from $c(B)$.

For a set of points $S$, a coreset is a set $S^{\prime }\subseteq S$ preserving a geometric property of $S$ [21]. A set $S^{\prime }\subseteq S$ is $\alpha$-$\text{coreset}(S)$ for MEB if each point of $S$ is contained in the $\alpha$-expansion of $\text{MEB}(S^{\prime })$.

We focus on computing $(\sqrt{2}+\epsilon )$-$\text{FN}(q)$ for any query $q\in {ℝ}^d$ and maintaining $(1.22+\epsilon )$-$\text{MEB}(S)$, $(\sqrt{2}+\epsilon )$-$\text{coreset}(S)$ and $(\sqrt{2}+\epsilon )$-$\text{FP}(S)$; these ratios are the same as in [5].

The Guarded Ball Cover is a collection $ℬ$ of balls that approximately cover all points of $S$. We represent each ball of $ℬ$ by a triplet $B=(c,r,q)$, where $c$ is the center of $B$ (possibly $c\notin S$), $r$ is its radius, and $q$ is a point of $S$ inside $B$. The point $q$ is referred to as the guard of $B$. Our algorithm maintains a coreset $Q$ that consists of the guard points. We treat the first point $p_1\in S$ specially by always having $p_1\in Q$.

Let $(1+\epsilon )ℬ=\{(c,(1+\epsilon )r,q):(c,r,q)\in ℬ\}$ be the collection of the $(1+\epsilon )$-expansions of the balls in $ℬ$. If the arriving point $p\in S$ belongs to $(1+\epsilon )ℬ$, then it is discarded. Otherwise, a new ball is added to $ℬ$. Finally, all balls of too small radius are removed from $ℬ$.

As the space bound is our primary measure, we assume an exact MEB algorithm, but a good approximation also suffices, specifically within a factor of $1+{\epsilon }^2/16$ (using the algorithm of [6] as a subroutine).

The following lemma holds for every MEB computed in line 2 of Algorithm 1:

To analyze the algorithm, we first observe that deleted balls are “guarded” by $p_1$.

We show that computing a $\sqrt{2}$-approximation (with $\epsilon =0$) of Farthest Neighbor queries or Farthest Pair is impossible in the streaming model without returning points outside of $S$.

This applies to the computational model of “coreset-based algorithms” in which the space bound is counted in the number of input points stored and the algorithm must return an input point upon a query (or two input points for the Farthest Pair); crucially, once a point is deleted from memory, it cannot be retrieved. This model is akin to comparison-based model in sorting or selection, as used in [13] for streaming lower bounds for quantile estimation.

We have designed streaming algorithms storing $𝒪((1/{\epsilon }^2)\log (1/\epsilon ))$ points from ${ℝ}^d$ that can estimate several extent statistics of the input. All error guarantees are almost optimal, with the only exception of the Minimum Enclosing Ball application, where there exists a small gap between the approximation guarantee of $1.22+\epsilon$ and the lower bound converging to $(\sqrt{2}+1)/2\approx 1.207$ for $d\to \mathrm{\infty }$. This is achieved by simplifying (and also fixing) the Blurred Ball Cover from [5] into a “Guarded Ball Cover”, where we store $\mathrm{\Theta }(1)$ points per ball, compared to $\mathrm{poly}(1/\epsilon )$ points per ball for the Blurred Ball Cover.

We believe that the space bound can be improved, at least by shaving off the $\log (1/\epsilon )$ factor. One possible direction for improvement is the use of randomization as both our algorithms and those of [5] are deterministic, while the simple lower bound of $\mathrm{\Omega }(1/\epsilon )$ for “coreset-based” algorithms holds even when randomization is used.

While our algorithms are more space-efficient than that of [5], the amortized update times are somewhat worse, as discussed in Section 3. Thus, we ask if it is possible to optimize the $\mathrm{poly}(d\cdot {\epsilon }^{-1})$ amortized update time while retaining the near-quadratic space bound. More importantly, it would be interesting to develop a “fast” streaming algorithm for extent problems, that is, with amortized update time $𝒪(d\cdot \mathrm{poly}(\log {\epsilon }^{-1}))$.

Beyond the streaming setting, an important property of data sketches is mergeability [1], which enables to summarize the input in a parallel or distributed way and then merge the resulting sketches into one summary of the whole dataset. It is open how to design a merge operation for Guarded (or Blurred) Ball covers while retaining the space and approximation guarantees.