Maximizing the Optimality Streak of Deferred Data Structuring (a.k.a. Database Cracking)

We now formalize the DDS problem. Initially, an algorithm $𝒜$ is provided with the dataset $S$ in an array, where the elements are arbitrarily permuted. An adversary first chooses a predicate $q_1$ for the first query, and solicits the answer ${\text{Ans}}_{q_1}(S)$ from $𝒜$. Iteratively, for each $i\ge 2$, after the answer of the ($i-1$)-th query has been obtained, the adversary either decides to terminate the whole process, or chooses the predicate $q_i$ for the next query and solicits ${\text{Ans}}_{q_i}(S)$ from $𝒜$. The adversary is permitted to observe the execution of $𝒜$ and, thus, capable of selecting a “bad” $q_i$ for $𝒜$.

The algorithm $𝒜$ is said to guarantee running time $\text{Time}(n,r)$ for $t$ queries if, for every $r\le t$, the first $r$ queries are processed with a total cost at most $\text{Time}(n,r)$. We will concentrate on $t\le n$ because this is the scenario important for database cracking.

While the above setup is “standard” for DDS, as far as database cracking is concerned, it makes sense to carry out investigation from another fresh perspective. As database cracking is useful mainly in the scenario where the dataset receives relatively few queries, it is imperative to design DDS algorithms that are particularly efficient when the number of queries is small.

To formalize the notion of “particularly efficient”, we leverage the fact that, for many DDS problems (including the ones considered in this work), there exist hardness barriers dictating $\text{Time}(n,r)=\mathrm{\Omega }(nLogr)$ for every $r\in [1,n]$ under a relevant computation model. Motivated by this, we say that an algorithm $𝒜$ guarantees a $\log (r)$-streak of $\text{LogStreak}(n)$ if its running time satisfies $\text{Time}(n,r)=O(nLogr)$ for all $r\le \text{LogStreak}(n)$.

The worst $\log (r)$-streak guarantee is $\text{LogStreak}(n)=O(1)$ – this is trivial because any query can be answered in $O(n)$ time. Ideally, we would like to have $\text{LogStreak}(n)=n$, but this is not always possible as argued later in the paper. For practical use, however, it would suffice for an algorithm to ensure $\text{LogStreak}(n)=\mathrm{\Omega }(n^{ϵ})$ for some constant $ϵ>0$ because $\mathrm{\Omega }(n^{ϵ})$ queries are perhaps already too many for database cracking to be appealing.

The above definition framework can be specialized into various problem instances that differ in the data domain $𝔻$ or the predicate domain $\mathbb{Q}$. Next, we introduce two problem classes relevant to our discussion:

• $\mathrm{■}$

  A problem instance is decomposable if, for any disjoint sets $S_1,S_2\subseteq 𝔻$ and any predicate $q\in \mathbb{Q}$, it is possible to derive ${\text{Ans}}_q(S_1\cup S_2)$ from ${\text{Ans}}_q(S_1)$ and ${\text{Ans}}_q(S_2)$ in constant time.

• $\mathrm{■}$

  We define a problem instance to be $(B(n),Q(n))$ spectrum indexable if the following property holds on every dataset $S\subseteq 𝔻$: for every integer $s\in [|S|]$, it is possible to construct a data structure on $S$ in $O(|S|\cdot B(s))$ time that can answer any query in $O(\frac{|S|}{s}\cdot Q(s))$ time. The term “spectrum indexable” is chosen to reflect the ability to build a “good” index structure – as far as functions $B(n)$ and $Q(n)$ are concerned – for the whole spectrum of the parameter $s$.

Two observations are important about the above definitions:

• $\mathrm{■}$

  $(B(n),Q(n))$ spectrum indexability implies that we can build a data structure on any dataset $S\subseteq 𝔻$ in $O(|S|\cdot B(|S|))$ time to answer a query in $O(Q(|S|))$ time (for this purpose, simply set $s=|S|$).

