Succinct Data Structures for Segments

This paper considers succinct data structures for the segment representation problem. We show the following main result on a standard unit cost word RAM model with logarithmic word size.

Compared to previous results of Bille and Gørtz [2], Theorem 1 improves the space bounds from $O(n\lg n)$ to $2n\lg n+O(n\lg n/\lg \lg n)$. At the same time, we obtain the optimal $O(\lg n/\lg \lg n)$ query time for segment selection and implement the segment rank query in the same time. Furthermore, we show that the space bound of Theorem 1 is optimal up to lower order terms.

Finally, we show that the query time for segment rank is also optimal.

We obtain our results by first considering a novel and simple structure, the segment wavelet tree, which may be of independent interest. The segment wavelet tree is inspired by the classical wavelet tree structure of Grossi et al. [9], and builds on the observation that the number of segments crossing a vertical line is the difference between the number of left and right endpoints occurring before said line. In the same manner, as the wavelet tree recursively splits the alphabet in its lower and upper half, the segment wavelet tree recursively splits the segments in the lower and upper half of the plane. Because of this, the segment wavelet tree can be used to search for the $j$th segment crossing a vertical line. The segment wavelet tree, however, only achieves $O(\lg n)$ query time since it only splits the plane into $2$ horizontal bands. In order to speed up the query to $O(\lg n/\lg \lg n)$ we generalize the segment wavelet tree to the $\mathrm{\Delta }$-ary segment wavelet tree, which splits the plane into $\mathrm{\Delta }$ horizontal bands called slabs, leading to Theorem 1. Next, we prove the information-theoretical lower bound of representing horizontal line segments by showing that in rank space, we need at least $2n\lg n-O(n)$ bits of space to represent $n$ horizontal line segments. Finally, we prove a matching lower bound for the segment rank query on horizontal line segments by showing that any static solution using $n{\lg }^{O(1)}n$ bits of space needs $\mathrm{\Omega }(\lg n/\lg \lg n)$ query time. To do so, we show a reduction from 2-dimensional dominance counting [19].

We present the required preliminaries for our solution in Section 2, and then we describe a simple structure in Section 3 and how we can answer segment rank and select queries with this structure. We then show our structure in Section 4 and how we answer rank and select queries succinctly in $O(\lg n/\lg \lg n)$ time leading to Theorem 1. Finally, we prove the space lower bounds for representing segments in rank space leading to Theorem 2 and prove the lower bounds for segment rank queries leading to Theorem 3 in Section 5.

Let $S[1,n]$ be a string of $n$ characters from an alphabet $\mathrm{\Sigma }=\{1,2,\mathrm{\dots },\sigma \}$ and define the following operations.

• $\mathrm{■}$

  $\text{access}(S,i):$ return $S[i]$.

• $\mathrm{■}$

  $\text{rank}(S,\alpha ,i):$ return the number of occurrences of character $\alpha$ in $S[1,i]$.

• $\mathrm{■}$

  $\text{select}(S,\alpha ,i):$ return the position in $S$ of the $i$th occurrence of character $\alpha$.

For binary strings, we use the following well-known result:

Let $ℒ$ be a set of $n$ horizontal line segments in rank space. We define the segment wavelet tree as a recursive decomposition of the line segments in $ℒ$ similar to the wavelet tree. For simplicity, we assume that $n$ is a power of $2$. Define $ℒ[a,b]\subseteq ℒ$ to be the segments with $y$-coordinate in $[a,b]$. The segment wavelet tree $T$ for $ℒ$ is a complete balanced binary tree on $n$ leaves. Each node $v$ represents a set of segments $ℒ(v)=ℒ[a,b]$. The root $r$ represents $ℒ(r)=ℒ[1,n]=ℒ$. Let $v$ be an internal node representing the segments $ℒ(v)=ℒ[a,b]$, and let $v_0$ and $v_1$ be the left and right child of $v$, respectively. Then $v_0$ represents the segments $ℒ(v_0)=ℒ[a,\lfloor (b-a)/2\rfloor ]$ and $v_1$ represents the segments $ℒ(v_1)=ℒ[\lfloor (b-a)/2\rfloor +1,b]$. A leaf node $v$ represents a single segment $ℒ(v)=ℒ[a,a]$.

We store the segment wavelet tree succinctly as follows. Each internal node $v$ stores two bitstrings $B^L(v)$ and $B^R(v)$ of length $|ℒ(v)|$.

