Asymmetric Streaming Approximate
Pattern Matching

As our first result, we give an efficient algorithm for the approximate pattern matching under the Hamming distance, in the asymmetric streaming model:

By the lower bound for counting ones in a sliding window [10] (see also [9]), any asymmetric streaming algorithm for this problem must use $\mathrm{\Omega }({ϵ}^{-1}{\log }^{2}m)$ bits.

The main idea of our algorithm is to divide the text, for every natural $k\le \log m$, into blocks of varying length but each at a distance roughly $2^k$ from the pattern. For any level $k$ and each of the $\lceil {ϵ}^{-1}\rceil$ latest blocks on this level, we store a sketch which uses $𝒪({ϵ}^{-2}{\log }^{2}n)$ bits and allows to compute $(1+ϵ)$-approximation of the Hamming distance. We then show that if the Hamming distance between $P$ and $T[j-m+1,j]$ is at most ${ϵ}^{-1}{2}^k$, where $T[j]$ is the latest arrived letter of the text, then whole $T[j-m+1,j]$ is covered by the stored blocks on level $k$, and we can use the sketches to compute an approximation of the Hamming distance, with some additive error which is reduced by the chosen parameters.

As our second and main contribution, we show a space-efficient asymmetric streaming algorithm for approximating the edit distances between the pattern and text substrings. Namely, for each position $j$ of the text $T$, we must compute an approximate value of the smallest possible edit distance between $P$ and some substring $T[i,j]$.

Asymmetric query complexity for edit distance was first considered in [3], with free access to one string and the goal of minimising the number of queries for letters in the other string. Saks and Seshadhri [18] furthered this idea and developed the asymmetric streaming model, along with the first asymmetric streaming algorithm for the longest common subsequence problem (LCS). The merged paper of Cheng, Farhadi, Hajiaghayi, Jin, Li, Rubinstein, Seddighin, and Zheng [5] (full versions [11], [6]) revisited the problem of computing the edit distance, and showed that there is (i) a deterministic asymmetric streaming algorithm which computes $𝒪(2^k)$-approximation of the edit distance between two strings using $\widetilde{𝒪}(k{m}^{1/k})$ space and polynomial time, and (ii) $(1+ϵ)$-approximation of the edit distance between two strings using $\widetilde{𝒪}({ϵ}^{-1}\sqrt{n})$ space for any constant $ϵ>0$. Li and Zheng [16] improved the space complexity of the $𝒪(2^k)$-approximation algorithm to $\widetilde{𝒪}(k{d}^{1/k})$, where $d$ is the edit distance between the input strings. They also showed that any asymmetric streaming algorithm (even randomised) computing the edit distance exactly must use $\mathrm{\Omega }(n)$ bits, and that computing the edit distance $(1+ϵ)$-approximately requires $\mathrm{\Omega }({ϵ}^{-1})$ bits.

For the problem of approximate pattern under the edit distance, we show the following:

Therefore, we are able to extend the result of [5] from string-to-string edit distance to approximate pattern matching under the edit distance, in the same space complexity $\widetilde{𝒪}(m^{1/k})$, losing only an additional $ϵ$ factor in the (large) constant-factor approximation.

The structure of our solution for the edit distance is similar to that for the Hamming distance; in particular, we still divide text into blocks, for multiple levels parametrised by distances. However, unlike the Hamming distance, there are no small-space sketches for approximating the edit distance between strings, which is the main source of difficulty. In their solution for string-to-string edit distance computation, [5] suggested approximating the blocks of the text with the closest substrings of the pattern (to which we have constant-time random access). We extend their techniques to pattern matching. There are some challenges in this approach: first, [5] works with a static decomposition of a fixed-length string, while we must maintain the decomposition for appropriate suffixes of the streamed longer text. To this end, we maintain a number of the latest static blocks in a queue, but then a substring $T[i,j]$, where $j$ is the latest arrived letter of the text, is rarely fully aligned with the chosen blocks. The first and last blocks need to be trimmed, introducing a small additive error, which nevertheless can be transformed into a multiplicative one.

