# The Complexity of the Co-Occurrence Problem

Philip Bille  Inge Li Gørtz  Tord Stordalen

###### Abstract

Let $S$ be a string of length $n$ over an alphabet $\Sigma$ and let $Q$ be a
subset of $\Sigma$ of size $q\geq 2$. The _co-occurrence problem_ is to
construct a compact data structure that supports the following query: given an
integer $w$ return the number of length-$w$ substrings of $S$ that contain
each character of $Q$ at least once. This is a natural string problem with
applications to, e.g., data mining, natural language processing, and DNA
analysis. The state of the art is an $O(\sqrt{nq})$ space data structure that
— with some minor additions — supports queries in $O(\log\log n)$ time [CPM
2021].

Our contributions are as follows. Firstly, we analyze the problem in terms of
a new, natural parameter $d$, giving a simple data structure that uses $O(d)$
space and supports queries in $O(\log\log n)$ time. The preprocessing
algorithm does a single pass over $S$, runs in expected $O(n)$ time, and uses
$O(d+q)$ space in addition to the input. Furthermore, we show that $O(d)$
space is optimal and that $O(\log\log n)$-time queries are optimal given
optimal space. Secondly, we bound $d=O(\sqrt{nq})$, giving clean bounds in
terms of $n$ and $q$ that match the state of the art. Furthermore, we prove
that $\Omega(\sqrt{nq})$ bits of space is necessary in the worst case, meaning
that the $O(\sqrt{nq})$ upper bound is tight to within polylogarithmic
factors. All of our results are based on simple and intuitive combinatorial
ideas that simplify the state of the art.

Technical University of Denmark, DTU Compute, Kgs. Lyngby, Denmark

<EMAIL_ADDRESS>
##  1 Introduction

We consider the _co-occurrence problem_ which is defined as follows. Let $S$
be a string of length $n$ over an alphabet $\Sigma$ and let $Q$ be a subset of
$\Sigma$ of size $q\geq 2$. For two integers $i$ and $j$ where $1\leq i\leq
j\leq n$, let $[i,j]$ denote the discrete interval $\\{i,i+1,\ldots,j\\}$, and
let $S[i,j]$ denote the substring of $S$ starting at $S[i]$ and ending at
$S[j]$. The interval $[i,j]$ is a _co-occurrence_ of $Q$ in $S$ if $S[i,j]$
contains each character in $Q$ at least once. The goal is to preprocess $S$
and $Q$ into a data structure that supports the query

  * •

$\textsf{co}_{S,Q}(w)$: return the number of co-occurrences of $Q$ in $S$ that
have length $w$, i.e., the number of length-$w$ substrings of $S$ that contain
each character in $Q$ at least once.

For example, let $\Sigma=\\{\texttt{A},\texttt{B},\texttt{C},\texttt{-}\\}$,
$Q=\\{\texttt{A},\texttt{B},\texttt{C}\\}$ and

$S\;=\;\underset{1}{\texttt{-}}\;\;\underset{2}{\texttt{-}}\;\;\underset{3}{\texttt{-}}\;\;\underset{4}{\texttt{-}}\;\;\underset{5}{\texttt{B}}\;\;\underset{6}{\texttt{C}}\;\;\underset{7}{\texttt{-}}\;\;\underset{8}{\texttt{A}}\;\;\underset{9}{\texttt{C}}\;\;\underset{10}{\texttt{C}}\;\;\underset{11}{\texttt{B}}\;\;\underset{12}{\texttt{-}}\;\;\underset{13}{\texttt{-}}\;\;.$

Then

  * •

$\textsf{co}_{S,Q}(3)=0$, because no length-three substring contains all three
characters A, B, and C.

  * •

$\textsf{co}_{S,Q}(4)=2$, because both $[5,8]$ and $[8,11]$ are co-occurrences
of $Q$.

  * •

$\textsf{co}_{S,Q}(8)=6$, because all six of the length-eight substrings of
$S$ are co-occurrences of $Q$.

Note that only sublinear-space data structures are interesting. With linear
space we can simply precompute the answer to $\textsf{co}_{S,Q}(i)$ for each
$i\in[0,n]$ and support queries in constant time.

This is a natural string problem with applications to, e.g., data mining, and
a large amount of work has gone towards related problems such as finding
frequent items in streams [6, 7, 8, 10] and finding frequent sets of items in
streams [1, 3, 4, 9, 11, 12, 16]. Furthermore, it is similar to certain string
problems, such as episode matching [5] where the goal is to determine all the
substrings of $S$ that occur a certain number of times within a given distance
from each other. Whereas previous work is mostly concerned with identifying
frequent patterns either in the whole string or in a sliding window of fixed
length, Sobel, Bertram, Ding, Nargesian and Gildea [14] introduced the problem
of studying a given pattern across all window lengths (i.e., determining
$\textsf{co}_{S,Q}(i)$ for all $i$). They motivate the problem by listing
potential applications such as training models for natural language processing
(short and long co-occurrences of a set of words tend to represent
respectively syntactic and semantic information), automatically organizing the
memory of a computer program for good cache behaviour (variables that are used
close to each other should be near each other in memory), and analyzing DNA
sequences (co-occurrences of nucleotides in DNA provide insight into the
evolution of viruses). See [14] for a more detailed discussion of these
applications.

Our work is inspired by [14]. They do not consider fast, individual queries,
but instead they give an $O(\sqrt{nq})$ space data structure from which they
can determine $\textsf{co}_{S,Q}(i)$ for each $i=1,\ldots,n$ in $O(n)$ time.
Supporting fast queries is a natural extension to their problem, and we note
that their solution can be extended to support individual queries in
$O(\log\log n)$ time using the techniques presented below.

A key component of our result is a solution to the following simplified
problem. A co-occurrence $[i,j]$ is _left-minimal_ if $[i+1,j]$ is not a co-
occurrence. The _left-minimal co-occurrence problem_ is to preprocess $S$ and
$Q$ into a data structure that supports the query

  * •

$\textsf{lmco}_{S,Q}(w)$: return the number of left-minimal co-occurrences of
$Q$ in $S$ that have length $w$.

We first solve this more restricted problem, and then we solve the co-
occurrence problem by a reduction to the left-minimal co-occurrence problem.
To our knowledge this problem has not been studied before.

###  1.1 Our Results

Our two main contributions are as follows. Firstly, we give an upper bound
that matches and simplifies the state of the art. Secondly, we provide lower
bounds that show that our solution has optimal space, and that our query time
is optimal for optimal-space data structures. As in previous work, all our
results work on the word RAM model with logarithmic word size.

To do so we use the following parametrization. Let $\delta_{S,Q}$ be the
difference encoding of the sequence
$\textsf{lmco}_{S,Q}(1),\ldots,\textsf{lmco}_{S,Q}(n)$. That is,
$\delta_{S,Q}(i)=\textsf{lmco}_{S,Q}(i)-\textsf{lmco}_{S,Q}(i-1)$ for each
$i\in[2,n]$ (note that $\textsf{lmco}(1)=0$ since $|Q|\geq 2$). Let
$Z_{S,Q}=\\{i\in[2,n]\mid\delta(i)\neq 0\\}$ and let $d_{S,Q}=|Z_{S,Q}|$. For
the remainder of the paper we will omit the subscript on lmco, co, $Z$, and
$d$ whenever $S$ and $Q$ are clear from the context. Note that $d$ is a
parameter of the problem since it is determined exclusively by the input $S$
and $Q$. We prove the following theorem.