Furthermore, we store a bitstring $E[1,2n]$ where

See Figure 1 for an example.

Alternatively, one can also view the segment wavelet tree as two superimposed wavelet trees of the strings $Y^L[1,n]$ and $Y^R[1,n]$, where $Y^L[1,n]$ and $Y^R[1,n]$ are the strings of $y$-coordinates of the left and right endpoints, respectively, ordered by increasing $x$-coordinate.

To achieve the desired space bounds, we store $B^L$ and $B^R$ as their superimposed wavelet trees $Y^L$ and $Y^R$ according to Lemma 6 and the bitstring $E$ according to Lemma 4.

We now show how to answer segment-access queries in $O(\lg n)$ time. To answer a $\text{segment-access}(y)$ query, we do a bottom-up traversal of the segment wavelet tree $T$ starting at the $y$th leaf in the left-to-right order. Let $s=(x_l,x_r,y)$ denote the segment we are searching for. At each node $v$ in the traversal we maintain the following local variables:

We perform the traversal as follows. Initially, $v$ is the $y$th leaf and $l_v=r_v=1$. Consider a non-root node $v$ with parent $v_p$ and let $b=0$ if $v$ is the left child of $v_p$ and $b=1$ otherwise. We compute $l_{v_p}=\mathrm{𝗌𝖾𝗅𝖾𝖼𝗍}(B^L(v_p),b,l_v)$ and $r_{v_p}=\mathrm{𝗌𝖾𝗅𝖾𝖼𝗍}(B^R(v_p),b,r_v)$. When we reach the root $u$ we compute $x_l=\text{select}(E,0,l_u)$ and $x_r=\text{select}(E,1,r_u)$. Finally, we return $(x_l,x_r,y)$.

We now show how to answer segment-select queries in $O(\lg n)$ time. To answer a $\text{segment-select}(i,j)$ query, we do a top-down traversal in the segment wavelet tree $T$ starting at the root and ending in the leaf containing the $j$th crossing segment of the vertical line at time $i$.

At each node $v$ with $ℒ(v)=ℒ[a,b]$ in the traversal we maintain the following local variables:

We perform the traversal as follows. Initially, $v$ is the root and we have $r_v=\text{rank}(E,1,i)$, $l_v=i-r_v,{\overline{j}}_v=0$ and $j_v=j$. Consider an internal node $v$ with children $v_0$ and $v_1$ and suppose we have computed $l_v$, $r_v,{\overline{j}}_v$, and $j_v$. We first compute the number of segments $k$ in $ℒ(v_0)$ crossing the vertical line at $i$ as

That is, $k$ is computed as the number of left endpoints of segments in $ℒ(v_0)$ with $x$-coordinate at most $i$ subtracted by the number of right endpoints in $ℒ(v_0)$ with $x$-coordinate at most $i$.

We continue the traversal in child $v_b$, where $b=0$ if $j_v\le k$ and $b=1$ otherwise.

We then compute the local variables for the child $v_b$ as

When $v$ is a leaf and $ℒ(v)=ℒ[a,a]$ we return $a$.

We now show how to answer segment-rank queries in $O(\lg n)$ time. To answer a $\text{segment-rank}(i,y)$ we perform a top-down traversal in the segment wavelet tree $T$ starting at the root and ending in the leaf $v$ such that $ℒ(v)=ℒ[y,y]$. At each node $v$ in the traversal we compute the local variables $l_v$, $r_v$ and ${\overline{j}}_v$ in the same manner as in Section 3.3. We perform the traversal as follows. Consider an internal node $v$ with $ℒ(v)=ℒ[a,b]$ and children $v_0$ and $v_1$, we continue the traversal in child $v_b$, where $b=0$ if $y\le \lfloor (b-a)/2\rfloor$ and $b=1$ otherwise. When $v$ is a leaf we return $\overline{j_v}+(l_v-r_v)$.

Let $ℒ$ be a set of $n$ horizontal line segments partitioned into $\mathrm{\Delta }=\lceil {\lg }^{ϵ}n\rceil$ slabs of approximately equal size, where . The slab representation problem is to preprocess $ℒ$ to support the operations:

• $\mathrm{■}$

  $\text{slab-select}(v,i,j)$: return the slab $k$ containing the $j$th segment in $ℒ(v)$ according to increasing $y$-coordinate among the segments crossing the vertical line through $x$-coordinate $i$.

