Dynamic Streaming Algorithms for Geometric Independent Set

We answer this question in the affirmative by presenting the first space-efficient, fully dynamic streaming $O(1)$-approximation algorithm for MIS for rectangles in the plane. Specifically, our algorithm computes an $O({(1/\delta )}^2)$-approximation of the optimal size with $O(U^{\delta }\mathrm{polylog}n)$ space and update time w.h.p.,³³3 With high probability, i.e., probability $1-O(1/n^c)$ for an arbitrarily large constant $c$. where coordinates are in ${[U]}^2$. In particular, for polynomially bounded universe size $U=n^{O(1)}$, the space and update time is $O(n^{\delta })$ (after adjusting $\delta$ by a constant factor).

We also obtain a similar result for (unweighted and weighted) fat objects in any constant dimension $d$; in particular, this is new even for arbitrary-radii disks in the plane. Here, our algorithm computes an $O({(1/\delta )}^2)$-approximation of the optimal size with $O(U^{\delta }\mathrm{polylog}n)$ space and update time w.h.p., assuming that the objects are contained in ${[0,U)}^d$ and have diameter $\mathrm{\Omega }(1)$ (and weights are in $[U]$).

Our algorithms are based on Bhore and Chan’s recent dynamic algorithms in the non-streaming setting [8]. Although most dynamic data structures do not adapt well to the streaming model and inherently require linear space or worse, we show that Bhore and Chan’s approach does, luckily! Their approach for MIS for rectangles can be viewed as a combination of the old divide-and-conquer method [2] with Mitchell’s constant-approximation DP-based algorithm [39]. More precisely, they used a $b$-way divide-and-conquer to reduce the problem to special subproblems in which the input rectangles are stabbable by $O(b)$ horizontal and vertical lines. The approximation ratio increases by an $O({({\log }_{b}n)}^2)$ factor, which is constant if we choose $b=n^{\delta }$. They observed that for these special subproblems, one can round the input to reduce the input size to $b^{O(1)}$, while increasing the approximation ratio by at most a constant; when the input size is this small, one can afford to run Mitchell’s polynomial-time approximation algorithm as a black box.

It turns out that the rounding trick is a perfect fit for dynamic streaming. The divide-and-conquer part, however, requires rethinking. We provide a new interpretation of the divide-and-conquer, by directly assigning input rectangles to levels of the recursion (this is possible due to the bounded integer universe assumption, with $U^{\delta }$ factors instead of $n^{\delta }$); this simpler interpretation actually helps understand Bhore and Chan’s algorithm better. To achieve sublinear space, we cannot afford to solve all subproblems across a level. Rather, we estimate the answer by taking a small random sample of the subproblems (the idea of using random sampling to approximate a sum appeared already in one version of Bhore and Chan’s static algorithm [8], but not dynamic). In the dynamic setting, the right sampling rate is not known ahead of time. Our idea is to try all sampling rates (powers of 2) simultaneously. However, for sampling rates that are too large, the space usage would be too large. We resolve this issue by hashing to a small universe. This ensures that space is kept small for all sampling rates, and at the same time, for the right sampling rate, collision is likely avoided. We remark that sampling and hashing are both commonly used in the streaming literature, but we will keep our presentation largely self-contained, to make it accessible to computational geometers without prior background on streaming.

MIS for fat objects can be solved in a similar way, using shifted quadtrees for the divide-and-conquer part.

Let $h:[M]\to [q]$ be a random function chosen from a pairwise independent hash family, for $q=4{\tau }^2$; by standard constructions (e.g. [40, Theorem 8.16]), $h$ can be represented using $O(\log m)$ space.

Our streaming algorithm is simple: for each $a\in [q]$, we use the given algorithm $𝒜$ to maintain $f(Y_a)$ for the set

i.e., when we insert/delete an object in $S_j$, we compute $a=h(j)$ and then insert/delete that object in $Y_a$ using algorithm $𝒜$. Finally, let

and when , we output

For correctness, we discuss the two cases. Suppose . We claim that $\widehat{T}=\tilde{T}$ (and trivially) with probability at least $3/4$. To see this, observe that $\widehat{T}=\tilde{T}$ when there are no colliding pairs, i.e., no pairs $(i,j)$ with $i\ne j$, $S_i,S_j\ne \mathrm{\varnothing }$, and $h(i)=h(j)$. The expected number of colliding pairs is at most . By Markov’s inequality, the probability that there is a colliding pair is less than $1/4$.