######  Theorem 1.

Let $S$ be a string of length $n$ over an alphabet $\Sigma$, let $Q$ be a
subset of $\Sigma$ of size $q\geq 2$, and let $d$ be defined as above.

  * (a)

There is an $O(d)$ space data structure that supports both
$\textsf{lmco}_{S,Q}$\- and $\textsf{co}_{S,Q}$-queries in $O(\log\log n)$
time. The preprocessing algorithm does a single pass over $S$, runs in
expected $O(n)$ time and uses $O(d+q)$ space in addition to the input.

  * (b)

Any data structure supporting either $\textsf{lmco}_{S,Q}$\- or
$\textsf{co}_{S,Q}$-queries needs $\Omega(d)$ space in the worst case, and any
$d\log^{O(1)}d$ space data structure cannot support queries faster than
$\Omega(\log\log n)$ time.

  * (c)

The parameter $d$ is bounded by $O(\sqrt{nq})$, and any data structure
supporting either $\textsf{lmco}_{S,Q}$\- or $\textsf{co}_{S,Q}$-queries needs
$\Omega(\sqrt{nq})$ _bits_ of space in the worst case.

Theorem 1(a) and 1(b) together prove that our data structure has optimal
space, and that with optimal space we cannot hope to support queries faster
than $O(\log\log n)$ time. In comparison to the state of the art by Sobel et
al. [14], Theorem 1(c) proves that we match their $O(\sqrt{nq})$ space and
$O(\log\log n)$ time solution, and also that the $O(\sqrt{nq})$ space bound is
tight to within polylogarithmic factors. All of our results are based on
simple and intuitive combinatorial ideas that simplify the state of the art.

Given a set $X$ of $m$ integers from a universe $U$, the _static predecessor
problem_ is to represent $X$ such that we can efficiently answer the query
$\textsf{predecessor}(x)=\max\\{y\in X\mid y\leq x\\}$. Tight bounds by
Pătraşcu and Thorup [13] imply that $O(\log\log|U|)$-time queries are optimal
with $m\log^{O(1)}m$ space when $|U|=m^{c}$ for any constant $c>1$. The lower
bound on query time in Theorem 1(b) follows from the following theorem, which
in turn follows from a reduction from the predecessor problem to the (left-
minimal) co-occurrence problem.

######  Theorem 2.

Let $X\subseteq\\{2,\ldots,u\\}$ for some $u$ and let $|X|=m$. Let $n$, $q$,
and $d$ be the parameters of the (left-minimal) co-occurrence problem as
above. Given a data structure that supports lmco\- or co-queries in
$f_{t}(n,q,d)$ time using $f_{s}(n,q,d)$ space, we obtain a data structure
that supports predecessor queries on $X$ in $O(f_{t}(2u^{2},2,8m))$ time using
$O(f_{s}(2u^{2},2,8m))$ space.

In particular, if $f_{s}(n,q,d)=d\log^{O(1)}d$ then we obtain an
$m\log^{O(1)}m$-space predecessor data structure on $X$. If also $u=m^{c}$,
then it follows from the lower bound on predecessor queries that
$f_{t}(2u^{2},2,8m)=\Omega(\log\log u)$, which in turn implies that
$f_{t}(n,q,d)=\Omega(\log\log n)$, proving the lower bound in Theorem 1(b).

The preprocessing algorithm and the proof of Theorem 2 can be found in
Appendices A and B, respectively.

###  1.2 Techniques

The key technical insights that lead to our results stem mainly from the
structure of $\delta$.

To achieve the upper bound for lmco-queries we use the following very simple
data structure. By definition, $\textsf{lmco}(w)=\sum_{i=2}^{w}\delta(i)$.
Furthermore, by the definition of $Z$ it follows that for any $w\in[2,n]$ we
have that $\textsf{lmco}(w)=\textsf{lmco}(w_{p})$ where $w_{p}$ is the
predecessor of $w$ in $Z$. Our data structure is a predecessor structure over
the set of key-value pairs $\\{(i,\textsf{lmco}(i))\mid i\in Z\\}$ and answers
lmco-queries with a single predecessor query. There are linear space
predecessor structures that support queries in $O(\log\log|U|)$ time [15].
Here the universe $U$ is $[2,n]$ so we match the $O(d)$ space and $O(\log\log
n)$ time bound in Theorem 1(a).

Furthermore, we prove the $O(\sqrt{nq})$ upper bound on space by bounding
$d=O(\sqrt{nq})$ using the following idea. In essence, each $\delta(z)$ for
$z\in Z$ corresponds to some length-$z$ _minimal co-occurrence_ , which is a
co-occurrence $[i,j]$ such that neither $[i+1,j]$ nor $[i,j-1]$ are co-
occurrences (see below for the full details on $\delta$). We bound the
cumulative length of all the minimal co-occurrences to be $O(nq)$; then there
are at most $d=O(\sqrt{nq})$ distinct lengths of minimal co-occurrences since
$d=\omega(\sqrt{nq})$ implies that the cumulative length of the minimal co-
occurrences is at least $1+\ldots+d=\Omega(d^{2})=\omega(nq)$.

To also support co-queries and complete the upper bound we give a straight-
forward reduction from the co-occurrence problem to the left-minimal co-
occurrence problem. We show that by extending the above data structure to also
store $\sum_{i=2}^{z}\textsf{lmco}(i)$ for each $z\in Z$, we can support co-
queries with the same bounds as for lmco-queries.

On the lower bounds side, we give all the lower bounds for the left-minimal
co-occurrence problem and show that they extend to the co-occurrence problem.
To prove the lower bounds we exploit that we can carefully design lmco-
instances that result in a particular difference encoding $\delta$ by
including minimal co-occurrences of certain lengths and spacing. Our lower
bounds on space in Theorem 1(b) and 1(c) are the results of encoding a given
permutation or set in $\delta$, respectively.

Finally, as mentioned above, we prove Theorem 2 (and, by extension, the lower
bound on query time in Theorem 1(b)) by encoding a given instance of the
static predecessor problem in an lmco-instance such that the predecessor of an
element $x$ equals $\textsf{lmco}(x)$.

##  2 The Left-Minimal Co-Occurrence Problem

###  2.1 Main Idea

Let $[i,j]\subseteq[1,n]$ be a co-occurrence of $Q$ in $S$. Recall that then
each character from $Q$ occurs in $S[i,j]$ and that $[i,j]$ is left-minimal if
$[i+1,j]$ is not a co-occurrence. The goal is to preprocess $S$ and $Q$ to
support the query $\textsf{lmco}(w)$, which returns the number of left-minimal
co-occurrences of length $w$.