• $\mathrm{■}$

  Consider any decomposable problem instance with the following property: for any dataset $S\subseteq 𝔻$, we can build a data structure $𝒯$ in $O(|S|\cdot B(|S|))$ time to answer a query in $O(Q(|S|))$ time. Then, the problem instance must be $(B(n),Q(n))$ spectrum indexable. To see why, given an integer $s\in [|S|]$, divide $S$ arbitrarily into $m=\lceil |S|/s\rceil$ disjoint subsets $S_1,S_2,\mathrm{\dots },S_m$ where all subsets have size $s$ except $S_m$. For each $i\in [m]$, create a structure $𝒯(S_i)$ in $O(|S_i|\cdot B(s))$ time; the total time to create all the $m$ structures is $O(m\cdot s\cdot B(s))=O(|S|\cdot B(s))$. To answer a query $q$, simply search every $𝒯(S_i)$ to obtain ${\text{Ans}}_q(S_i)$ in $O(Q(s))$ time and then combine ${\text{Ans}}_q(S_1),{\text{Ans}}_q(S_2),\mathrm{\dots },{\text{Ans}}_q(S_m)$ into ${\text{Ans}}_q(S)$ using $O(m)$ time. The total query time is therefore $O(m\cdot Q(s))$.

We assume, w.l.o.g., that $n$ is a power of 2. As with the bottom-up approach, at any moment, we divide $S$ arbitrarily into runs with the same size $s=2^i$ for some $i\ge 0$. For each run, build a structure on the elements therein. The initial run size $s$ is 1. Every time $s$ grows from $2^i$ to $2^j$ for some value $j>i$, an overhaul is performed to construct the runs of size $2^j$. By linear mergeability, we can build the structure of a size-$2^j$ run by merging the structures of $2^{j-i}$ runs of size $2^i$ in $O(2^j\cdot (j-i))$ time. By an analysis similar to the one in Section 2, if the current run size is $s$, the overall cost of producing the structures for all the runs that ever appeared in history is $O(nLogs)$.

A query with predicate $q$ is answered by searching the structure of every run, and then combining the answers from all the runs into ${\text{Ans}}_q(S)$. The query cost is $O(\frac{n}{s}\cdot Q(s))$. We require that, before answering the $i$-th ($i\ge 1$) query, the run size $s$ must satisfy

If this requirement is not met, we launch an overhaul to increase $s$ to the least power of 2 fulfilling (2). This ensures that the $i$-th query is answered with a cost $O(n/i)$. Hence, the total cost of processing $r$ queries is $O(nLogr)$.

What remains is to bound the cost of the overhauls. The final run size $s$ is the least power of 2 satisfying

• $\mathrm{■}$

  $s\le n$ (the run size cannot exceed $n$) and

• $\mathrm{■}$

  $s/Q(s)\ge r$ (because of (2)).

Rather than solving $s$ precisely, we instead aim to find an upper bound for it. As $Q(s)=O(s^{1-ϵ})$, we know $Q(s)\le \alpha \cdot s^{1-ϵ}$ for some constant $\alpha >0$. Hence, $s/Q(s)\ge s^{ϵ}/\alpha$. Let $\widehat{s}$ be the least power of 2 satisfying

$\widehat{s}\le n$ and ${\widehat{s}}^{ϵ}/\alpha \ge r$.

Since the condition $s^{ϵ}/\alpha \ge r$ implies $s/Q(s)\ge r$, it holds that $\widehat{s}\ge s$.

The condition ${\widehat{s}}^{ϵ}/\alpha \ge r$ can be rewritten as $\widehat{s}\ge {(\alpha \cdot r)}^{1/ϵ}$. Therefore, if ${(\alpha \cdot r)}^{1/ϵ}\le n/2$, then $\widehat{s}$ is simply the least power of 2 at least ${(\alpha \cdot r)}^{1/ϵ}$. This means $\widehat{s}=O(r^{1/ϵ})$ and thus $O(Logs)=O(Log\widehat{s})=O(Logr)$, in which case all the overhauls require $O(nLogs)=O(nLogr)$ time overall.