Conversely, suppose $|\{i\in [M]:S_i\ne \mathrm{\varnothing }\}|\ge \tau$. We claim that $y\ge \tau$ with probability at least $3/4$. To see this, pick $\tau$ nonempty subsets $S_i$. By the same argument as above, with probability at least $3/4$, there are no colliding pairs among these $\tau$ nonempty subsets $S_i$, implying $y\ge \tau$.

The error probability is bounded by a constant, but can be lowered by running logarithmically many independent copies of the algorithm and taking the majority of the answers. $◀$

Note that alternatively, the above condition can be tested by directly applying known techniques for sampling elements (an “${\mathrm{\ell }}_0$-sampler”) in a turnstile stream [28, 36] (viewing an insertion/deletion in $S_i$ as incrementing/decrementing the multiplicity of $i\in [M]$). The proof above may be viewed as an adaptation or extension of such techniques.

We now reduce the general case to the special case by random sampling, using logarithmically many random subsets with different sampling rates. Chebyshev’s inequality shows that the sum of a random subset approximates the overall sum, assuming pairwise independence.

Let $X={\sum }_{i\in R}{a}_i={\sum }_{i=1}^m{a}_i\cdot [i\in R]$, where $[\cdot ]$ denotes the Iverson bracket. Then $𝔼[X]=\rho T$, and by pairwise independence, $Var[X]={\sum }_{i=1}^m{a}_i^2\rho \le B{\sum }_{i=1}{a}_i\rho =B\rho T$. By Chebyshev’s inequality, $\mathrm{Pr}[|X-𝔼[X]|\ge \epsilon 𝔼[X]]\le Var[X]/({\epsilon }^2𝔼{[X]}^2)\le B/({\epsilon }^2\rho T)\le B/({\epsilon }^2\rho m)\le 1/c$. $◀$

For each $\rho =1/2,1/4,\mathrm{\dots },1/2^{\lceil \log M\rceil }$, let $R_{\rho }$ be a random subset of $[M]$ with sampling rate $\rho$, where the events “$i\in R_{\rho }$” are pairwise independent. By standard constructions (e.g. [40, Theorem 8.16]), such a subset can be represented using $O(\log m)$ space (so that we can tell if a given index $i$ is in $R_{\rho }$ in $O(1)$ time).

We will apply the algorithm in Lemma 2 to try to maintain

with $\tau =cB/{\epsilon }^2$ for a sufficiently large constant $c$. Pick the largest ${\rho }^{\ast }$ for which (recall that this condition can be tested w.h.p. by Lemma 2). Then the algorithm from Lemma 2 will succeed in computing ${\tilde{T}}_{{\rho }^{\ast }}$ w.h.p. and we return $(1/{\rho }^{\ast }){\tilde{T}}_{{\rho }^{\ast }}$.

For the analysis, let $m=|\{i\in [M]:S_i\ne \mathrm{\varnothing }\}|$. Let ${\rho }_0$ be a power of 2 with . Then by Chebyshev’s inequality,

On the other hand, for each $\rho \ge 8{\rho }_0$, by Chebyshev’s inequality,

By a geometric series over all $\rho \ge 8{\rho }_0$, $\mathrm{Pr}[{\rho }^{\ast }\ge 8{\rho }_0]\le O(1/({\rho }_{0}m))$. Thus, with probability $1-O(1/c)$, ${\rho }^{\ast }$ must be a value among $\{{\rho }_0,2{\rho }_0,4{\rho }_0\}$. For each such value $\rho$, the probability that ${\rho }^{\ast }=\rho$ but $(1/\rho ){\tilde{T}}_{\rho }$ is not a $(1\pm \epsilon )$-approximation of $T$ is at most $O(1/c)$, by applying Lemma 3 to the sum $T={\sum }_{i\in [M]:S_i\ne \mathrm{\varnothing }}f(S_i)$, which has $m$ nonempty terms.

The error probability is bounded by a constant, but can again be lowered by running logarithmically many independent copies of the algorithm and taking the majority of the answers. (For simplicity, we have not attempted to optimize the ${(B/\epsilon )}^{O(1)}{\log }^{O(1)}(nM)$ factors.) $◀$

The lines in $\mathrm{\Gamma }$ form a (non-uniform) grid with $O(b^2)$ grid cells. (See Figure 1.) Place two rectangles of $S$ in the same class if they intersect the same subset of grid cells. There are $O(b^4)$ classes. Let $\widehat{S}$ be a subset of $S$ where we keep one “representative” element from each class. Then $|\widehat{S}|=O(b^4)$. We apply Mitchell’s algorithm [39] (or its subsequent improvement [31, 30]) to compute an $O(1)$-approximation of the maximum independent set for the rectangles in $\widehat{S}$. This takes time polynomial in $|\widehat{S}|$, i.e., $b^{O(1)}$ time (note that the optimal size must be at most $b^2$ under the input assumption). Bhore and Chan [8] proved that this is an $O(1)$-approximation of the maximum independent set for $S$.

To implement the algorithm in the dynamic streaming model, it suffices to maintain one representative element per class, since we can re-run Mitchell’s algorithm from scratch. Frahling, Indyk, and Sohler [28] (see also [36]) showed how to maintain a random element of a set in the dynamic streaming model; we can just apply their algorithm to each class and use the random element as the representative. $◀$

We now solve the main problem by reinterpreting the divide-and-conquer approach by Bhore and Chan [8] and incorporating Theorem 1.

Write each coordinate value in base $b$; the number of digits in each value is $\lceil {\log }_{b}U\rceil$.

Consider a rectangle $s=[x,x^{\prime }]\times [y,y^{\prime }]$ in $S$. Suppose that the most significant digit which $x$ and $x^{\prime }$ differ in is the $k$-th most significant digit, and the most significant digit which $y$ and $y^{\prime }$ differ in is the $\mathrm{\ell }$-th most significant digit. Let $\xi$ be the $k-1$ most significant digits of $x$ and $x^{\prime }$. Let $\eta$ be the $\mathrm{\ell }-1$ most significant digits of $y$ and $y^{\prime }$. We place $s$ in a set $S_{\xi ,\eta }$; in turn, we place the set $S_{\xi ,\eta }$ in a collection ${𝒮}_{k,\mathrm{\ell }}$.⁴⁴4 Roughly, Bhore and Chan’s recursion [8] generates a primary tree (essentially a $b$-ary interval tree in $x$), where each node stores a secondary tree (a $b$-ary interval tree in $y$). Each set $S_{\xi ,\eta }$ corresponds to a node of a secondary tree. Each collection ${𝒮}_{k,\mathrm{\ell }}$ corresponds to a “level” of the whole structure (namely, the $\mathrm{\ell }$-th level of all nodes at the $k$-th level of the primary tree). (See Figure 2.)

For each $k,\mathrm{\ell }\in [\lceil {\log }_{b}U\rceil ]$, we maintain an $O(1)$-approximation of