We say that $[i,j]$ is a _minimal co-occurrence_ if neither $[i+1,j]$ nor
$[i,j-1]$ are co-occurrences and we denote the $\mu$ minimal co-occurrences of
$Q$ in $S$ by $[\ell_{1},r_{1}],\ldots,[\ell_{\mu},r_{\mu}]$ where
$r_{1}<\ldots<r_{\mu}$. This ordering is unique since at most one minimal co-
occurrence ends at a given index. To simplify the presentation we define
$r_{\mu+1}=n+1$. Note that also $\ell_{1}<\ldots<\ell_{\mu}$ due to the
following property.

######  Property 1.

Let $[a,b]$ and $[a^{\prime},b^{\prime}]$ be two minimal co-occurrences.
Either both $a<a^{\prime}$ and $b<b^{\prime}$, or both $a^{\prime}<a$ and
$b^{\prime}<b$.

###### Proof.

If $a<a^{\prime}$ and $b\geq b^{\prime}$ then $[a,b]$ strictly contains
another minimal co-occurrence $[a^{\prime},b^{\prime}]$ and can therefore not
be minimal itself. The other cases are analogous.

∎

We now show that given all the minimal co-occurrences we can determine all the
left-minimal co-occurrences.

######  Lemma 1.

Let $[\ell_{1},r_{1}],\ldots,[\ell_{\mu},r_{\mu}]$ be the minimal co-
occurrences of $Q$ in $S$ where $r_{1}<\ldots<r_{\mu}$ and let
$r_{\mu+1}=n+1$. Then

  * (a)

there are no left-minimal co-occurrences that end before $r_{1}$, i.e., at an
index $k<r_{1}$, and

  * (b)

for each index $k$ where $r_{i}\leq k<r_{i+1}$ for some $i$, the left-minimal
co-occurrence ending at $k$ starts at $\ell_{i}$.

###### Proof.

See Fig. 1 for an illustration of the proof.

  * (a)

If $[j,k]$ is a left-minimal co-occurrence where $k<r_{1}$, it must contain
some minimal co-occurrence that ends before $r_{1}$ — obtainable by shrinking
$[j,k]$ maximally — leading to a contradiction.

  * (b)

Let $r_{i}\leq k<r_{i+1}$. Then $[\ell_{i},k]$ is a co-occurrence since it
contains $[\ell_{i},r_{i}]$. We show that it is left-minimal by showing that
$[\ell_{i}+1,k]$ is not a co-occurrence. If it were, it would contain a
minimal co-occurrence $[s,t]$ where $\ell_{i}<s$ and $t<r_{i+1}$. By Property
1, $\ell_{i}<s$ implies that $r_{i}<t$. However, then $r_{i}<t<r_{i+1}$,
leading to a contradiction.

∎

$S=\hbox
to0.0pt{$\displaystyle\phantom{\cdots}\overbrace{\phantom{\cdot\cdots\circ\cdots\cdot}}^{[j,k]}$\hss}\cdots\cdot\cdots\underbrace{\circ\cdots\cdot\cdots\circ}_{[\ell_{1},r_{1}]}\cdots\cdots\qquad\quad
S=\cdots\cdots\underset{\mathclap{\ell_{i}}}{\circ}\overbrace{\cdot\underbrace{\cdot\cdot\underset{\mathclap{r_{i}}}{\circ}\cdot\cdot}_{[s,t]}\cdot\,\underset{\mathclap{k}}{\circ}}^{(\ell_{1},k]}\cdots\underset{\mathclap{r_{i+1}}}{\circ}\cdots\cdots$
Figure 1: _Left (Lemma 1(a)):_ Any left-minimal co-occurrence $[j,k]$ must
contain a minimal co-occurrence ending at or before $k$. If $k<r_{1}$ this
contradicts that $r_{1}$ is the smallest endpoint of a minimal co-occurrence.
_Right (Lemma 1(b)):_ $[\ell_{i},k]$ is a co-occurrence because it contains
$[\ell_{i},r_{i}]$. However, $[\ell_{i}+1,k]$ is not a co-occurrence; if it
were it would contain a minimal co-occurrence $[s,t]$ that ends between
$r_{i}$ and $k$, leading to a contradiction since $r_{i}<t<r_{i+1}$.

Let $\textsf{len}(i,j)=j-i+1$ denote the length of the interval $[i,j]$. Lemma
1 implies that each minimal co-occurrence $[\ell_{i},r_{i}]$ gives rise to one
additional left-minimal co-occurrence of length $k$ for
$k=\textsf{len}(\ell_{i},r_{i}),\ldots,\textsf{len}(\ell_{i},r_{i+1})-1$.
Also, note that each left-minimal co-occurrence is determined by a minimal co-
occurrence in this manner. Therefore, $\textsf{lmco}(w)$ equals the number of
minimal co-occurrences $[\ell_{i},r_{i}]$ where
$\textsf{len}(\ell_{i},r_{i})\leq w<\textsf{len}(\ell_{i},r_{i+1})$. Recall
that $\delta(i)=\textsf{lmco}(i)-\textsf{lmco}(i-1)$ for $i\in[2,n]$. Since
$\textsf{lmco}(1)=0$ (because $|Q|\geq 2$) we have
$\textsf{lmco}(w)=\sum_{i=2}^{w}\delta(i)$. It follows that

$\delta(w)=\sum_{i=1}^{\mu}\begin{cases}1&\text{if
}\textsf{len}(\ell_{i},r_{i})=w\\\ -1&\text{if
}\textsf{len}(\ell_{i},r_{i+1})=w\\\ 0&\text{otherwise }\end{cases}$

since the contribution of each $[\ell_{i},r_{i}]$ to the sum
$\sum_{i=2}^{w}\delta(i)$ is one if $\textsf{len}(\ell_{i},r_{i})\leq
w<\textsf{len}(\ell_{i},r_{i+1})$ and zero otherwise. We say that
$[\ell_{i},r_{i}]$ _contributes_ plus one and minus one to
$\delta(\textsf{len}(\ell_{i},r_{i}))$ and
$\delta(\textsf{len}(\ell_{i},r_{i+1}))$, respectively.

However, note that only the non-zero $\delta(\cdot)$-entries affect the result
of lmco-queries. Denote the elements of $Z$ by $z_{1}<z_{2}<\ldots<z_{d}$ and
define $\textsf{pred}(w)$ such that $z_{\textsf{pred}(w)}$ is the predecessor
of $w$ in $Z$, or $\textsf{pred}(w)=0$ if $w$ has no predecessor. We get the
following lemma.

######  Lemma 2.

For any $w\in[z_{1},n]$ we have that

$\textsf{lmco}(w)=\sum_{i=1}^{\textsf{pred}(w)}\delta(z_{i})=\textsf{lmco}(z_{\textsf{pred}(w)}).$

For $w\in[0,z_{1})$, $w$ has no predecessor in $Z$ and $\textsf{lmco}(w)=0$.

###### Proof.

The proof follows from the fact that
$\textsf{lmco}(w)=\sum_{i=2}^{w}\delta(i)$ and $\delta(i)=0$ for each
$i\not\in Z$.

∎

###  2.2 Data Structure

The contents of the data structure are as follows. Store the linear space
predecessor structure from [15] over the set $Z$, and for each key $z_{i}\in
Z$ store the data $\textsf{lmco}(z_{i})$. To answer $\textsf{lmco}(w)$, find
the predecessor $z_{\textsf{pred}(w)}$ of $w$ and return
$\textsf{lmco}(z_{\textsf{pred}(w)})$. Return $0$ if $w$ has no predecessor.

