Permutation Patterns in Streams

The sequence variant of PPM has been considered in the non-deterministic model by Jelínek, Opler, and Valtr [21], who applied it to the problem of recognizing merges of permutations.

Another important recent line of work that is close to ours studies PPM in a property-testing framework. Here, the input sequence is assumed to either avoid the pattern $\pi$, or be $\epsilon$-far from avoiding $\pi$, i.e., differ in $\epsilon n$ elements from any $\pi$-avoiding sequence. The task is to solve PPM by querying only a sublinear number of elements (with random access). Both adaptive and nonadaptive variants have been studied [27, 5, 6, 28, 34], and other distance models were also considered [17]. The special case of $\pi =21$ is also known as monotonicity testing (see, e.g., Fischer [16]).

Another, more difficult problem related to PPM is pattern counting, where the number of occurrences of $\pi$ in $\tau$ must be determined. In the usual non-streaming setting, fixed-parameter tractability, or even a runtime of the form $n^{o(k/\log k)}$ would contradict standard complexity assumptions [20, 9] but the above exponential runtimes for PPM largely transfer.

Counting smaller concrete patterns is important in non-parametric statistics: Even-Zohar and Leng [15] observed that Kendall’s $\tau$, Spearman’s $\rho$, the Bergsma–Dassios–Yanagimoto test, and Hoeffding’s independence test can be inferred from counting patterns of size 2, 3, 4, and 5, respectively. Accordingly, counting concrete small patterns has been the subject of study in both the exact and approximate sense [15, 14, 7].

Counting the simplest possible pattern $\pi =21$ yields the number of inversions, a natural measure of sortedness of a sequence. In the streaming setting, counting 21 already requires $\mathrm{\Omega }(n)$ space [4], even when the input sequence is a permutation.

Let us repeat the definition of the two problems we study in this paper (we define the model formally in Section 2.1). The first problem, called $\pi$-${\text{PPM}}_n$, consists of determining whether the pattern $\pi$ is contained in an input permutation $\tau$ on $[n]$ that arrives one value at the time. We treat this as a non-uniform problem, that is, an algorithm may hard-code the input size $n$. This makes our lower bounds stronger and simplifies our algorithms somewhat.

The second problem, $\pi$-${\text{SequencePPM}}_n$ is similar, except the input now is a sequence of at most $n$ distinct values out of $[n]$. Our lower bounds still work when the input size $m\le n$ is known to the algorithm, though we do not study all possible combinations of parameters $m,n$.

Note that we can store the whole input using $𝒪(n\log n)$ bits, which is therefore a trivial upper bound for the space complexity. It is also not hard to show the following weak lower bound (Section 4).

We now present our main results. For monotone patterns, a simple modification of the standard longest increasing subsequence algorithm allows us to solve both problems with $𝒪(k\log n)$ bits of space, and we prove that this is tight up to a constant independent of $k$.

We prove Theorem 1.2 in Section 3. For non-monotone patterns, both problems are hard in almost all cases (Section 4). For SequencePPM, we give a short proof using our machinery.³³3Jelínek, Opler, and Valtr [21] gave another proof based on a preliminary version of this paper.

Hardness of PPM (for almost all patterns) is one of our main new results, and significantly harder to prove.

Finally, we show that $\pi$-${\text{PPM}}_n$ can be solved using sublinear space for non-monotone patterns of size three, which implies a separation between SequencePPM and PPM (Section 5).

Note that all bounds are tight up to a $𝒪(\log n)$ factor, except Theorem 1.5, where a $\tilde{\mathrm{\Theta }}(\sqrt{n})$ gap remains. Our lower bounds in Theorems 1.3 and 1.4 extend to a multi-pass variant: When the algorithm can take $p$ passes over the input, we obtain lower bounds of $\mathrm{\Omega }(n/p)$ bits in both cases. Moreover, Theorems 1.3 and 1.4 hold even when randomized or nondeterministic streaming algorithms are allowed (cf. Jelínek, Opler, Valtr [21]).

We conclude the paper with some open questions (Section 6).

We give a direct communication complexity proof. Assume $\pi$ is increaseing, $n$ is even, and $n\ge k^2$. Let Alice have the first half of the input permutation, which will consist of the odd integers in $[n]$, and let Bob have the latter half, containing the even integers of $[n]$. We will construct a set of $2^{\mathrm{\Omega }(k\log n)}$ possible inputs for Alice such that Bob must be able to distinguish between any two of them. This means that Alice has to send $\mathrm{\Omega }(k\log n)$ bits of information, implying the stated lower bound.

Let $\rho =r_1{r}_2\mathrm{\dots }{r}_{k-2}\in {[n]}^{k-2}$ be an increasing sequence of odd integers with $r_1=1$. Observe that there are