• $\mathrm{■}$

  $\text{slab-rank}(v,i,j)$: return the number of segments in $ℒ(v)$ crossing the vertical line through $x$-coordinate $i$ in slabs $[1,j]$.

• $\mathrm{■}$

  $\text{endpoint-select}(v,k,i)$: return the $x$-coordinate of the $i$th endpoint in $ℒ(v)$ in the $k$th slab according to increasing $x$-coordinate among the segments.

• $\mathrm{■}$

  $\text{endpoint-rank}(v,k,i)$: return the number of endpoints in $ℒ(v)$ in the $k$th slab who has a $x$-coordinate of at most $i$.

In [2] they show that slab-select and slab-rank can be done in $O(n\lg {\lg }^{ϵ}n)$ space and constant query time using $O(n)$ preprocessing time. We show how to modify this result and the analysis to achieve $2n\lg {\lg }^{ϵ}n+O(n)$ bits of space while maintaining constant query time.

Let $ℒ$ be a set of $n$ horizontal line segments in rank space. We define the $\mathrm{\Delta }$-ary segment wavelet tree as a recursive decomposition of the line segments in $ℒ$ similar to the $\mathrm{\Delta }$-ary wavelet tree. For simplicity, we assume that $n$ is a power of $\mathrm{\Delta }$. Define $ℒ[a,b]\subseteq ℒ$ to be the segments with $y$-coordinate in $[a,b]$. The $\mathrm{\Delta }$-ary segment wavelet tree $T$ for $ℒ$ is a complete balanced $\mathrm{\Delta }=\lceil {\lg }^{ϵ}n\rceil$ tree on $n$ leaves. Each node $v$ represents a set of segments $ℒ(v)=ℒ[a,b]$. The root $r$ represents $ℒ(r)=ℒ[1,n]=ℒ$. Let $v$ be an internal node representing the segments $ℒ(v)=ℒ[a,b]$, and let $v_0,\mathrm{\dots },v_{\mathrm{\Delta }-1}$ be the children of $v$. Then $v_i$ represents the segments $ℒ(v_i)=ℒ[a+\lfloor (1+b-a)/\mathrm{\Delta }\cdot i\rfloor ,a+\lfloor (1+b-a)/\mathrm{\Delta }\cdot (i+1)\rfloor -1]$. A leaf node $v$ represents a single segment $ℒ(v)=ℒ[a,a]$. We store the $\mathrm{\Delta }$-ary segment wavelet tree succinctly as follows. Intuitively, each internal node $v$ stores the structure of Lemma 8, but to achieve the desired space complexity, we instead, for each level in the $\mathrm{\Delta }$-ary segment wavelet tree, concatenate the segments of the nodes on that level into one single structure of Lemma 8, as in [16]. Since there is exactly one segment of each $y$ coordinate, we can easily maintain the indices into the single structure corresponding to each node. When $n$ is not a power of $\mathrm{\Delta }$, we pack the segments such that all levels in $T$ are complete except possibly the lowest, which is filled from the left. We then store the path along with indices to the rightmost leaf on the lowest level. This allows us to compute the indices into the single structure of each level.

We now show how to answer segment-access queries in $O(\lg n/\lg \lg n)$ time. To answer a $\text{segment-access}(y)$ query, we first compute the path to the $y$th leaf in the left-to-right order. We can trivially compute the path by performing a top-down traversal of the $\mathrm{\Delta }$-ary segment wavelet tree $T$ starting at the root and ending in the $y$th leaf. We then do a bottom-up traversal of the $\mathrm{\Delta }$-ary segment wavelet tree $T$ starting at the $y$th leaf. Let $s=(x_l,x_r,y)$ denote the segment we are searching for. At each node $v$ in the traversal we maintain the following local variables:

We perform the traversal as follows. Initially, $v$ is the $y$th leaf and $l_v=1$ and $r_v=2$. Consider a non-root node $v$ with parent $v_p$ and let $v$ be the $k$th child of $v_p$. We compute $l_{v_p}=\text{endpoint-select}(v_p,k,l_v)$ and $r_{v_p}=\text{endpoint-select}(v_p,k,r_v)$. When we reach the root $u$ we return $(l_u,r_u,y)$.