The correctness of the query follows from Lemma 2. The query time is
$O(\log\log|U|)$ [15] which is $O(\log\log n)$ since the universe is $[2,n]$,
i.e., the domain of $\delta$. The predecessor structure uses $O(|Z|)=O(d)$
space, which we now show is $O(\sqrt{nq})$. We begin by bounding the
cumulative length of the minimal co-occurrences.

######  Lemma 3.

Let $[\ell_{1},r_{1}],\ldots,[\ell_{\mu},r_{\mu}]$ be the minimal co-
occurrences of $Q$ in $S$. Then

$\sum_{i=1}^{\mu}\textsf{len}(\ell_{i},r_{i})=O(nq).$

###### Proof.

We prove that for each $k\in[1,n]$ there are at most $q$ minimal co-
occurrences $[\ell_{i},r_{i}]$ where $k\in[\ell_{i},r_{i}]$; the statement in
the lemma follows directly. Suppose that there are $q^{\prime}>q$ minimal co-
occurrences $[s_{1},t_{1}],\ldots,[s_{q^{\prime}},t_{q^{\prime}}]$ that
contain $k$ and let $t_{1}<\ldots<t_{q^{\prime}}$. By Property 1, and because
each minimal occurrence contains $k$, we have

$s_{1}<\ldots<s_{q^{\prime}}\leq\;k\;\leq t_{1}<\ldots<t_{q^{\prime}}$

Furthermore, for each $s_{i}$ we have that $S[s_{i}]=p$ for some $p\in Q$;
otherwise $[s_{i}+1,t_{i}]$ would be a co-occurrence and $[s_{i},t_{i}]$ would
not be minimal. Since $q^{\prime}>q$ there is some $p\in Q$ that occurs twice
as the first character, i.e., such that $S[s_{i}]=S[s_{j}]=p$ for some $i<j$.
However, then $[s_{i}+1,t_{i}]$ is a co-occurrence because it still contains
$S[s_{j}]=p$, contradicting that $[s_{i},t_{i}]$ is minimal.

∎

By the definition of $\delta$, we have that $\delta(k)\neq 0$ only if there is
some minimal co-occurrence $[\ell_{i},r_{i}]$ such that either
$\textsf{len}(\ell_{i},r_{i})=k$ or $\textsf{len}(\ell_{i},r_{i+1})=k$. Using
this fact in conjunction with Lemma 3 we bound the sum of the elements in $Z$.

$\displaystyle\sum_{z\in Z}z=\sum_{k\text{ where }\delta(k)\neq 0}k\quad$
$\displaystyle\leq\sum_{i=1}^{\mu}\textsf{len}(\ell_{i},r_{i})+\textsf{len}(\ell_{i},r_{i+1})$
$\displaystyle=\sum_{i=1}^{\mu}\textsf{len}(\ell_{i},r_{i})+\Big{(}\textsf{len}(\ell_{i},r_{i})+\textsf{len}(r_{i}+1,r_{i+1})\Big{)}$
$\displaystyle=\sum_{i=1}^{\mu}2\cdot\textsf{len}(\ell_{i},r_{i})+\sum_{i=1}^{\mu}\textsf{len}(r_{i}+1,r_{i+1})$
$\displaystyle=O(nq)+O(n)$

Since the sum over $Z$ is at most $O(nq)$ we must have $d=O(\sqrt{nq})$,
because with $d=\omega(\sqrt{nq})$ distinct elements in $Z$ we have

$\sum_{z\in Z}z\geq 1+2+\ldots+d=\Omega(d^{2})=\omega(nq).$

##  3 The Co-Occurrence Problem

Recall that $\textsf{co}(w)$ is the number of co-occurrences of length $w$, as
opposed to the number of left-minimal co-occurrences of length $w$. That is,
$\textsf{co}(w)$ counts the number of co-occurrences among the intervals
$[1,w],[2,w+1],\ldots,[n-w+1,n]$. We reduce the co-occurrence problem to the
left-minimal co-occurrence problem as follows.

######  Lemma 4.

Let $S$ be a string over an alphabet $\Sigma$, let $Q\subseteq\Sigma$ and let
lmco be defined as above. Then

$\textsf{co}(w)=\left(\sum_{i=2}^{w}\textsf{lmco}(i)\right)\;-\;\max(w-r_{1},0).$

###### Proof.

For any index $k\geq w$, the length-$w$ interval $[k-w+1,k]$ ending at $k$ is
a co-occurrence if and only if the length of the left-minimal co-occurrence
ending at index $k$ is at most $w$. The sum $\sum_{i=2}^{w}\textsf{lmco}(i)$
counts the number of indices $j\in[1,n]$ such that the left-minimal co-
occurrence ending at $j$ has length at most $w$. However, this also includes
the left-minimal co-occurrences that end at any index $j\in[r_{1},w-1]$. While
all of these have length at most $w-1$, none of the length-$w$ intervals that
end in the range $[r_{1},w-1]$ correspond to substrings of $S$, so they are
not co-occurrences. Therefore, the sum $\sum_{i=2}^{w}\textsf{lmco}(i)$
overestimates $\textsf{co}(w)$ by $w-r_{1}$ if $r_{1}<w$ and by $0$ otherwise.

∎

We show how to represent the sequence
$\sum_{i=2}^{2}\textsf{lmco}(i),\ldots,\sum_{i=2}^{n}\textsf{lmco}(i)$
compactly, in a similar way to what we did for lmco-queries. Recall that the
elements of $Z$ are denoted by $z_{1}<\ldots<z_{d}$, that
$z_{\textsf{pred}(x)}$ is the predecessor of $x$ in $Z$, and that
$\textsf{pred}(x)=0$ if $x$ has no predecessor. Then, for any $w\geq 2$ we get
that

${}\begin{split}\sum_{i=2}^{w}\textsf{lmco}(i)&=\sum_{i=2}^{w}\sum_{j=1}^{\textsf{pred}(i)}\delta(z_{j})\\\
&=\sum_{k=1}^{\textsf{pred}(w)}\delta(z_{k})(w-z_{k}+1)\\\
&=(w+1)\underbrace{\sum_{k=1}^{\textsf{pred}(w)}\delta(z_{k})}_{\textsf{lmco}(w)}-\sum_{k=1}^{\textsf{pred}(w)}z_{k}\delta(z_{k})\end{split}$
(1)

The first step follows by Lemma 2 and the second step follows because
$\delta(z_{k})$ occurs in $\sum_{j=1}^{\textsf{pred}(i)}\delta(z_{j})$ for
each of the $w-z_{k}+1$ choices of $i\in[z_{k},w]$.

To also support co-queries we extend our data structure from before as
follows. For each $z_{k}$ in the predecessor structure we store
$\sum_{i=1}^{k}z_{i}\delta(z_{i})$ in addition to $\textsf{lmco}(z_{k})$. We
also store $r_{1}$. Using Lemma 4 and Equation 1 we can then answer co-queries
with a single predecessor query and a constant amount of extra work, taking
$O(\log\log n)$ time. The space remains $O(d)=O(\sqrt{nq})$. This completes
the proof of Theorem 1(a), as well as the upper bound on space from Theorem
1(c).