such sequences. We claim that we can construct a permutation $\alpha$ for Alice so that $\rho$ describes the state of the algorithm given at the start of the section; that is, we have that $r_i$ is the lowest value that is the last element of an increasing sequence of length $i$. Indeed, let $\alpha$ start with a decreasing sequence of all odd integers not contained in $\rho$, and end with $\rho$.

Now let ${\alpha }_1,{\alpha }_2$ be constructed in this way from distinct integer sequences $\rho =r_1{r}_2\mathrm{\dots }{r}_{k-1}$ and $\sigma =s_1{s}_2\mathrm{\dots }{s}_{k-1}$. We show that there exists a permutation $\beta$ of the even values in $[n]$ so that out of ${\alpha }_1\beta$ and ${\alpha }_2\beta$, exactly one contains $\pi$. That means that Bob, when given $\beta$, must be able to distinguish between ${\alpha }_1$ and ${\alpha }_2$, as desired. (See Figure 1.)

Let $i\in [k-1]$ be minimal such that $r_i\ne s_i$, and assume without loss of generality. Let now $\beta ={\beta }_1{\beta }_2{\beta }_3$ be the following sequence. Start with the decreasing subsequence ${\beta }_1=(n,n-2,\mathrm{\dots },r_i+2(k-i)+1)$, continue with increasing ${\beta }_2=(r_i+1,r_i+3,\mathrm{\dots },r_i+2(k-i)-1)$ and finish with ${\beta }_3=(r_i-1,r_i-3,\mathrm{\dots },2)$. Observe that ${\alpha }_1\beta$ contains an increasing subsequence of length $k$. Indeed, recall that $r_i$ is the last element of an increasing subsequence of length $i$, which can be concatenated with ${\beta }_2$ to obtain one of length $k$.

We finish the proof by arguing that ${\alpha }_2\beta$ does not contain a increasing subsequence of length $k$. Suppose for the sake of contradiction that such a subsequence $\gamma ={\gamma }_1{\gamma }_2$ exists, with ${\gamma }_1$ being part of ${\alpha }_2$ and ${\gamma }_2$ being part of $\beta$. Write $j=|{\gamma }_1|$, so $k-j=|{\gamma }_2|$. The longest increasing subsequence in $\beta$ has length $k-i$, implying $j\ge i$. Further, since the longest increasing subsequence in ${\alpha }_2$ has length $k-2$, we have $k-j\ge 2$.

Note that ${\gamma }_1$ ends with a value at least $s_j\ge s_i+2(j-i)>r_i+1+2(j-i)$, and ${\gamma }_2$ starts with a value at most , which means ${\gamma }_1{\gamma }_2$ is not increasing, a contradiction. $◀$

For patterns of smaller size $k\le 3$, we can still show a $\mathrm{\Omega }(\log n)=\mathrm{\Omega }(k\log n)$ bound. Note that this is easy for $\pi$-${\text{SequencePPM}}_n$, even if $\pi =12$ and the input sequence consists of only two values $x,y$: By a simple adversarial argument, a correct algorithm must be able to distinguish between any two odd values for $x$. For $\pi$-PPM, the proof is a little more involved.

Set $\pi =21$ for now. Let $𝔸$ be a streaming algorithm $𝔸$ for ${\text{PPM}}_n$ with $m$ states. In the following, we show that $m>\frac{n}{4}$, implying that $\log n-2$ bits of space are necessary.

Let $Q=(q_0,q_1,\mathrm{\dots },q_n)$ be the sequence of states $𝔸$ takes when the input is the increasing permutation $12\mathrm{\dots }n$. Observe that states may repeat. However, we claim that pairs of consecutive states must be pairwise distinct. Indeed, suppose we have $q_{i-1}=q_{j-1}$ and $q_i=q_j$ for two distinct $i,j\in [n]$. Then swapping $i$ and $j$ in the input will not change the behavior of $𝔸$, even though the sequence is no longer monotone.

Our claim in particular implies that a state cannot be repeated three times consecutively. However, a state may appear twice consecutively. Construct a new state sequence $Q^{\prime }$ by deleting one element from each of these consecutive appearances. We clearly have $|Q^{\prime }|\ge \frac{1}{2}|Q|=\frac{n+1}{2}$. moreover, $Q^{\prime }$ is a so-called Davenport-Schinzel sequence of order two [2]. It is well known that if such a sequence consists of $m$ distinct symbols (corresponding to states here), then its length is at most $2m-1$. Thus, we have $\frac{n+1}{2}\le 2m-1$, implying that $m>\frac{n}{4}$, as desired.