We now show how to answer segment-select queries in $O(\lg n/\lg \lg n)$ time. To answer a $\text{segment-select}(i,j)$ query, we do a top-down traversal in the $\mathrm{\Delta }$-ary segment wavelet tree $T$ starting at the root and ending in the leaf containing the $j$th crossing segment of the vertical line at time $i$.

At each node $v$ with $ℒ(v)=ℒ[a,b]$ in the traversal we maintain the following local variables:

We perform the traversal as follows. Initially, $v$ is the root and we have $i_v=i$, ${\overline{j}}_v=0$ and $j_v=j$. Consider an internal node $v$ with children $v_0,\mathrm{\dots },v_{\mathrm{\Delta }-1}$ and suppose we have computed $l_v$, ${\overline{j}}_v$, and $j_v$. We compute the child $v_k$ containing the $j_v$th segment crossing the vertical line at $i_v$ as

We then compute the local variables for the child $v_k$ as

When $v$ is a leaf and $ℒ(v)=ℒ[a,a]$ we return $a$.

We now show how to answer segment-rank queries in $O(\lg n/\lg n\lg n)$ time. To answer a $\text{segment-rank}(i,y)$, we perform a top-down traversal in the segment wavelet tree $T$ starting at the root and ending in the leaf $v$ such that $ℒ(v)=ℒ[y,y]$. At each node $v$ with $ℒ(v)=ℒ[a,b]$ in the traversal, we compute the local variables $i_v$, and ${\overline{j}}_v$ in the same manner as in Section 4.4. We perform the traversal as follows. Consider an internal node $v$ with $ℒ(v)=ℒ[a,b]$ and children $v_0,\mathrm{\dots },v_{\mathrm{\Delta }-1}$. we continue the traversal in child $v_k$, where $k=\lfloor (y-a)/((1+b-a)/\mathrm{\Delta })\rfloor$. When $v$ is a leaf we return $\overline{j_v}+1$ if $i_v=1$ and $\overline{j_v}$ otherwise.

Here, we show Theorem 2. Let $ℒ$ be a set of $n$ horizontal line segments in rank space on the plane $[1,2n]\times [1,n]$ such that there is exactly one endpoint on each $x$-coordinate and one segment on each $y$-coordinate. If we only consider the $x$-coordinates of the left and right endpoint of each segment, then the number of ways to arrange $n$ pairs of endpoints is the number of ways that we can pair $2n$ elements.

Since each segment has a unique $y$-coordinate, the number of ways the segments can be arranged on the $y$-axis is $n!$. Thus, the number of ways to arrange $n$ segments in rank space $[1,2n]\times [1,n]$ is $\frac{(2n)!}{2^n}$. Thus to distinguish between each instance we need $\lceil \lg \frac{(2n)!}{2^n}\rceil =2n\lg n-O(n)$ bits. In summary, we have shown Theorem 2.

Here, we show Theorem 3. We reduce from 2-dimensional dominance counting. The 2-dimensional dominance counting problem is to preprocess $n$ points $(x_1,y_1),\mathrm{\dots },(x_n,y_n)$ from rank space, such that given a point $(x,y)$ compute the number of points $(x_i,y_i)$ such that $x_i\le x$ and $y_i\le y$.

Given $n$ points $(x_1,y_1),\mathrm{\dots },(x_n,y_n)$ to the 2-dimensional dominance counting problem, we construct an instance of the segment representation problem. We assume wlog. that these $n$ points are in rank space on the plane $[1,n]\times [1,n]$ such that there is exactly one point on each $x$ and $y$ coordinate. To see why this assumption is acceptable to establish the lower bound, we refer to the discussion by Pătrașcu [19]. We construct the $n$ segments $ℒ$ as follows: For each point $(x_i,y_i)$ we construct the corresponding segment such that the left endpoint is $(x_i,y_i)$ and the right endpoint is $(n+x_i,y_i)$ for $1\le i\le n$. For a given query point $(x,y)$, we count the number of points $(x_i,y_i)$ such that $x_i\le x$ and $y_i\le y$ by performing the query $\text{segment-rank}(x,y)$. Since no segment ends before $x$-coordinate $n$, the number of segments crossing the vertical line through $x$-coordinate $x$ with $y$-coordinate in $[1,y]$ are the segments with left endpoints $(x_i,y_i)$ such that $x_i\le x$ and $y_i\le y$. In summary, we have shown Theorem 3.