The above argument does not work if ${(\alpha \cdot r)}^{1/ϵ}>n/2$. However, in this case, $r>n^{ϵ}/(2^{ϵ}\alpha )$, that is, $r$ is already a polynomial of $n$. This motivates the following brute-force strategy. When $r$ reaches $\lceil n^{ϵ}/(2^{ϵ}\alpha )\rceil$ – a moment we call the snapping point – we simply create a structure on the whole $S$ in $O(n\log n)=O(n\log r)$ time, and use it to answer every subsequent query in $O(Q(n))$ time until $r=\min \{n,\frac{c\cdot n\log n}{Q(n)}\}$. All the queries after the snapping point have a total cost of $O(n\log n)=O(n\log r)$. We thus have obtained an algorithm that guarantees $\text{Time}(n,r)=O(nLogr)$ for all $r\le \min \{n,\frac{c\cdot n\log n}{Q(n)}\}$. $◀$

The above reduction crucially relies on the fact that the structure $𝒯$ is linearly mergeable. Otherwise, the overhaul for creating size-$2^i$ runs would become $\mathrm{\Omega }(n\cdot \log (2^i))$, in which case all the overhauls would end up with a total cost of $\mathrm{\Omega }(n\cdot {Log}^{2}r)$. Next, we will present another reduction that can shave a $Logr$ factor.

For proving hardness results, we can specialize the problem class at will, and we do so by considering only decomposable problems. A reduction algorithm $𝒜$ is required to work on any decomposable problem that is $(B(n),Q(n))$ spectrum indexable. As explained in Section 1.1, this implies a data structure $𝒯$ that can be built on any $S\subseteq 𝔻$ in $O(|S|\cdot B(|S|))$ time and answer any query on $S$ in $O(Q(|S|))$ time.

As long as $(B(n),Q(n))$ spectrum indexability is retained, we can restrict the functionality of $𝒯$ to make it hard for $𝒜$. Specifically, $𝒯$ provides only the following “services” to $𝒜$:

• $\mathrm{■}$

  $𝒜$ can create a structure $𝒯(S^{\prime })$ on any subset $S^{\prime }\subseteq S$;

• $\mathrm{■}$

  given a predicate $q\in \mathbb{Q}$, $𝒜$ can use $𝒯(S^{\prime })$ to find the answer ${\text{Ans}}_q(S^{\prime })$ on $S^{\prime }$;

• $\mathrm{■}$

  given a predicate $q$, after $𝒜$ already has obtained ${\text{Ans}}_q(S_1^{\prime })$ and ${\text{Ans}}_q(S_2^{\prime })$ for disjoint subsets $S_1^{\prime },S_2^{\prime }\subseteq S$, it can combine the answers into ${\text{Ans}}_q(S_1^{\prime }\cup S_2^{\prime })$ in constant time (the combining algorithm is provided by $𝒯$).

Despite its limited functionalities, $𝒯$ still makes the problem $(B(n),Q(n))$ spectrum indexable because the problem is decomposable; see the explanation in Section 1.1.

So far no restriction has been imposed on the behavior of $𝒜$, but we are ready to do so now. To answer a query, the algorithm $𝒜$ needs to search the structures on a number (including zero) of subsets of $S$, say, $𝒯(S_1^{\prime }),𝒯(S_2^{\prime }),\mathrm{\dots },𝒯(S_t^{\prime })$. The algorithm can choose any $t\ge 0$ and any $S_1^{\prime },{𝒮}_2^{\prime },\mathrm{\dots },S_t^{\prime }$ (they do not need to be disjoint). In addition, $𝒜$ is also allowed to examine another subset $S_{\mathrm{𝑠𝑐𝑎𝑛}}^{\prime }\subseteq S$ by paying $\mathrm{\Omega }(|S_{\mathrm{𝑠𝑐𝑎𝑛}}^{\prime }|)$ time. With all these, the algorithm must ensure

The above constraint is natural because otherwise at least one element of $S$ is absent from $S_{\mathrm{𝑠𝑐𝑎𝑛}}^{\prime }\cup S_1^{\prime }\cup S_2^{\prime }\cup \mathrm{\dots }\cup S_t^{\prime }$. If the algorithm $𝒜$ “dares” to return the query answer anyway, it must have acquired certain special properties of the underlying problem. In this work, we are interested in generic reductions that are unaware of problem-specific properties.

We will refer to reduction algorithms obeying the above requirements as black-box reductions. Our algorithms in Lemma 2 and Theorem 1 belong to the black-box class.