##  4 Lower Bounds

In this section we show lower bounds on the space complexity of data
structures that support lmco\- or co-queries. In Section 4.1 we introduce a
gadget that we use in Section 4.2 to prove that any data structure supporting
lmco\- or co-queries needs $\Omega(d)$ space (we use the same gadget in
Appendix B to prove Theorem 2). In Section 4.3 we prove that any solution to
the (left-minimal) co-occurrence problem requires $\Omega(\sqrt{nq})$ bits of
space in the worst case.

All the lower bounds are proven by reduction to the left-minimal co-occurrence
problem. However, they extend to data structures that support co-queries by
the following argument. Store $r_{1}$ and any data structure that supports co
on $S$ and $Q$ in time $t$ per query. Then this data structure supports lmco-
queries in $O(t)$ time, because by Lemma 4 we have that

co $\displaystyle(w)\,-\,\textsf{co}(w-1)$
$\displaystyle=\left(\sum_{i=2}^{w}\textsf{lmco}(i)\;-\;\max(w-r_{1},0)\right)-\left(\sum_{i=2}^{w-1}\textsf{lmco}(i)\;-\;\max(w-1-r_{1},0)\right)$
$\displaystyle=\textsf{lmco}(w)-\max(w-r_{1},0)+\max(w-1-r_{1},0)$

###  4.1 The Increment Gadget

Let $Q=\\{\texttt{A},\texttt{B}\\}$ and $U=\\{2,\ldots,u\\}$. For each $i\in
U$ we define the _increment gadget_

$G_{i}=\underbrace{\texttt{A}\;\texttt{\$}\cdots\texttt{\$}\;\texttt{B}}_{i}\;\underbrace{\texttt{\$}\cdots\texttt{\$}}_{u}$

where $\texttt{\$}\cdots\texttt{\$}$ denotes a sequence of characters that are
not in $Q$.

######  Lemma 5.

Let $Q=\\{\texttt{A},\texttt{B}\\}$, $U=\\{2,\ldots,u\\}$, and let $G_{i}$ be
defined as above. Furthermore, for some
$E=\\{e_{1},e_{2},\ldots,e_{m}\\}\subseteq U$ let $S$ be the concatenation of
$c_{1}>0$ copies of $G_{e_{1}}$, with $c_{2}>0$ copies of $G_{e_{2}}$, and so
on. That is,

$S=\underbrace{G_{e_{1}}\cdots
G_{e_{1}}}_{c_{1}}\;\ldots\ldots\ldots\;\underbrace{G_{e_{m}}\cdots
G_{e_{m}}}_{c_{m}}$

Then $\delta(e_{i})=c_{i}$ for each $e_{i}\in E$ and $\delta(e)=0$ for any
$e\in U\setminus E$. Furthermore, $m\leq d\leq 8m$ and $n\leq 2uC$ where
$C=\sum_{i=1}^{m}c_{i}$ is the number of gadgets in $S$.

###### Proof.

Firstly, $|G_{j}|=j+u\leq 2u$ since $j\in U$, so the combined length of the
$C$ gadgets is at most $2uC$.

Now we prove that $\delta(e_{i})=c_{i}$ for each $e_{i}\in E$ and
$\delta(e)=0$ for each $e\in U\setminus E$. Consider two gadgets $G_{j}$ and
$G_{k}$ that occur next to each other in $S$.

$\overbrace{\underbrace{\texttt{A}\;\texttt{\$}\cdots\texttt{\$}\;\texttt{B}}_{j}\;\underbrace{\texttt{\$}\cdots\texttt{\$}}_{u}}^{G_{j}}\;\overbrace{\underbrace{\texttt{A}\;\texttt{\$}\cdots\texttt{\$}\;\texttt{B}}_{k}\;\underbrace{\texttt{\$}\cdots\texttt{\$}}_{u}}^{G_{k}}$

Three of the minimal co-occurrences in $S$ occur in these two gadgets. Denote
them by $[s_{1},t_{1}]$,$[s_{2},t_{2}]$ and $[s_{3},t_{3}]$.

$\hbox
to0.0pt{$\displaystyle\underbrace{\phantom{\texttt{A}\;\texttt{\$}\cdots\texttt{\$}\;\texttt{B}}}_{[s_{1},t_{1}]}$\hss}\texttt{A}\;\texttt{\$}\cdots\texttt{\$}\;\hbox
to0.0pt{$\displaystyle\overbrace{\phantom{\texttt{B}\;\texttt{\$}\cdots\texttt{\$}\;\texttt{A}}}^{[s_{2},t_{2}]}$\hss}\texttt{B}\;\texttt{\$}\cdots\texttt{\$}\;\underbrace{\texttt{A}\;\texttt{\$}\cdots\texttt{\$}\;\texttt{B}}_{[s_{3},t_{3}]}\;\texttt{\$}\cdots\texttt{\$}$

The two first minimal co-occurrences start in $G_{j}$. They contribute

  * •

plus one to $\delta(x)$ for
$x\in\\{\textsf{len}(s_{1},t_{1}),\textsf{len}(s_{2},t_{2})\\}=\\{j,u+2\\}$.

  * •

minus one to $\delta(x)$ for
$x\in\\{\textsf{len}(s_{1},t_{2}),\textsf{len}(s_{2},t_{3})\\}=\\{j+u+1,k+u+1\\}$.

Hence, each occurrence of $G_{j}$ contributes plus one to $\delta(j)$, and the
remaining contributions are to $\delta(x)$ where $x\not\in U$. The argument is
similar also for the last gadget in $S$ that has no other gadget following it.
For each $e_{i}\in E$ there are $c_{i}$ occurrences of $G_{e_{i}}$ so
$\delta(e_{i})=c_{i}$. For each $e\in U\setminus E$ there are no occurrences
of $G_{e}$ so $\delta(e)=0$.

Finally, note that each occurrence of $G_{j}G_{k}$ at different positions in
$S$ contributes to the same four $\delta(\cdot)$-entries. Therefore the number
of distinct non-zero $\delta(\cdot)$-entries is linear in the number of
distinct pairs $(j,k)$ such that $G_{j}$ and $G_{k}$ occur next to each other
in $S$. Here we have no more than $2m$ distinct paris since $G_{e_{i}}$ is
followed either by $G_{e_{i}}$ or $G_{e_{i+1}}$. Each distinct pair
contributes to at most four $\delta(\cdot)$-entries so $d\leq 8m$. Finally
each $G_{e_{i}}$ contributes at least to $\delta(e_{i})$ so $m\leq d$,
concluding the proof.

∎

###  4.2 Lower Bound on Space

We prove that any data structure supporting lmco-queries needs $\Omega(d)$
space in the worst case. Let $U$ and $Q$ be defined as in the increment gadget
and let $P=p_{2},\ldots,p_{m}$ be a sequence of length $m-1$ where each
$p_{i}\in U$ (the first element is named $p_{2}$ for simplicity). We let $S$
be the concatenation of $p_{2}$ occurrences of $G_{2}$, with $p_{3}$
occurrences of $G_{3}$, and so on. That is,

