Dynamic and Streaming Algorithms for Union Volume Estimation

We answer our driving question (Q1) positively, not only for 2D triangles, 3D simplices, and other common types of objects encountered in computational geometry, but in the full generality of the oracle model. Our new dynamic algorithm can handle arbitrary sequences of both insertions and deletions.

More precisely, we consider an initially empty multiset of objects $𝒳$ under the updates insert($X$), which adds object $X$ to $𝒳$, and delete($X$), which removes object $X$ from $𝒳$. Upon query estimate(), the algorithm outputs a $(1\pm \epsilon )$-approximation to the volume $\mathrm{vo}\mathrm{\ell }\left({\bigcup }_{X\in 𝒳}X\right)$.

During insertion/deletion the algorithm is given oracle access to the inserted/deleted object. We also need the ability to store objects (or their oracles), in case of future lookup of the previously inserted objects. We make the natural assumption that (i) the argument of insert($X$) and delete($X$) is a pointer to the oracle of $X$, (ii) we can store a pointer in a machine word, and (iii) knowing the pointer allows us to access the oracle to which the pointer is pointing. In this interpretation, $𝒳$ is treated as a multiset of pointers: the same pointer can be inserted multiple times, and upon deletion, the multiplicity of the pointer is decreased by one. Naturally, the multiplicity of any pointer must be non-negative throughout the process (in particular, objects being deleted must have previously been inserted).

Note that since the algorithm operates in the general oracle model, it works well even for high-dimensional objects (e.g., for simplices in ${ℝ}^d$, with polynomial dependence on $d$).

In our remaining results, we turn to streaming algorithms and our driving question (Q2) and show that polylogarithmic time and space can be achieved in certain settings. We first consider the sliding window setting [22], which supports insertions of objects and querying over the last $w$ objects for a fixed window size $w$; thus, objects are deleted in the same order as they are inserted. Numerous results and techniques have been developed in the sliding window setting (see [41, 3, 8] for an overview and [48, 30, 25] for recent work), but no such result was known for union volume estimation.

We obtain the first efficient sliding-window algorithm for union volume estimation. Again, it works in the general oracle model! Moreover, the result holds in an extension of the sliding-window setting, where at each time $t=1,\mathrm{\dots },n$ an object $X_t$ is inserted (but cannot be deleted), and a query estimate($s$) may return a $(1\pm \epsilon )$-approximation to the volume of the suffix $\mathrm{vo}\mathrm{\ell }(X_s\cup \mathrm{\cdots }\cup X_t)$ with high probability for any number $s$ the user specifies.

Our algorithm not only generalizes previous insertion-only results [40], but is also remarkably simple. Note that the space bound depends on the aspect ratio $M$, defined as the ratio of the largest volume of any object ever inserted and the smallest volume of any object ever inserted. In many applications, $M$ is a polynomial in $n$ and thus $\log (M)=O(\log n)$. Furthermore, geometric algorithms in the sliding window setting [24, 20] usually have logarithmic dependencies on parameters such as the aspect ratio or spread.

Lastly, we consider streaming algorithms that support both insertions and deletions. We manage to develop an efficient algorithm for a reasonably wide class of geometric objects – namely, convex bodies in any constant dimension:

The bounds depend polylogarithmically on $R/r$, which is common in volume estimation algorithms for a single convex object [23] as well as geometric streaming algorithms [29, 26].

Previously, Tirthapura and Woodruff obtained an efficient dynamic streaming algorithm only for axis-aligned boxes [47] (with $\mathrm{po}\mathrm{\ell }\mathrm{y}(\log n,\log \mathrm{\Delta },\frac{1}{\epsilon },d)$ update time and space in a discrete universe ${\{1,\mathrm{\dots },\mathrm{\Delta }\}}^d$). To emphasize the generality of our algorithm, note that many non-convex objects can be decomposed into a small number of convex objects, e.g., non-convex polyhedra of constant combinatorial complexity in constant dimensions can be decomposed into a constant number of simplices, to which our algorithm can be applied.

Karp, Luby and Madras’ algorithm [34] and subsequent work are based on the observation that we can estimate the volume of a union $U$ by maintaining a finite random subset $S^{(\mathrm{\ell })}\subset U$ that selects every point independently with probability density $1/2^{\mathrm{\ell }}$. It turns out that the “right” choice of $\mathrm{\ell }$ is one such that $|S^{(\mathrm{\ell })}|\approx \log (n)/{\epsilon }^2$; in this case $2^{\mathrm{\ell }}|S^{(\mathrm{\ell })}|$ provides a good estimate of the volume of $U$.