We will prove that any black-box reduction can answer only $r=O(\frac{n\log n}{Q(n)})$ queries in $O(nLogr)$ time for any function $Q(n):{\mathbb{N}}^{+}\to {\mathbb{N}}^{+}$ that

• $\mathrm{■}$

  satisfies $Q(n)=O(n)$, and $Q(n)=\mathrm{\Theta }(Q(c\cdot n))$ for any constant $c>0$;

• $\mathrm{■}$

  is sub-additive, i.e., $Q(x+y)\le Q(x)+Q(y)$ holds for any $x,y\ge 1$.

This will confirm the tightness of Theorem 1 on the black-box class.

We will contrive a decomposable problem and an accompanying data structure, both of which make no sense in reality but nonetheless are sound in mathematics. The dataset $S$ consists of $n$ arbitrary elements; given any predicate, a query on $S$ always returns $|S|$ (the concrete forms of elements and predicates are irrelevant). Whenever asked to “build” a data structure on $S$, we waste on purpose $|S|\log |S|$ time and then simply output an arbitrary permutation of $S$ in an array. Whenever asked to “answer” a query, we waste on purpose $Q(|S|)$ time and then return $|S|$. The problem is clearly decomposable.

We argue that any black-box reduction algorithm $𝒜$ needs $\mathrm{\Omega }(Q(n))$ time to answer every query. Consider an arbitrary query and suppose that $𝒜$ processes it by searching the structures $𝒯(S_1^{\prime }),\mathrm{\dots },𝒯(S_t^{\prime })$ for some $t\ge 0$ and scanning $S_{\mathrm{𝑠𝑐𝑎𝑛}}^{\prime }$. By the design of our structure, the query cost is at least

By definition of $\log (r)$-streak, algorithm $𝒜$ must process $r=\text{LogStreak}(n)$ queries within a total cost of $O(n\log r)$, which obviously cannot exceed $O(n\log n)$ (remember $r\le n$). It thus follows that $𝒜$ can process only $O(\frac{n\log n}{Q(n)})$ queries.

The problem can be converted [19] to the following equivalent form by resorting to geometry duality [7]:

• $\mathrm{■}$

  Line through convex hull. $S$ is a set of $n$ points in ${ℝ}^2$. Given any line $l$ in ${ℝ}^2$, a query determines if $l$ intersects with the convex hull of $S$, denoted as $\text{CH}(S)$.

We will concentrate on the above problem instead.

Suppose, for now, that we are given a point $q$ on $l$ that falls outside $\text{CH}(S)$. From $q$, we can shoot two tangent rays, each touching $\text{CH}(S)$ but not entering into the interior of $\text{CH}(S)$. In Figure 1(a) where $S$ is the set of black points, the first ray passes point $p_1\in S$ while the second passes $p_2\in S$. The two rays form a “wedge” enclosing $\text{CH}(S)$ within (note that the angle of the wedge is less than 180^∘); we will call it the wedge of $q$ on $\text{CH}(S)$. Line $l$ passes through $\text{CH}(S)$ if and only if $l$ goes through the wedge. If the vertices of $\text{CH}(S)$ have been stored in clockwise order, the two tangent rays can be found in $O(\log n)$ time [25].

We will prove that the “line through convex hull” problem is $(Logn,Logn)$ spectrum indexable. Take any integer $s\in [1,n]$ and set $m=\lceil n/s\rceil$. Divide $S$ arbitrarily into $S_1$, $S_2$, …, $S_m$ such that $|S_i|=s$ for $i\in [m-1]$ and $|S_m|=n-s(m-1)$. To build a structure $𝒯$, use $O(sLogs)$ time to compute $\text{CH}(S_i)$ for each $i\in [m]$ and store its vertices in clockwise order. The structure’s construction time is $O(nLogs)$. Let us see how to answer a query with line $l$. Suppose, once again, that a point $q$ on $l$ outside $\text{CH}(S)$ is given. For each $i\in [m]$, compute the wedge of $q$ on $\text{CH}(S_i)$ in $O(Logs)$ time. From these $m$ wedges, it is a simple task to obtain in $O(m)$ time the wedge of $q$ on $\text{CH}(S)$ (we will deal with a more general problem shortly in discussing “convex hull containment”). Now, whether $l$ intersects with $\text{CH}(S)$ can be determined easily. The query time so far is $O(mLogs)$.