The case $\pi =321$ reduces to 21 by simply adding the value $n+1$ at the start. The cases $\pi \in \{12,123\}$ are symmetric. $◀$

Overall, since $\pi$-PPM cannot be harder than $\pi$-SequencePPM, we have: See 1.2

Let ${\pi }^{\prime }=\sigma x$; the other case is similar. Take an algorithm $𝔸$ that solves ${\pi }^{\prime }$-${\text{PPM}}_{2n}$ with $f(2n)$ bits of space. We now give an algorithm for $\pi$-${\text{PPM}}_n$. Without loss of generality, assume that ${\pi }^{\prime }(k-1)>{\pi }^{\prime }(k)$.

Let $\tau$ be the input. Compute ${\tau }^{\prime }$ by first taking every value in $\tau$, in order, and doubling it; and then append the sequence $1,3,5,\mathrm{\dots },2n-1$. Observe that ${\tau }^{\prime }$ is a permutation on $[2n]$ and can be constructed one value at the time as $\tau$ arrives, using $𝒪(\log n)$ space. The algorithm for $\pi$-${\text{PPM}}_n$ consists of feeding ${\tau }^{\prime }$ into $𝔸$. The algorithm clearly requires $f(2n)+𝒪(\log n)$ space. We now show correctness.

If $\tau$ contains $\pi$, then clearly ${\tau }^{\prime }$ also contains ${\pi }^{\prime }$. On the other hand, if ${\tau }^{\prime }$ contains ${\pi }^{\prime }$, then either the occurrence of ${\pi }^{\prime }$ is within the first $n$ elements of ${\tau }^{\prime }$ (which implies $\tau$ contains ${\pi }^{\prime }$, and thus $\pi )$, or, since ${\pi }^{\prime }(k-1)>{\pi }^{\prime }(k)$, only the last element of ${\pi }^{\prime }$ is mapped to the second half of ${\tau }^{\prime }$ (which implies that $\tau$ contains $\pi$). Thus, our algorithm is correct.

The proof for SequencePPM is essentially the same. $◀$

It seems likely that the space complexity of ${\pi }^{\prime }$-${\text{SequencePPM}}_n$ and ${\pi }^{\prime }$-${\text{PPM}}_n$ is, in fact, monotone under taking sub-patterns (say, for large enough $n$); however, this seems more difficult to prove and is not needed to show our bounds.

Combining Lemma 4.1 with Lemma 3.3 already yields a $\mathrm{\Omega }(\log n)$ bound for every pattern $\pi$, thus proving Theorem 1.1. We now move on to the lower bound for SequencePPM.

By Lemma 4.1, it suffices to show a lower bound for non-monotone patterns of length 3. We show the stronger lower bound in the multi-pass model, as mentioned in the introduction.

We show that 312-${\text{SequencePPM}}_{3n}$ is 1-${\text{Disj}}_n$ hard, which suffices to prove our claim by Lemmas 2.2, 2.3, and 2.4. Let $(S,T)$ be an input for ${\text{Disj}}_n$. Construct the sequence $f_1(S)$ as follows (see Figure 2). For each $i\in S$, in ascending order, add the values $3i,3i-2$. Further, construct the sequence $g_1(T)$ by adding $3i-1$ for each $i\in T$, in descending order. We now show that $\tau =f_1(S)g_1(T)$ contains 312 if and only if there is some $i\in S\cap T$.

First suppose that $i\in S\cap T$; then $\tau$ contains the subsequence $3i,3i-2,3i-1$, which is an occurrence of 312. Second, suppose $\tau$ contains an occurrence $(a,b,c)$ of 312. Since $g_1(T)$ is descending, we cannot have $b,c\in g_1(T)$, implying $a,b\in f_1(S)$. Since $a>b$, and all descending pairs in $f_1(S)$ are of the form $(3i,3i-2)$, we have $a=3i$ and $b=3i-2$ for some $i\in [n]$, implying $i\in S$. Now we must have $c=3i-1$, which implies that $i\in T$, and we are done. $◀$

We now formally prove the following, which includes Theorem 1.3 as the special case $p=1$.

Observe that for each non-monotone pattern $\pi$ of length at least four, we can remove either the first or last element and the pattern stays non-monotone. Thus, every pattern $\pi$ of length $k\ge 3$ can be reduced to a non-monotone pattern $\rho$ of length 3 in $k-3$ such steps. By Lemma 4.1, if $\pi$-${\text{SequencePPM}}_n$ can be solved with $f(n)$ space and $p$ passes, then $\rho$-${\text{SequencePPM}}_n$ can be solved with $f(2^{k-3}n)+{𝒪}_k(\log n)$ space and $p$ passes. Our claim thus follows from Lemma 4.2. $◀$