$S=\underbrace{G_{2}\ldots
G_{2}}_{p_{2}}\;\cdots\cdots\cdots\;\underbrace{G_{m}\ldots G_{m}}_{p_{m}}$

Then any data structure supporting lmco on $S$ and $Q$ is a representation of
$P$; by Lemma 5 we have that $\delta(i)=p_{i}$ for $i\in[2,m]$ and by
definition we have $\delta(i)=\textsf{lmco}(i)-\textsf{lmco}(i-1)$.

The sequence $P$ can be any one of $(u-1)^{m-1}$ distinct sequences, so any
representation of $P$ requires

$\log((u-1)^{m-1})=(m-1)\log(u-1)=\Omega(m\log u)$

bits — or $\Omega(m)$ words — in the worst case. By Lemma 5 this is
$\Omega(d)$.

###  4.3 Lower Bound on Space in Terms of $\boldsymbol{n}$ and
$\boldsymbol{q}$

Here we prove that any data structure supporting lmco needs
$\Omega(\sqrt{nq})$ bits of space in the worst case.

The main idea is as follows. Given an integer $\alpha$ and some
$k\in\\{2,\ldots,\alpha\\}$, let $V$ be the set of _even_ integers from
$\\{k+1,\ldots,k\alpha\\}$, and let $T$ be some subset of $V$. We will
construct an instance $S$ and $Q$ where

  * •

the size of $Q$ is $q=k$

  * •

the length of $S$ is $n=O(k\alpha^{2})$

  * •

for each $i\in V$ we have $\delta(i)=1$ if and only if $i\in T$.

Then, as above, any data structure supporting lmco-queries on $S$ and $Q$ is a
representation of $T$ since $\delta(i)=\textsf{lmco}(i)-\textsf{lmco}(i-1)$.
There are $2^{\Omega(k\alpha)}$ choices for $T$, so any representation of $T$
requires

$\log
2^{\Omega(k\alpha)}=\Omega(k\alpha)=\Omega(\sqrt{k^{2}\alpha^{2}})=\Omega(\sqrt{nq})$

bits in the worst case.

The reduction is as follows. Let
$Q=\\{\texttt{C}_{1},\ldots,\texttt{C}_{k}\\}$ and let $ be a character not in
$Q$. Assume for now that $|T|$ is a multiple of $k-1$ and partition $T$
arbitrarily into $t=O(\alpha)$ sets $T_{1},\ldots,T_{t}$, each of size $k-1$.
Consider $T_{j}=\\{e_{1},\ldots,e_{k-1}\\}$ where
$e_{1}<e_{2}<\ldots<e_{k-1}$. We encode $T_{j}$ in the gadget $R_{j}$ where

  * •

the length of $R_{j}$ is $3k\alpha$.

  * •

$R_{j}[1,k]=\texttt{C}_{1}\texttt{C}_{2}\ldots\texttt{C}_{k}$.

  * •

$R_{j}[i+e_{i}]=\texttt{C}_{i}$ for each $\texttt{C}_{i}$ except
$\texttt{C}_{k}$. This is always possible since $i+e_{i}<(i+1)+e_{i+1}$.

  * •

all other characters are $.

$\underset{1}{\texttt{C}_{1}}\;\underset{2}{\texttt{C}_{2}}\;\ldots\;\underset{k}{\texttt{C}_{k}}\;\texttt{\$}\cdots\texttt{\$}\;\underset{\mathclap{1+e_{1}}}{\texttt{C}_{1}}\;\texttt{\$}\cdots\texttt{\$}\;\ldots\ldots\ldots\;\texttt{\$}\cdots\texttt{\$}\;\underset{\mathclap{k-1+e_{k-1}}}{\texttt{C}_{k-1}}\overbrace{\texttt{\$}\cdots\cdots\cdots\texttt{\$}}^{\geq
k\alpha}$

$\hbox
to0.0pt{$\displaystyle\underbrace{\phantom{\texttt{C}_{1}\;\texttt{C}_{2}\;\ldots\;\texttt{C}_{k}}}_{[s_{1},t_{1}]}$\hss}\texttt{C}_{1}\;\hbox
to0.0pt{$\displaystyle\overbrace{\phantom{\texttt{C}_{2}\;\ldots\;\texttt{C}_{k}\;\texttt{\$}\cdots\texttt{\$}\;\texttt{C}_{1}}}^{[s_{2},t_{2}]}$\hss}\texttt{C}_{2}\;\ldots\;\underbrace{\underset{\phantom{a}}{\texttt{C}_{k}}\;\texttt{\$}\cdots\texttt{\$}\;\texttt{C}_{1}\;\texttt{\$}\cdots\texttt{\$}\;\ldots\ldots\ldots\;\texttt{\$}\cdots\texttt{\$}\;\texttt{C}_{k-1}}_{[s_{k},t_{k}]}\texttt{\$}\cdots\cdots\cdots\texttt{\$}$

Figure 2: _Top:_ Shows the layout of the gadget $R_{j}$, where
$\texttt{\$}\cdots\texttt{\$}$ denotes a sequence of characters not in $Q$.
The first $k$ characters are $\texttt{C}_{1}\ldots\texttt{C}_{k}$. For
$i\in[1,k-1]$ there is another occurrence of $\texttt{C}_{i}$ at index
$i+e_{i}$. Note that the second occurrence of $\texttt{C}_{1}$ occurs before
the second occurrence of $\texttt{C}_{2}$, and so on. All other characters are
$. Since $|R_{j}|=3k\alpha$ and $k-1+e_{k-1}\leq 2k\alpha$, $R_{j}$ ends with
at least $k\alpha$ characters that are not in $Q$. _Bottom:_ Shows the $k$
minimal co-occurrences in $R_{j}$ denoted by
$[s_{1},t_{1}],\ldots,[s_{k},t_{k}]$. Each of the $k-3$ minimal co-occurrences
that are not depicted start at the first occurrence of some $\texttt{C}_{i}$
and ends at the second occurrence of $\texttt{C}_{i-1}$.

See Fig. 2 for an illustration both of the layout of $R_{j}$ and of the
minimal co-occurrences contained within it. There are $k$ minimal co-
occurrences contained in $R_{j}$ which we denote by
$[s_{1},t_{1}],\ldots,[s_{k},t_{k}]$.

  * •

The first one, $[s_{1},t_{1}]=[1,k]$, starts and ends at the first occurrence
of $\texttt{C}_{1}$ and $\texttt{C}_{k}$, respectively.

  * •

For each $i\in[2,k]$, the minimal co-occurrence $[s_{i},t_{i}]$ starts at the
first occurrence of $\texttt{C}_{i}$ and ends at the second occurrence of
$\texttt{C}_{i-1}$, i.e., $[s_{i},t_{i}]=[i,i-1+e_{i-1}]$.

Consider how these minimal co-occurrences contribute to $\delta$. Each
$[s_{i},t_{i}]$ contributes plus one to $\delta(\textsf{len}(s_{i},t_{i}))$.
For the first co-occurrence, $\textsf{len}(s_{1},t_{1})=k$ (which is not a
part of the universe $V$). Each of the other co-occurrences $[s_{i},t_{i}]$
has length