It remains to explain how to find $q$. This can be done in $O(1)$ time if we already have the minimum axis-parallel bounding rectangle of $S$, denoted as $\text{MBR}(S)$. Note that $\text{MBR}(S)$ must contain $\text{CH}(S)$; see Figure 1(b). It is clear that $\text{MBR}(S)$ can be obtained from $\text{MBR}(S_1)$, $\text{MBR}(S_2)$, …, $\text{MBR}(S_m)$ in $O(m)$ time, while each $\text{MBR}(S_i)$ ($i\in [m]$) can be computed in $O(s)$ time during the construction of the structure $𝒯$. We thus conclude that the problem is $(Logn,Logn)$ spectrum indexable and can now apply Theorem 1.

In this problem, $S$ is a set of $n$ points in ${ℝ}^2$. Given any point $q\in {ℝ}^2$, a query determines if $q$ is covered by $\text{CH}(S)$. We will prove that the problem is $(Logn,Logn)$ spectrum indexable.

Take any integer $s\in [1,n]$ and set $m=\lceil n/s\rceil$. Divide $S$ arbitrarily into $S_1$, $S_2$, …, $S_m$ such that $|S_i|=s$ for $i\in [m-1]$ and $|S_m|=n-s(m-1)$. To build a structure $𝒯$, compute $\text{CH}(S_i)$ for each $i\in [m]$ and store its vertices in clockwise order; this takes $O(nLogs)$ time as explained before. Let us see how to answer a query given point $q$. For each $i\in [m]$, whether $q$ is covered by $\text{CH}(S_i)$ can be checked in $O(Logs)$ time [25]. If the answer yes for any $i$, point $q$ must be covered by $\text{CH}(S)$, and we are done. The subsequent discussion assumes that $q$ is outside $\text{CH}(S_i)$ for all $i$. In $O(mLogs)$ time, compute the wedge of $q$ on $\text{CH}(S_i)$ for all $i\in [m]$ as described in the previous problem.

It remains to determine from the $m$ wedges whether $q$ is covered by $\text{CH}(S)$. This can be re-modeled as the following problem. Place an arbitrary circle centered at $q$. For each wedge, its two bounding rays intersect the circle into an arc of less than 180^∘. Let $a_1,a_2,\mathrm{\dots },a_m$ be the arcs produced this way, and define $a^{\ast }$ to be the smallest arc on the circle covering them all. Figure 1(c) shows an example with $m=3$. Arc $a_1$ is subtended by points A and B, arc $a_2$ by points C and D, and arc $a_3$ by points E and F. Here, the smallest arc $a^{\ast }$ goes clockwise from point A to F. Crucially, $q$ is covered by $\text{CH}(S)$ if and only if $a^{\ast }$ spans at least ${180}^{\circ }$ (this is the case in Figure 1(c)) – note that if $q$ is outside $\text{CH}(S)$, then $a^{\ast }$ must be subtended by the wedge of $q$ on $\text{CH}(S)$, which must be less than ${180}^{\circ }$. Therefore, the goal is to determine whether $a^{\ast }$ is at least ${180}^{\circ }$.

It is possible to achieve the purpose in $O(m)$ time (even if the $m$ arcs are given to us in an arbitrary order). For this purpose, we process the arcs one by one, maintain the smallest arc $a^{\ast }$ covering the arcs already processed, and stop the algorithm when it becomes clear that $a^{\ast }$ must be at least ${180}^{\circ }$. Specifically, for $i=1$, simply set $a^{\ast }$ to $a_1$. Iteratively, given the next arc $a_i$ ($i\ge 2$), check in constant time if an arc of less than ${180}^{\circ }$ can cover both $a_i$ and $a^{\ast }$. If so, update $a^{\ast }$ to that arc; otherwise, stop the algorithm. In Figure 1(c), for example, after $a_2$ is processed, the $a^{\ast }$ we maintain goes clockwise from A to D. When processing $a_3$, the algorithm realizes that $a^{\ast }$ must be at least ${180}^{\circ }$ and hence terminates.