using Theorem 1. Here, $f_{k,\mathrm{\ell }}(S)$ is defined as the maximum independent set size for $S^{\mathrm{\#}}=\{s^{\mathrm{\#}}:s\in S\}$, where $s^{\mathrm{\#}}$ denotes the rectangle obtained from $s=[x,x^{\prime }]\times [y,y^{\prime }]$ by removing the $k-1$ most significant digits from $x$ and $x^{\prime }$ and the $\mathrm{\ell }-1$ most significant digits from $y$ and $y^{\prime }$, assuming that $x$ and $x^{\prime }$ differ in the $k$-th most significant digit and $y$ and $y^{\prime }$ differ in the $\mathrm{\ell }$-th most significant digit (if the assumption is not satisfied, make $s^{\mathrm{\#}}$ undefined). Note that for an individual set $S_{\xi ,\eta }\in {𝒮}_{k,\mathrm{\ell }}$, $f(S_{\xi ,\eta })$ is the same as the maximum independent set size for $S_{\xi ,\eta }$ (although this may not be true for a general set $S$). Also note that every rectangle $s^{\mathrm{\#}}$ is stabbed by one of the $b$ vertical lines at $x=b^{\lceil {\log }_{b}U\rceil -k}i$ for some $i\in [b]$, and one of the $b$ horizontal lines at $y=b^{\lceil {\log }_{b}U\rceil -\mathrm{\ell }}j$ for some $j\in [b]$, and so we can maintain $f_{k,\mathrm{\ell }}(S)$ using Lemma 4 (note that $f_{k,\mathrm{\ell }}(S)\le b^2$). The conditions of Theorem 1 are fulfilled with $B=b^2$ and $s(n),t(n)=O(b^{O(1)}{\log }^{O(1)}n)$. We return the maximum of the approximations of $T_{k,\mathrm{\ell }}$ over all $k,\mathrm{\ell }\in [\lceil {\log }_{b}U\rceil ]$.

Observe that $T_{k,\mathrm{\ell }}$ is just the maximum independent set size for ${\bigcup }_{S_{\xi ,\eta }\in {𝒮}_{k,\mathrm{\ell }}}{S}_{\xi ,\eta }$, because rectangles in $S_{{\xi }_1,{\eta }_1}$ do not overlap with rectangles in $S_{{\xi }_2,{\eta }_2}$ for any two different sets $S_{{\xi }_1,{\eta }_1},S_{{\xi }_2,{\eta }_2}\in {𝒮}_{k,\mathrm{\ell }}$. Thus, $\mathrm{OPT}$ (the maximum independent set size for $S$) is at most ${\sum }_{k,\mathrm{\ell }}{T}_{k,\mathrm{\ell }}\le O{({\log }_{b}U)}^2\cdot {\max }_{k,\mathrm{\ell }}{T}_{k,\mathrm{\ell }}$. It follows that the returned value is an $O({({\log }_{b}U)}^2)$-approximation of $\mathrm{OPT}$. Finally, we set $b=U^{\delta }$. $◀$

Although the preceding proof is compact, the details are subtle. For example, some readers may wonder why we didn’t define $f_{k,\mathrm{\ell }}(S)$ more simply as the maximum independent set size for $S$, bypassing the definition of $s^{\mathrm{\#}}$. The reason is that Theorem 1 requires working with $f_{k,\mathrm{\ell }}(S)$ for general sets $S$, not just the $S_{\xi ,\eta }$’s: indeed, the proof of Lemma 2 maintains intermediate sets that are unions of $S_{\xi ,\eta }$’s (from a common bucket); without replacing $s$ with $s^{\mathrm{\#}}$, the rectangles in such composite sets may not be stabbable by $b$ vertical/horizontal lines. Admittedly, defining $f_{k,\mathrm{\ell }}(S)$ as the maximum independent set for $S^{\mathrm{\#}}$ is somewhat counterintuitive, as its value seems irrelevant or meaningless when $S$ is a union of two or more sets $S_{\xi ,\eta }$’s. (To picture such a set $S^{\mathrm{\#}}$, imagine overlaying the two violet cells in Figure 2 on top of each other.) However, under the “right” circumstances, when we don’t have collisions, as in the proof of Lemma 2, $S$ would revert to a single $S_{\xi ,\eta }$, and $f_{k,\mathrm{\ell }}(S)$ would become meaningful again.

First round the weights to powers of 2; the approximation ratio increases by at most a factor of 2.

Place two objects of $S$ in the same class if they intersect the same subset of cells in $\mathrm{\Gamma }$. There are at most $b^{O(1)}$ classes (as noted in [8]). Let $\widehat{S}$ be a subset of $S$ where we keep one “representative” element from each class, namely, a largest-weight element from the class. Then $|\widehat{S}|\le b^{O(1)}$. We apply a known algorithm (e.g., [16]) to compute an $O(1)$-approximation to the maximum-weight independent set for the fat objects in $\widehat{S}$. This takes time polynomial in $|\widehat{S}|$, i.e., $b^{O(1)}$ time. Bhore and Chan [8] proved that this is an $O(1)$-approximation of the maximum independent set for $S$ (using the goodness assumption).

To implement the algorithm in the dynamic streaming model, it suffices to maintain a representative element per class. Frahling, Indyk, and Sohler [28] (see also [36]) showed how to maintain a random element of a set in the dynamic streaming model; we can just apply their algorithm to each class restricted to elements of each weight, and use the random element as the representative for the largest weight whose set is nonempty. There are only $O(\log U)$ possible weights. $◀$

We now solve the main problem, via quadtree-based divide-and-conquer, as in [8],⁵⁵5Bhore and Chan [8] needed a balanced version of quadtrees (requiring cells that are differences of two quadtree boxes), but we are able to simplify the divide-and-conquer because of the bounded universe assumption. but in combination with Theorem 1.

We assume that all objects of $S$ are $O(d)$-good. This is without loss of generality by the shifting lemma (Fact 7): for each of the $d+1$ shifts $v_j(j\in \{0,\mathrm{\dots },d\})$, we can solve the problem for the good objects of $S+v_j$ in parallel, and return the maximum of the answers. The approximation ratio increases by a factor of $d+1=O(1)$.

Furthermore, we assume that all objects have weights in a common interval $[b^k,b^{k+1})$. This is without loss of generality, if we increase the approximation ratio by an extra factor of $O({\log }_{b}U)$ (since there are $O({\log }_{b}U)$ choices for $k$). By rescaling, we may now assume that all objects have weights in $[1,b)$.

Consider an object $s\in S$. Let $\gamma$ be the smallest quadtree box containing $s$ such that $\text{diam}(\gamma )$ is a power of $b$ (the parameter $b$ will be a power of 2). Suppose that $\text{diam}(\gamma )=b^{\mathrm{\ell }}$. We place $s$ in a set $S_{\gamma }$; in turn, we place the set $S_{\gamma }$ in a collection ${𝒮}_{\mathrm{\ell }}$.⁶⁶6 Each $S_{\gamma }$ corresponds to a node in the $b$-ary variant of the quadtree. Each ${𝒮}_{\mathrm{\ell }}$ corresponds to one level of the quadtree.

For each $\mathrm{\ell }\in [{\log }_{b}U]$, we maintain an $O(1)$-approximation of $T_{\mathrm{\ell }}={\sum }_{S_{\gamma }\in {𝒮}_{\mathrm{\ell }}}{f}_{\mathrm{\ell }}(S_{\gamma })$ using Theorem 1. Here, $f_{\mathrm{\ell }}(S)$ is defined as the maximum independent set weight for $S^{\mathrm{\#}}=\{s^{\mathrm{\#}}:s\in S\}$, where $s^{\mathrm{\#}}$ denotes the object $s$ shifted by $-p_{\gamma }$, where $\gamma$ is the quadtree box containing $s$ with $\text{diam}(\gamma )=b^{\mathrm{\ell }}$, and $p_{\gamma }$ is the lexicograpically smallest vertex of $\gamma$, assuming that $s$ is not contained in any quadtree box with diameter $b^{\mathrm{\ell }-1}$ (if the assumption is not satisfied, make $s^{\mathrm{\#}}$ undefined). Note that for an individual set $S_{\gamma }\in {𝒮}_{\mathrm{\ell }}$, $f(S_{\gamma })$ is the same as the maximum independent set weight for $S_{\mathrm{\ell }}$. Also note that every object $s^{\mathrm{\#}}$ intersects the boundary of one of the $b^d$ quadtree boxes of diameter $b^{\mathrm{\ell }-1}$ contained in ${[0,b^{\mathrm{\ell }})}^d$, and so we can maintain $f_{\mathrm{\ell }}(S)$ using Lemma 4 after replacing $b$ with $b^d$ (note that $f_{\mathrm{\ell }}(S)\le b^{O(1)}$, since all objects have weights in $[1,b)$). The conditions of Theorem 1 are fulfilled with $B=b^{O(1)}$ and $s(n),t(n)=O(b^{O(1)}{\log }^{O(1)}(nU))$. We return the maximum of the approximations of $T_{\mathrm{\ell }}$ over all $\mathrm{\ell }\in [{\log }_{b}U]$.

Observe that $T_{\mathrm{\ell }}$ is just the maximum independent set weight for ${\bigcup }_{S_{\gamma }\in {𝒮}_{\mathrm{\ell }}}{S}_{\gamma }$, because rectangles in $S_{{\gamma }_1}$ do not overlap with rectangles in $S_{{\gamma }_2}$ for any two different sets $S_{{\gamma }_1},S_{{\gamma }_2}\in {𝒮}_{\mathrm{\ell }}$. Thus, $\mathrm{OPT}$ (the maximum independent set weight for $S$) is at most ${\sum }_{\mathrm{\ell }}{T}_{\mathrm{\ell }}\le O({\log }_{b}U)\cdot {\max }_{\mathrm{\ell }}{T}_{\mathrm{\ell }}$. It follows that the returned value is an $O({\log }_{b}U)$-approximation of $\mathrm{OPT}$, under the assumption that objects have weights in $[1,b)$. We thus obtain approximation ratio $O({({\log }_{b}U)}^2)$ for the general problem. Finally, we set $b=U^{\delta }$. $◀$