Meel, Vinodchandran, and Chakraborty [40] described a particularly simple way to maintain such a random set $S^{(\mathrm{\ell })}$ for insertion-only updates: when a new object $X$ is inserted, we remove from $S^{(\mathrm{\ell })}$ all points that are contained in $X$, then add to $S^{(\mathrm{\ell })}$ freshly sampled points in $X$ with density $1/2^{\mathrm{\ell }}$. This step is inexpensive for the right choice of $\mathrm{\ell }$ since $|S^{(\mathrm{\ell })}|$ is logarithmic. If $|S^{(\mathrm{\ell })}|$ becomes too big, we increment $\mathrm{\ell }$ (thereby halving the sampling rate and also $|S^{(\mathrm{\ell })}|$ in expectation) and move on.

Difficulty arises in the presence of deletions: the volume is no longer monotonically increasing, and the right choice of $\mathrm{\ell }$ may increase or decrease over time. Our first observation is that the deletion-only case can be handled by a variant of Meel, Vinodchandran, and Chakraborty’s insertion-only algorithm. Roughly, we can maintain $S^{(\mathrm{\ell })}$ for the right $\mathrm{\ell }$ by keeping a counter on the number of objects containing each sample point (recall that $|S^{(\mathrm{\ell })}|$ is logarithmic for the right $\mathrm{\ell }$). When an object $X$ is deleted, we decrement the counters of all points in $S^{(\mathrm{\ell })}\cap X$, and when a counter drops to 0, the point is removed from $S^{(\mathrm{\ell })}$. When the number of surviving sample points drops below logarithmic, we decrease $\mathrm{\ell }$, rebuild $S^{(\mathrm{\ell })}$ by iterating over all objects that has not been deleted (recall that we can store pointers to all objects), and reinitialize the counters.

A popular technique in dynamic computational geometry by Bentley and Saxe [4], called the logarithmic method, transforms deletion-only data structures into fully dynamic ones. It works by decomposing a fully dynamic set into logarithmically many deletion-only subsets, increasing the update and query time by typically just a logarithmic factor. The logarithmic method applies to so-called decomposable problems that satisfy the following property: if the input is decomposed into subsets, then the answer to the original problem can be quickly obtained from the answers to the individual subsets. Unfortunately, union volume estimation is not a decomposable problem: We cannot determine the volume of the union of ${𝒳}_0\cup \mathrm{\cdots }\cup {𝒳}_{\log n}$ just from the volume of the union of each ${𝒳}_i$.

Nevertheless, we show that a novel variant of the logarithmic method can still work. Recall that the deletion-only data structure already maintains a sample for each ${𝒳}_i$. For each sample point we keep track of more counters – specifically, how many sets from the other ${𝒳}_i$’s contain the point. These counters provide enough information to avoid double counting and help us estimate the union volume accurately. One issue though is that many counters need to be adjusted when one of the deletion-only data structures changes $\mathrm{\ell }$ and recomputes $S^{(\mathrm{\ell })}$. Fortunately, we manage to bound the total number of such changes, so the amortized cost for maintaining all counters remains polylogarithmic. See Section 5 for details.

The dynamic algorithm with arbitrary insertions and deletions needs linear space because the data structure rebuilds on the remaining objects when the “right” $\mathrm{\ell }$ decreases. However, in the sliding window setting and more generally the setting of suffix queries, the remaining objects are contiguous in time and need not be stored explicitly. We obtain a streaming algorithm in this case by a simple yet non-trivial generalization of Meel, Vinodchandran, and Chakraborty’s algorithm. Specifically, we keep the timestamp when each point in $S^{(\mathrm{\ell })}$ is sampled. For each $\mathrm{\ell }$ we keep track of the largest timestamp $s^{(\mathrm{\ell })}$ such that discarding points older than $s^{(\mathrm{\ell })}$ from $S^{(\mathrm{\ell })}$ makes $|S^{(\mathrm{\ell })}|$ logarithmically bounded. This timestamp $s^{(\mathrm{\ell })}$ is monotonically increasing over time for each fixed $\mathrm{\ell }$. To estimate the volume of the union of $X_s\cup \mathrm{\cdots }\cup X_t$ for a given $s$ at time $t$, we identify the smallest $\mathrm{\ell }$ for which $s^{(\mathrm{\ell })}\le s$, and output $2^{\mathrm{\ell }}|S^{(\mathrm{\ell })}\cap (X_s\cup \mathrm{\dots }\cup X_t)|$. See Section 6 in the full version [5] for details.