Our results lead to intriguing open problems. First, what is the best time complexity one can achieve for approximate pattern matching under the Hamming distance while using polylogarithmic space? Ideally, the time per letter of the text would also be polylogarithmic, but in our solution complexity is dominated by computing distances to all substrings of given length, which takes quadratic time per letter due to sketch properties. Second, can pattern matching under the Hamming distance be solved with a deterministic algorithm more efficiently than under the edit distance? Our space-efficient algorithm uses randomised sketches.

For the pattern matching with edits, can we achieve $(1+ϵ)$-approximation in $\widetilde{𝒪}({ϵ}^{-1})$ space? Note that even for only string-to-string edit distance, the best existing solution takes $\widetilde{𝒪}({ϵ}^{-1}\sqrt{n})$ bits, so the first step would be to match this for pattern matching. Finally, can randomisation help to achieve a better space or time complexity for the edit distance? The time complexity of known deterministic algorithms is large.

The above follows from the fact that $Q$ holds up to $r$ latest blocks, and each block is an approximation of some $T[q_1,q_2]$ at distance from $P$ exceeding $r$.

Assume $\mathrm{ED}(P,T[i,j])\le r^2=m$, and $i$ is not covered by $Q$, thus the queue must be full. For the $k$-th block in $Q$ for $k\in [1,r]$, denote that it stores $P[a_k,a_k^{\prime }]$ as an approximation of $T[b_k,b_{k+1})$. As $i$ is not covered, we have $b_1>i$. By Proposition 6, consider a partition of $P=P_0\circ P_1\circ \mathrm{\dots }\circ P_{r+1}$ such that $\mathrm{ED}(P,T[i,j])=\mathrm{ED}(P_0,T[i,b_1))+{\sum }_{k=1}^r\mathrm{ED}(P_k,T[b_k,b_{k+1}))+\mathrm{ED}(P_{r+1},T[b_{r+1},j])$. By definition of blocks stored in $Q$, they are at distance larger than $r$ from $P$, so for any $k$ $\mathrm{ED}(P_k,T[b_k,b_{k+1}))>r$. But this contradicts $\mathrm{ED}(P,T[i,j])\le r^2=m$, as there are $r$ blocks at a distance larger than $r$. $◀$

It remains to bound the approximation we can obtain using the queue. For some index $i$, assume that $\mathrm{ED}(P,T[i,j])\le m$, with the last processed index of $T$ being $j$. By Proposition 12, $T[i,j]$ is covered by $Q$. We consider a string $T^{\prime }$ constructed as follows, in order to approximate $T[i,j]$ (which is not stored explicitly) with blocks from the queue.

Let $B=[1,b]$ be a block in $Q$ being approximation of $T[q_1,q_2]$ with $q_1\le i$ and maximal $q_1$. Recall $B$ is a substring of $P$. Set $T^{\prime }=B(i-q_1,b]$, as $B$ is an approximate block for a substring of $T$ extending too far to the left of $i$. Since we are interested in the edit distance to just $T[i,q_2]$, we drop a prefix of $B$ of length $i-q_1$, using the fact that removing the first letters from two strings does not increase the edit distance between them. That is, $\mathrm{ED}(S_1,S_2)\ge \mathrm{ED}(S_1[q,|S_1|],S_2[q,|S_2|])$, for any . Note that we need to know $q_1$, but it can be stored for any approximate block without affecting space complexity (we omit this detail in the pseudocode).

Then, append to $T^{\prime }$ all blocks following $B$ in the queue, and finally append the suffix of $T$ which is still being processed by the queue procedure. Let $D_l$ be an additive value for the $l$-th concatenated full approximate block, and $D=\sum D_l$. See Figure 3.

We do not build $T^{\prime }$ explicitly, as it can be much more than $r$ letters. It is just represented as a sequence of indices to the read-only pattern, and for the unprocessed suffix, additionally a list of edit operations and a buffer of the most recent letters. Next, we show that $T^{\prime }$ can be used to approximate distance between $T[i,j]$ and arbitrary substring of the pattern:

Recall that $B=[1,b]$ is a block in $Q$ being approximation of $T[q_1,q_2]$ with $q_1\le i$ and maximal $q_1$. Let $i_1,i_2,\mathrm{\dots },i_{z+1}$ be the sequence of indices such that $l$-th block $B_l$ in $Q$ after initial block $B$ is an approximation of $T[i_l,i_{l+1})$. Note that:

By Proposition 6, $P^{\ast }$ can be partitioned into consecutive substrings $P_0,\mathrm{\dots },P_{z+1}$ such that $\mathrm{ED}(P^{\ast },T[i,j])=\mathrm{ED}(P_0,T[i,i_1))+{\sum }_{l=1}^z\mathrm{ED}(P_l,T[i_l,i_{l+1}))+\mathrm{ED}(P_{z+1},T[i_{z+1},j])$. Note this is not necessarily a partition optimal for computing $\mathrm{ED}(P^{\ast },T^{\prime })$ with selected blocks.

We have $\mathrm{ED}(T[i,i_1),B(i-q_1,b])\le 2r$, which means that:

for any string $S$, by the triangle inequality. We cannot claim 3-approximation here, as $B(i-q_1,b]$ is not the closest substring of $T[i,i_1)$, but only a trimmed closest substring of $T[q_1,q_2]$, which was at distance at most $2r$.

Moreover, from definition of 3-approximate blocks, for any $l$ it holds that $\mathrm{ED}(P_l,T[i_l,i_{l+1}))\le \mathrm{ED}(P_l,B_l)+D_l\le 3\mathrm{E}\mathrm{D}(P_l,T[i_l,i_{l+1}))$. We want to avoid guessing the optimal partition of $P^{\ast }$ necessary for block-by-block computation, so instead need to tie $\mathrm{ED}(P^{\ast },T^{\prime })$, relatively easy to compute, to $\mathrm{ED}(P^{\ast },T[i,j])=d$. The algorithm will return value $\mathrm{ED}(P^{\ast },T^{\prime })+2r+D$. As an upper bound for this estimate of $d$, we get:

(3) holds as we partition $P^{\ast }$ into $P_0,P_1,\mathrm{\dots }$, and $T^{\prime }$ into blocks. (4) is by using (1) and the blocks being 3-approximate. (5) follows just by the chosen partition of $P^{\ast }$ optimal for computing $\mathrm{ED}(P^{\ast },T[i,j])$. $\mathrm{⊲}$

To obtain a lower bound for the returned estimate, let us consider another partition of $P^{\ast }$ into $z+2$ consecutive substrings $P_0^{\prime },\mathrm{\dots },P_{z+1}^{\prime }$ such that $\mathrm{ED}(P^{\ast },T^{\prime })=\mathrm{ED}(P_0^{\prime },B(i-q_1,b])+{\sum }_{l=1}^z\mathrm{ED}(P_l^{\prime },B_l)+\mathrm{ED}(P_{z+1}^{\prime },T[i_{z+1},j])$.

(6) follows from $P_0^{\prime },P_1^{\prime },\mathrm{\dots }$ being a partition of $P^{\ast }$. (7) is by using (1) and the blocks being 3-approximate. (8) holds by the chosen partition of $P^{\ast }$ optimal for computing $\mathrm{ED}(P^{\ast },T^{\prime })$. $\mathrm{⊲}$

By Claims 14 and 15, $d\le \mathrm{ED}(P^{\ast },T^{\prime })+2r+D\le 3d+4r$. The algorithm can compute $(1+ϵ)$-approximation of $\mathrm{ED}(P^{\ast },T^{\prime })$, using Fact 9, as we have access to all letters of $T^{\prime }$. $2r+D$ is known to the algorithm. $◀$