$\textsf{len}(s_{i},t_{i})\;=\;t_{i}-s_{i}+1\;=\;(i-1+e_{i-1})-i+1\;=\;e_{i-1}$

Therefore, the remaining minimal co-occurrences contribute plus one to of each
the $\delta(\cdot)$-entries $e_{1},\ldots,e_{k-1}$.

Furthermore, each $[s_{i},t_{i}]$ contributes negative one to
$\delta(\textsf{len}(s_{i},t_{i+1}))$, where we define $t_{k+1}=|R_{j}|+1$.
For $i<k$ we have that
$\textsf{len}(s_{i},t_{i+1})=1+\textsf{len}(s_{i+1},t_{i+1})=1+e_{i}$ since
$s_{i}+1=s_{i+1}$. Note that $1+e_{i}$ is odd since $e_{i}$ is even, and
therefore not in $V$. For $i=k$, we get that $t_{i+1}=t_{k+1}=|R_{j}|+1$. The
last $k\alpha$ (at least) characters of $R_{j}$ are not in $Q$, so
$\textsf{len}(s_{k},|R_{j}|+1)>k\alpha$ and therefore not in $V$.

Hence, $R_{j}$ contributes plus one to $\delta(e_{1}),\ldots,\delta(e_{k-1})$
and does not contribute anything to $\delta(i)$ for any other $i\in V\setminus
T_{j}$. To construct $S$, concatenate $R_{1},\ldots,R_{t}$. Note that any
minimal co-occurrence that crosses the boundary between two gadgets will only
contribute to $\delta(i)$ for $i>k\alpha$ due to the trailing characters of
each gadget that are not in $Q$. Since $S$ consists of $t=O(\alpha)$ gadgets
that each have length $O(k\alpha)$, we have $n=O(k\alpha^{2})$ as stated
above.

Finally, note that the assumption that $|T|$ is a multiple of $k-1$ is not
necessary. We ensure that the size is a multiple of $k-1$ by adding at most
$k-2$ _even_ integers from $\\{k\alpha+1,\ldots,2k\alpha\\}$ and adjusting the
size of the gadgets accordingly. The reduction still works because we add even
integers, the size of $S$ is asymptotically unchanged, and any minimal co-
occurrence due to the extra elements will have length greater than $k\alpha$
and will not contribute to any relevant $\delta$-entries.

#### Acknowledgements

We would like to thank the anonymous reviewers for their comments, which
improved the presentation of the paper.

##  Appendix A Preprocessing

#### Finding Minimal Co-Occurrences

To build the data structure, we need to find all the minimal co-occurrences in
order to determine $\delta$. For $j\geq r_{1}$, let $\textsf{lm}(j)$ denote
the length of the left-minimal co-occurrence ending at index $j$. By Lemma 1,
$\textsf{lm}(r_{i})=\textsf{len}(\ell_{i},r_{i})$ for each $i\in[1,\mu]$.
Furthermore, for $j\in[r_{i}+1,r_{i+1}-1]$ we have
$\textsf{lm}(j)=\textsf{lm}(j-1)+1$ since both of the left-minimal co-
occurrences ending at these two indices start at $\ell_{i}$. However,
$\textsf{lm}(r_{i})\leq\textsf{lm}(r_{i}-1)$ for each $i\in[2,\mu]$; the left-
minimal co-occurrence ending at $r_{i}$ starts at least one index further to
the right than the left-minimal co-occurrence ending at $r_{i}-1$ because
$\ell_{i-1}<\ell_{i}$, so it cannot be strictly longer.

We determine $\ell_{1},\ldots,\ell_{\mu}$ and $r_{1},\ldots,r_{\mu}$ using the
following algorithm. Traverse $S$ and maintain $\textsf{lm}(j)$ for the
current index $j$. Whenever $\textsf{lm}(j)\neq\textsf{lm}(j-1)+1$ the
interval $[j-\textsf{lm}(j)+1,\;j]$ is one of the minimal co-occurrences. Note
that this algorithm finds the minimal co-occurrences in order by their
rightmost endpoint. We maintain $\textsf{lm}(j)$ as follows. For each
character $p\in Q$ let $\textsf{dist}(j,p)$ be the distance to the closest
occurrence of $p$ on the left of $j$. Then $\textsf{lm}(j)$ is the maximum
$\textsf{dist}(j,\cdot)$-value. As in [14], we maintain the
$\textsf{dist}(j,\cdot)$-values in a linked list that is dynamically reordered
according to the well-known _move-to-front_ rule. The algorithm works as
follows. Maintain a linked list over the elements in $Q$, ordered by
increasing dist-values. Whenever you see some $p\in Q$, access its node in
expected constant time through a dictionary and move it to the front of the
list. The least recently seen $p\in Q$ (i.e., the $p$ with the largest
$\textsf{dist}(j,\cdot)$-value) is found at the back of the list in constant
time. The algorithm uses $O(q)$ space and expected constant time per character
in $S$, thus it runs in expected $O(n)$ time.

#### Building the Data Structure

We build the data structure as follows. Traverse $S$ and maintain the two most
recently seen minimal co-occurrences using the algorithm above. We maintain
the non-zero $\delta(\cdot)$-values in a dictionary $D$ that is implemented
using chained hashing in conjunction with universal hashing [2]. When we find
a new minimal co-occurrence $[\ell_{i+1},r_{i+1}]$ we increment
$D[\textsf{len}(\ell_{i},r_{i})]$ and decrement
$D[\textsf{len}(\ell_{i},r_{i+1})]$. Recall that $Z=\\{z_{1},\ldots,z_{d}\\}$
where $z_{j}<z_{j+1}$ is defined such that $\delta(i)\neq 0$ if and only if
$i\in Z$. After processing $S$ the dictionary $D$ encodes the set
$\\{(z_{1},\delta(z_{1})),\ldots,(z_{d},\delta(z_{d}))\\}$. Sort the set to
obtain the array $E[j]=\delta(z_{j})$. Compute the partial sum array over $E$,
i.e the array

$F[j]=\sum_{i=1}^{j}E[i]=\sum_{i=1}^{j}\delta(z_{i})=\textsf{lmco}(z_{j}).\qquad\qquad\qquad\text{(we
use $1$-indexing)}$

Build the predecessor data structure over $Z$ and associate
$\textsf{lmco}(z_{j})$ with each key $z_{j}$.

The algorithm for finding the minimal co-occurrences uses $O(q)$ space and the
remaining data structures all use $O(d)$ space, for a total of $O(d+q)$ space.
Finding the minimal co-occurrences and maintaining $D$ takes $O(n)$ expected
time, and so does building the predecessor structure from the sorted input.

Furthermore, we use the following sorting algorithm to sort the $d$ entries in
$D$ with $O(d)$ extra space in expected $O(n)$ time. If $d<n/\log n$ we use
merge sort which uses $O(d)$ extra space and runs in $O(d\log d)=O(n)$ time.
If $d\geq n/\log n$ we use radix sort with base $\sqrt{n}$, which uses
$O(\sqrt{n})$ extra space and $O(n)$ time. To elaborate, assume without loss
of generality that $2k$ bits are necessary to represent $n$. We first
distribute the elements into $2^{k}=O(\sqrt{n})$ buckets according to the most
significant $k$ bits of their binary representation, partially sorting the
input. We then sort each bucket by distributing the elements in that bucket
according to the _least_ significant $k$ bits of their binary representation,
fully sorting the input. The algorithm runs in $O(n)$ time and uses
$O(\sqrt{n})=O(n/\log n)=O(d)$ extra space.