Our streaming algorithm for low-dimensional convex objects for arbitrary insertions and deletions is based on another simple sampling strategy. First, it is not difficult to discretize the space ${ℝ}^d$ to a grid ${[\mathrm{\Delta }]}^d$ for some large $\mathrm{\Delta }$, so that the volume of the union $U$ is close to the number of grid points in $U\cap {[\mathrm{\Delta }]}^d$. The idea now is to select a random subset $R^{(\mathrm{\ell })}$ of the grid ${[\mathrm{\Delta }]}^d$ in the beginning, and maintain the intersection $S^{(\mathrm{\ell })}:=U\cap R^{(\mathrm{\ell })}$ during the updates. Using a pairwise independent family of hash functions, $R^{(\mathrm{\ell })}$ can be represented implicitly with logarithmically many bits.

When we insert or delete an object $X$, we just need to insert or delete $X\cap R^{(\mathrm{\ell })}$ to or from $S^{(\mathrm{\ell })}$ (viewed as a multiset of points). An issue is that the space usage may be large for a $S^{(\mathrm{\ell })}$ with a “wrong” sampling rate, and we do not know which $\mathrm{\ell }$ is the right choice beforehand. Furthermore, a wrong choice may become right at a later time. This issue can be resolved by representing $S^{(\mathrm{\ell })}$ by data structures for sparse vectors [26, 31], which support adding numbers to a given coordinate, as well as recovering the vector when its norm is below a threshold. In this way, we essentially just pay for the space at the right sampling rate.

A question remains: how to enumerate the points of $X\cap R^{(\mathrm{\ell })}$ for a given object $X$ and for our implicitly represented set $R^{(\mathrm{\ell })}$? For the case where the objects are rotated (non-axis-aligned) boxes in constant dimension, and for a particular pairwise independent family of hash functions, we observe that this subproblem directly reduces to integer linear programming (ILP) with a constant number of constraints and variables, and therefore can be solved efficiently by well-known algorithms [38]. For more general convex objects in constant dimension, we bound each object $X$ by a small rotated box $B\supseteq X$, use an ILP to enumerate the points of $B\cap R^{(\mathrm{\ell })}$ and discard those not in $X$. By “small” we mean that the volume of $B$ is comparable to that of $X$, so in particular the number of discarded points is small. See Section 7 in the full version [5] for details.

Our approach is related to Tirthapura and Woodruff’s algorithm [47] for axis-aligned boxes. Their idea was to directly adapt a streaming algorithm for approximately counting distinct elements to estimate $|U\cap {[\mathrm{\Delta }]}^d|$: to insert or delete an object $X$, we cannot afford to literally insert or delete all points in $|X\cap {[\mathrm{\Delta }]}^d|$, but they showed how to efficiently simulate the effect for a specific distinct elements algorithm in the case of axis-aligned boxes. Our approach is more modular in that we apply sparse recovery only as a black box. Our main contribution however is the realization, via solving an ILP, that this type of approach works far more generally than for axis-aligned boxes, namely, for general convex objects.

We will use the Karp–Luby–Madras algorithm as a subroutine:

We need a somewhat technical notion that is “close” to an $\mathrm{\ell }$-sample at the right level $\mathrm{\ell }$.

Next we study the decremental setting. That is, we receive a set of objects $𝒳$ and want to build a data structure that allows efficient deletions. At any time, it needs to quickly report a digest of the union of the surviving objects (i.e., objects that have not been deleted).

In this section, we apply the decremental data structure from the previous section to derive a dynamic algorithm for union volume estimation, using a novel variant of the logarithmic method [4]. Throughout the algorithm, the remaining objects are partitioned into bins ${𝒳}_0,\mathrm{\dots },{𝒳}_{\log n}$. Each bin ${𝒳}_j$ holds at most $2^j$ objects and is implemented by the decremental data structure. Every now and then, we merge some (small) bins into a larger bin by re-initializing the target bin with the objects in the source bins. Between any two merges that involve a bin ${𝒳}_j$, it undergoes deletions only. At any time, we can access a digest $({𝒳}_j.L,{𝒳}_j.S)$ of the union ${\bigcup }_{X\in {𝒳}_j}X$. Additionally, for every point $x\in {𝒳}_j.S$, we keep track of the number $n_x:=\mathrm{\#}\{X\in {𝒳}_0\cup \mathrm{\cdots }\cup {𝒳}_{j-1}:x\in X\}$.