By Lemma 13, for any constant $ϵ$ we can compute $(3+ϵ)$-approximation of $\mathrm{ED}(P^{\ast },T[i,j])$ but with an additive factor $𝒪(r)$. To get rid of it, we create an additional queue $Q_0$ storing blocks at a constant distance from $P$, augmented with the full list of edit operations transforming a substring of $P$ into a substring of $T$; so these are in fact not approximate blocks, but provide exact access to substrings of $T$. This can be done by a variant of Algorithm 1, replacing the inequality in line 7 with instead of , and additionally reading only a single letter into the buffer. This ensures that the distance of a block from $P$ is always 1. $Q_0$ stores up to $r\log m$ augmented blocks, and we have that:

This allows us to compute the edit distance exactly for suffixes of $T$ close to the pattern. Otherwise, we can assume that $\mathrm{ED}(P,T[i,j])=d\ge r\log m$. By Lemma 13 and Proposition 12, we can obtain estimate $w$ such that . As $1/\log m=o(1)$, Algorithm 2 can compute $(3+ϵ)$-approximation of ${\min }_i\mathrm{ED}(T[i,j],P)$ for any constant $ϵ$, for $m$ large enough.

The total space used by the algorithm is $𝒪(m^{1/2}{\log }^{2}m)$ bits, as $Q_0$ uses $𝒪(r{\log }^{2}m)$ bits for storing blocks and lists of edit operations. $Q$ uses a smaller number of $𝒪(r\log m)$ bits to store the blocks and one list of edit operations for the unfinished block. $𝒪(r\log m)$ bits is also enough to compute this list of edit operations by Proposition 11. Using Fact 9 requires asymptotically fewer bits. This finishes the proof of Theorem 10.

Let $P^{\ast }$ be any substring of $P$, by assumption $\mathrm{ED}(P^{\ast },T[i,j])\ge d$. $\mathrm{ED}(P^{\ast },T[i,j])\le v+\mathrm{ED}(P^{\ast },P^{\prime })$ by the triangle inequality. On the other hand, $v+\mathrm{ED}(P^{\ast },P^{\prime })\le v+\mathrm{ED}(P^{\ast },T[i,j])+ED(P^{\prime },T[i,j])\le 2v+\mathrm{ED}(P^{\ast },T[i,j])\le (2g+1)\mathrm{ED}(P^{\ast },T[i,j])$. $◀$

For an integer $k$, set $r=m^{1/k}$ as roughly the space complexity we are aiming for. We assume $r$ is a power of two, otherwise we can take the largest power of two smaller than $m^{1/k}$. The algorithm maintains the set of queues $Q_t$ for $t\in [0,k)$, each queue holding up to $r\log m$ approximate blocks (assume $\log m$ is an integer). The index $t$ is called a level of the queue $Q_t$. We will be using Fact 9 with some small constant ${ϵ}^{\prime }$ to be specified later.

The base of the algorithm is formed by $Q_0$, constructed exactly as in the previous section, and providing access to the suffix of the streamed text which is very close to the pattern. The queues on further levels cannot be constructed in the same manner, since we do not want to maintain in a buffer a suffix of $T$ which is at a distance larger than $r$ from $P$. Instead, we will maintain $Q_t$ using $Q_{t-1}$, so there are $k$ steps in the inductive structure. $Q_1$ could also be built directly, but not any of the further queues, so we choose not to distinguish $Q_1$. We construct queues with the following properties:

Let $A_t=q^t(2^{t+1}-1)$. We will proceed by induction on levels. As in Lemma 13, $Q_t$ can be used to compute distance to any substring of $P$. For some long suffix of $T$ we possibly can no longer compute the closest substring in $P$, but still can obtain an approximate closest substring, compounding the approximation factor for each consecutive level, by Proposition 17. This is described in Algorithm 3; $Q_0$ works as in the previous section.