##  Appendix B Lower Bound on Time

We now prove Theorem 2 by the following reduction from the predecessor
problem. Let $U$, $Q$ and $G_{i}$ be as defined in Section 4.1 and let
$X=\\{x_{1},x_{2},\ldots,x_{m}\\}\subseteq U$ where $x_{1}<\ldots<x_{m}$.
Define

$S=\underbrace{G_{x_{1}}\cdots G_{x_{1}}}_{x_{1}}\;\underbrace{G_{x_{2}}\cdots
G_{x_{2}}}_{x_{2}-x_{1}}\;\ldots\ldots\ldots\;\underbrace{G_{x_{m}}\cdots
G_{x_{m}}}_{x_{m}-x_{m-1}}$

By Lemma 5 we have that $\delta(x_{1})=x_{1}$, $\delta(x_{i})=x_{i}-x_{i-1}$
for $i\in[2,m]$ and $\delta(i)=0$ for $i\in U\setminus X$. Then, if the
predecessor of some $x\in U$ is $x_{p}$, we have

$\textsf{lmco}(x)=\sum_{i=2}^{x}\delta(i)=x_{1}+(x_{2}-x_{1})+\ldots+(x_{p}-x_{p-1})=x_{p}$

On the other hand, if $x<x_{1}$ then $\sum_{i=0}^{x}\delta(i)=0$,
unambiguously identifying that $x$ has no predecessor.

Applying Lemma 5 again, we have $d\leq 8m$. Furthermore, there are
$x_{1}+(x_{2}-x_{1})+\ldots+(x_{m}-x_{m-1})=x_{m}\leq u$ gadgets in total so
$n\leq 2u^{2}$. Hence, given a data structure that supports lmco in
$f_{t}(n,q,d)$ time using $f_{s}(n,q,d)$ space, we get a data structure
supporting predecessor queries on $X$ in $O(f_{t}(2u^{2},2,8m))$ time and
$O(f_{s}(2u^{2},2,8m))$ space, proving Theorem 2.

## References

  * [1] Daichi Amagata and Takahiro Hara.  Mining top-$k$ co-occurrence patterns across multiple streams (extended abstract).  In Proc. 34th ICDE, pages 1747–1748, 2018.
  * [2] Larry Carter and Mark N. Wegman.  Universal classes of hash functions.  J. Comput. Syst. Sci., 18(2):143–154, 1979.
  * [3] Joong Hyuk Chang and Won Suk Lee.  Finding recently frequent itemsets adaptively over online transactional data streams.  Inf. Syst., 31(8):849–869, 2006.
  * [4] Michele Dallachiesa and Themis Palpanas.  Identifying streaming frequent items in ad hoc time windows.  Data Knowl. Eng., 87:66–90, 2013.
  * [5] Gautam Das, Rudolf Fleischer, Leszek Gasieniec, Dimitrios Gunopulos, and Juha Kärkkäinen.  Episode matching.  In Proc. 8th CPM, pages 12–27, 1997.
  * [6] Erik D. Demaine, Alejandro López-Ortiz, and J. Ian Munro.  Frequency estimation of internet packet streams with limited space.  In Proc. 10th ESA, pages 348–360, 2002.
  * [7] Lukasz Golab, David DeHaan, Erik D. Demaine, Alejandro López-Ortiz, and J. Ian Munro.  Identifying frequent items in sliding windows over on-line packet streams.  In Proc. 3rd ACM IMC, pages 173–178, 2003.
  * [8] Richard M. Karp, Scott Shenker, and Christos H. Papadimitriou.  A simple algorithm for finding frequent elements in streams and bags.  ACM Trans. Database Syst., 28:51–55, 2003.
  * [9] Hua-Fu Li and Suh-Yin Lee.  Mining frequent itemsets over data streams using efficient window sliding techniques.  Expert Syst. Appl., 36(2):1466–1477, 2009.
  * [10] Yongsub Lim, Jihoon Choi, and U Kang.  Fast, accurate, and space-efficient tracking of time-weighted frequent items from data streams.  In Proc. 23rd CIKM, pages 1109–1118, 2014.
  * [11] Chih-Hsiang Lin, Ding-Ying Chiu, Yi-Hung Wu, and Arbee L. P. Chen.  Mining frequent itemsets from data streams with a time-sensitive sliding window.  In Proc. 5th SDM, pages 68–79, 2005.
  * [12] Barzan Mozafari, Hetal Thakkar, and Carlo Zaniolo.  Verifying and mining frequent patterns from large windows over data streams.  In Proc. 24th ICDE, pages 179–188, 2008.
  * [13] Mihai Patrascu and Mikkel Thorup.  Randomization does not help searching predecessors.  In Proc. 18th SODA, pages 555–564, 2007.
  * [14] Joshua Sobel, Noah Bertram, Chen Ding, Fatemeh Nargesian, and Daniel Gildea.  AWLCO: all-window length co-occurrence.  In Proc. 32nd CPM, LIPIcs, pages 24:1–24:21, 2021.
  * [15] Dan E. Willard.  Log-logarithmic worst-case range queries are possible in space $\Theta(N)$.  Inf. Process. Lett., 17(2):81–84, 1983.
  * [16] Ziqiang Yu, Xiaohui Yu, Yang Liu, Wenzhu Li, and Jian Pei.  Mining frequent co-occurrence patterns across multiple data streams.  In Proc. 1th EDBT, pages 73–84, 2015.


In Category theory (Gummersbach, 1981), volume 962 of Lecture Notes in Math., pages 282–291. Springer, Berlin, 1982.

[53]
Thomas Streicher.
Universes in toposes.
In From sets and types to topology and analysis, volume 48 of
Oxford Logic Guides, pages 78–90. Oxford Univ. Press, Oxford, 2005.

[54]
Andrew Swan and Taichi Uemura.
On Church's thesis in cubical assemblies.
arXiv:1905.03014, 2019.

[55]
R. W. Thomason.
Cat as a closed model category.
Cahiers Topologie Géom. Différentielle, 21(3):305–324,

[56]
Taichi Uemura.
Cubical assemblies, a univalent and impredicative universe and a
failure of propositional resizing.
In Peter Dybjer, José Espírito Santo, and Luís Pinto,
editors, 24th International Conference on Types for Proofs and Programs
(TYPES 2018), volume 130 of Leibniz International Proceedings in
Informatics (LIPIcs), pages 7:1–7:20, Dagstuhl, Germany, 2019. Schloss
Dagstuhl–Leibniz-Zentrum fuer Informatik.

[57]
Univalent Foundations Program.
Homotopy Type Theory: Univalent Foundations of Mathematics.
<http://homotopytypetheory.org/book/>, first edition, 2013.

[58]
Benno van den Berg.
Predicative toposes.
arXiv:1207.0959, 2012.