For the ease of presentation, in the pseudocode each queue moves the current index $j$ in $T$, while in fact this process should be synchronised between all queues processing the next letter from the stream, starting from level 0. The details of the algorithm in lines 5 or 9 are described below. A temporary block $temp{B}_t$ is a substring of $P$ with the smallest approximate distance to the current suffix of $T$ on level $t$; only in $Q_0$ we could afford direct access to this suffix. As previously, we create a new full block only when the (approximate) distance from $P$ exceeds some threshold.

We need to inductively bound the approximation factor, as in the lemma statement. All properties hold for the base of $t=0$, so assume they hold for $t$ and consider $Q_{t+1}$. $Q_{t+1}$ is constructing blocks using $Q_t$ and its $A_t$-approximate blocks. Let the current suffix be $T[i,j]$, meaning the last block in $Q_{t+1}$ ended at $i-1$ and the current index is $j$, and consider any substring $P^{\ast }$ of the pattern.

The algorithm can approximate $\mathrm{ED}(P^{\ast },T[i,j])=d$ as follows, similarly to Lemma 13. Let $B[1,b]$ be a block in $Q_t$ being approximation of $T[q_1,q_2]$ with $q_1\le i$ and maximal $q_1$. Such a block exists since $i$ is covered by $Q_t$, and recall that $B$ is a substring of $P$. Set $T^{\prime }=B(i-q_1,b]$, as $B$ is an approximate block for a substring of $T$ extending too far to the left. Then, append to $T^{\prime }$ all blocks following $B$ from $Q_t$, and finally append $temp{B}_t$, the temporary block approximating the suffix which is still being processed by the queue procedure in $Q_t$. Again, $T^{\prime }$ is not built explicitly, but as it is a concatenation of fragments of $P$, we can access any of its letters. Let $D_l$ be the additive value for the $l$-th concatenated full approximate block $B_l$, and $D={\sum }_{l=1}^z{D}_l$. Let $i_1,i_2,\mathrm{\dots },i_{z+1}$ be the sequence of indices such that the $l$-th block in the $Q_t$ after $B$ is an approximation of $T[i_l,i_{l+1})$.

Recall $A_t=q^t(2^{t+1}-1)$ is the approximation ratio of blocks in $Q_t$. By Proposition 6, $P^{\ast }$ can be partitioned into $z+2$ consecutive substrings $P_0,P_1,\mathrm{\dots },P_{z+1}$ such that $d=\mathrm{ED}(P_0,T[i,i_1))+{\sum }_{l=1}^z\mathrm{ED}(P_l,T[i_l,i_{l+1}))+\mathrm{ED}(P_{z+1},T[i_{z+1},j])$. From the second property of $Q_t$ we have $\mathrm{ED}(T[i,i_1),B(i-q_1,b])\le 2r^t{A}_t$, thus by the triangle inequality for any string $S$ it holds that:

For any $l$, $\mathrm{ED}(P_l,T[i_l,i_{l+1}))\le \mathrm{ED}(P_l,B_l)+D_l\le A_t\mathrm{ED}(P_l,T[i_l,i_{l+1}))$, by the first property and the definition of approximate blocks. By Line 7 of Algorithm 3, we have that $\mathrm{ED}(temp{B}_t,T[i_{z+1},j])\le 2r^t{A}_t$ is enforced directly, so again for any $S$:

Since the algorithm have no access to $T[i,j]$, it estimates $\mathrm{ED}(P^{\ast },T[i,j])$ with value of $\mathrm{ED}(P^{\ast },T^{\prime })+4r^t{A}_t+D$. We can obtain the following upper bound:

where steps are analogous to those in Lemma 13. To get a lower bound, consider another partition of $P^{\ast }$ into substrings $P_0^{\prime },\mathrm{\dots },P_{z+1}^{\prime }$ with $\mathrm{ED}(P^{\ast },T^{\prime })=\mathrm{ED}(P_0^{\prime },B(i-q_1,b])+{\sum }_{l=1}^z\mathrm{ED}(P_l^{\prime },B_l)+\mathrm{ED}(P_{z+1}^{\prime },temp{B}_t)$. We then have: