Longest Alignment with Edits in Data Streams

arXiv:1711.04367v1 [cs.DS] 12 Nov 2017

Elena Grigorescu∗

Erfan Sadeqi Azer†

Abstract— Analyzing patterns in data streams generated
by network traffic, sensor networks, or satellite feeds is a
challenge for systems in which the available storage is limited.
In addition, real data is noisy, which makes designing data
stream algorithms even more challenging.
Motivated by such challenges, we study algorithms for
detecting the similarity of two data streams that can be read
in sync. Two strings S, T ∈ Σn form a d-near-alignment if
the distance between them in some given metric is at most d.
We study the problem of identifying a longest substring of S
and T that forms a d-near-alignment under the edit distance,
in the simultaneous streaming model. In this model, symbols of
strings S and T are streamed at the same time, and the amount
of available processing space is sublinear in the length of the
strings.
We give several algorithms, including
an exact one-pass

algorithm that uses O d2 + d log n bits of space. We couple
these results with comparable lower bounds.

I. I NTRODUCTION
A data stream is a massive sequence of elements (network
packets, database transactions, sensor network reads, or parts
of nucleic acids) that requires further processing, while it
is too large to be stored entirely. The area of streaming
algorithms, initiated in [1], is now a core subject in computer
science, focusing on re-designing classical algorithms to the
setting where the amount of available working space is only
sublinear in the size of the data. Furthermore, the area has
connections to other modern topics, including sketching,
compressed sensing and communication complexity (for
comprehensive surveys, see e.g., [8], [23], [15]).
In this work we are concerned with approximately measuring the similarity between two data streams, by finding a
largest ‘near-alignment’. Two strings S, T ∈ Σn form a dnear-alignment if the distance between them in some given
metric is at most d. In this paper we consider the edit distance
(or Levenshtein distance), which is the minimum number of
insertions, deletions, or substitutions needed to obtain one
string from the other.
We study the d-Substring Alignment problem of finding
the longest d-near-alignment in the edit distance, consisting
of substrings in S and T of the form (S[i, j], T [i, j])), when
the symbols of S and T are streamed in sync1 .
∗ Department of Computer Science, Purdue University, West Lafayette,
IN. elena-g@purdue.edu. Research supported in part by NSF CCF1649515.
† School of Informatics and Computing, Indiana University, Bloomington,
IN. esadeqia@indiana.edu
‡ Department of Computer Science, Purdue University, West Lafayette,
IN. samsonzhou@gmail.com. Research supported in part by NSF
CCF-1649515.
1 In this paper, all the techniques and results are presented assuming the
input is in binary bits. However, all the results can be adapted for non-binary
settings.

Samson Zhou

‡

The following definition formally defines ℓmax , the quantity that is studied in this paper.
Definition 1: The length of the longest d-near-alignment
between two strings S and T , with length n, is
ℓmax =

max {j − i + 1 | ed(S[i, j], T [i, j]) ≤ d},

1≤i≤j≤n

where ed(S[i, j], T [i, j]) denotes the minimum number of
insertions, deletions, or substitutions needed to obtain T [i, j]
from S[i, j].
Example 2: Let S = “1234yyyyyy123456789xxxxx”
and T = “1234xxxxxx123467890yyyyy”, and d = 2. The
longest d-near-alignment between S and T is “123456789”
from S and “123467890” from T . This implies that ℓmax =
9.
Specifically, in the simultaneous streaming model, the
symbols at index i of two strings S and T arrive at the
same time, and the pair (S[i], T [i]) arrives right before
the pair (S[i + 1], T [i + 1]). In the streaming model, the
algorithm can only use a small amount of space, ideally
sublinear in the length of the input. The input may be
revealed in one pass or multiple passes, and the goal is
to obtain a solution to an optimization problem. One pass
algorithms have a wider range of applications. Though, some
applications might allow two or more passes over input.
Our results
We obtain several algorithms and lower bounds for the dSubstring Alignment problem in the simultaneous streaming
model, as detailed next. We will use ℓmax to denote the
length of a longest d-near-alignment, in the edit distance.
As a warm-up, we start with a multiplicative and an
additive approximation.
Theorem 3: There exists a one-pass simultaneous streaming algorithm
that provides
a (1 + ǫ)-approximation to ℓmax ,


log2 n
using O ǫ dlog(1+ǫ)
bits of space.
Theorem 4: There exists a one-pass simultaneous streaming algorithm that provides a d-near-alignment
of length at

n
least ℓmax − E using O E
d log n bits of space.
Our main result is a one-pass, exact algorithm that outputs
a maximum-length d-near-alignment using O d2 + d log n
bits of space. Hence, the multiplicative bound from
Theorem 3 achieves space savings guarantees if the sequence
of edits does not need to be printed and d = ω(log2 n). The
additive space bound from Theorem 4 achieves
better upper
n
.
bounds guarantees if we afford E = ω n log
d
Theorem 5: There exists a deterministic one-pass algorithm that outputs ℓmax , along with the necessary edit
operations, using O d2 + d log n bits of space.

We remark that our algorithms can be extended to the
more general case where the substrings of S and T need not
begin at the same index. Given the promise that a longest
alignment of the two strings begins within δ indices of each
other, one may run δ instances of our algorithms in parallel,
thus incurring an extra factor of δ in the space complexity.
In terms of lower bounds, if the edits to obtain the longest
d-near alignment are output, then we trivially must use
Ω(d log n) bits of space. A straightforward argument shows
that this lower bound holds even if the algorithm is not
required to output the positions of the mismatched indices.
Theorem 6: For ǫ < 1 and E ∈ R+ , any deterministic
algorithm that computes a (1 + ǫ)-multiplicative, or an Eadditive approximation of ℓmax requires Ω(d log n) bits of
processing space.
We also give a lower bound for the d-Substring Alignment
problem in the streaming model where the string S appears
before the string T (rather than √
in sync).
Theorem 7: For 7 < d = o( n), any randomized (1 +
ǫ)-approximation streaming algorithm computing ℓmax with
success probability at least 1 − 1/n, requires Ω(d log n) bits
of space.
Finally, we observe that our algorithms can be modified
to recognize complementary d-near-alignments, which are
objects relevant to computational biology arising in pairings
of DNA or RNA sequences:
P
P
Definition 8: Let f : P→
be a pairing of symbols in
n
the alphabet. A string S ∈
is a complementary alignment
if S[x] = f (T [x]) for all 1 ≤ x ≤ n.
Indeed, for each character T [x] in T , one can feed f (T [x])
instead of T [x] to our algorithm in order to find a complementary alignment between S and T .
Motivation and related work
The d-Substring Alignment problem is a restricted variant
of the classic Longest Common Substring problem, in which
the goal is to find a longest substring common to the given
strings S and T . It is also related to the Longest Common
Subsequence problem, in which the goal is to find the longest
common subsequence of S and T . The offline solutions
to these problems involve either suffix trees or dynamic
programming [33], [18]. Some of these problems and related
string alignment problems have been recently studied in the
streaming model (e.g., [22], [29], [7], [20], [14]).
Real data is often subject to errors, and hence algorithms
that account for “near”-alignments, rather than just alignments, are important for processing data. The mismatches
leading to near-alignments are most relevant to metrics such
as Hamming and edit distance. While the Hamming distance
only accounts for substitutions, the edit distance accounts
for insertions and deletions, in addition to substitution.
Therefore, it is often the case that the study of alignment
problems in the edit distance is more challenging than in the
Hamming distance.
Alignment problems have sustained interest in the computer science community over many decades (see e.g., book
[4]). The edit metric has been recently well-studied in the

streaming model, e.g., [3], [5], [9], [10], [6]), and “mismatches” in the Hamming metric have been investigated in
[25], [21], [2], [13], [11], [28], [16], [12].
Preliminaries and Overview
We denote the set {1, 2, . . . , n} by [n]. We assume that two
input streams are strings of length n over a finite alphabet Σ.
Given a string S[1, . . . , n], we denote its length by |S|, its ith
character by S[i] or Si , and the substring between locations
i and j (inclusive) by S[i, j].
The edit or Levenshtein distance between S and T ,
denoted ed(S, T ), is the minimum number of insertions,
deletions, or substitutions needed to obtain one string from
the other. We say S[i, j] and T [i, j] is a d-near-alignment
if ed(S[i, j], T [i, j]) ≤ d. A related metric which we use
in proving lower bounds is the Hamming distance. The
Hamming distance between S and T , denoted HAM(S, T )
is the number of indices whose symbols do not match:
HAM(S, T ) = {i | S[i] 6= T [i]} .
The approximation algorithms from Theorem 3 and
Theorem 4: We define a sequence of checkpoints, such that
at each checkpoint we initiate a sketch of the following
characters in each of the two streams, S and T , so that
we can compare the alignments. The checkpoints for the
one-pass multiplicative algorithm in Theorem 3 are dynamically created and maintained to guarantee the (1 + ǫ)approximation, as in Figure 1, while the checkpoints for the
one-pass additive algorithm are predefined.
For each checkpoint c, we create a sketch of S[c, x], using
the data structure from [6], which uses O (d log n) bits of
space. This sketch is indeed relevant to the simultaneous
streaming model.
Theorem 9: [6] There exists a data structure in the simultaneous streaming model that computes the edit distance
using O (d log n) bits of space and O n + d2 processing
time. Furthermore, this data structure can be augmented
 to
recover the necessary edit operations, using O d2 log n bits
of space.
Upon reading S[x] and T [x], for each checkpoint c
we compare the sketches of S[c, x] and T [c, x] using [6]
(Theorem 9). If the edit distance is greater than d, we discard
the sketches. Otherwise, we compare x − c + 1 to our
estimate of the length of the longest d-near-alignment and
proceed with the stream. We give further details about how
the structure updates from S[c, x] to S[c, x + 1] shortly.
To obtain the additive approximation guaranteed by the
one-pass algorithm in Theorem 4, we modify our checkpoints, so that they appear in every E positions. Hence,
the longest d-near-alignment contains a checkpoint within
E positions of the its first position, and the algorithm will
recover a d-near-alignment with length at least ℓmax − E.
For the sake of completeness, we now briefly describe the
Belazzougui-Zhang (BZ) Sketch [6] (Theorem 9) mentioned
above. Recall that the edit distance between two strings in
the classic offline model can be solved through dynamic programming, such as in the Needleman-Wunsch and WagnerFischer algorithms [31], [24], [26], [27], [32]. The dynamic

Longest d-near-alignment

String T
String S
ci+1

ci

ci+2

ci+3

x

Sketch for each checkpoint c to recover ed(S[c, x], T [c, x]).
Fig. 1.

Checkpoints spaced to guarantee (1 + ǫ)-approximation.

programming solution involves creating an alignment matrix,
namely an n × n matrix whose ij th entry contains the value
of ed(S[1, i], T [1, j]), called the score of that entry. The
BZ data structure outputs ed(S[1, x], T [1, x]) by keeping a
sketch of the alignment matrix, size O (d log n), as well as
some additional information to mimic the recursive solution
in the offline model. Upon seeing S[x + 1] and T [x + 1], it
updates the sketch by performing the same recursion as the
classic offline dynamic programming solution.
Specifically, the BZ sketch notes that for aligned strings
with edit distance at most d, at most 2d + 1 diagonals need
to be considered, as in Figure 2. The sketch maintains a key
invariant: the scores of any two adjacent diagonals can differ
by at most 1.
The algorithm maintains a suffix tree that allows computation of the longest common prefix of suffixes of S and T .
Thus, the algorithm updates the score for each diagonal by
mimicking dynamic programming, based on the scores of the
adjacent diagonals, information from the suffix tree, as well
as additional information on the location of the most recent
edit operation in each diagonal.
Our one-pass exact algorithm in Theorem 5 bypasses
the use of the BZ sketch from [6], to obtain improved
space guarantees. Indeed, while one may use the BZ sketch
here too for O d2 log n bits of space, our algorithm uses
O d2 + d log n bits of space.
Our approach is based on a couple of important observations. First, no character in S may be aligned to a character
in T that is at least d + 1 positions away. Thus, if there
exist d + 1 consecutive positions in S that are aligned to
d + 1 consecutive positions in T , then we only need to keep
the locations of the d most recent edit operations before this
region. Therefore, any (d + 1)2 sequence of consecutive positions either contains such a region (where d+1 consecutive
positions in S are aligned to d+1 consecutive positions in T ),
or requires at least d edit operations in order to be aligned.
The algorithm maintains a sliding window of size (d + 1)2
as well as the locations of the d most recent edit operations,
allowing recovery of the longest d-near-alignment.
However, straightforward recovery of the edit operations
in the sliding window using a BZ sketch takes O d2 log n

bits. To improve on this space complexity, we modify the
classical Hirschberg’s algorithm [17]. Recall that Hirschberg
algorithm is a dynamic programming algorithm that finds the
optimal sequence alignment between two strings of length n
using O (n log n) bits of space. It uses divide-and-conquer
to split each string into two substrings, and recursively
compares the optimal sequence alignment between the corresponding substrings. Weuse the algorithm here on the sliding
window of length O d2 , but because we are only interested
in finding alignments with edit distance at most d, we can
allow the Hirschberg algorithm to throw away any alignments
with edit distance more than d. This modification, detailed
11, produces an algorithm that uses
in the proof of Theorem

O d2 + d log n bits of space.
The lower bounds Finally, to show the lower bound
from Theorem 7 we construct distributions for which any
deterministic algorithm fails with significant probability unless given a certain amount of space, and then apply Yao’s
principle. We first reduce the problem of approximating
the longest d-near-alignment under the edit distance to the
problem of approximating longest d-near-alignment under
the Hamming distance. We then reduce the problem to exactly identifying whether two strings have Hamming distance
at most d. We construct hard distributions, and show via
counting arguments that deterministic algorithms using “low”
amounts of space fail on inputs from these distributions.
II. T HE M ULTIPLICATIVE A PPROXIMATION A LGORITHM
In this 
section, we prove Theorem 3, giving a

log2 n
space, one-pass streaming algorithm
O ǫ dlog(1+ǫ)
with multiplicative approximation (1 + ǫ) to the length
of the longest d-near-alignment under
the edit distance.

3
) log2 n
update
Furthermore, the algorithm uses O (nd+d
ǫ log(1+ǫ)
time per arriving symbol.
Prior to the stream, we initialize the list of checkpoints C
to be the empty set, and ℓ̃ (the current estimate of the length
of the longest d-near-alignment) to be zero. We dynamically
create and maintain the checkpoints to guarantee the (1 + ǫ)approximation. At each checkpoint, we initiate a BZ sketch
for each of the two streams, S and T , so that we can compare
the alignments. We also set cstart , the beginning position of

T [2d]

T [d]

T [1]
S[1]
Fig. 2.

Maintenance:
(1) Read S[x], T [x].
(2) For each checkpoint c ∈ C, update the sketches of
ed(S[c, x − 1], T [c, x − 1]) to ed(S[c, x], T [c, x])
respectively.
(3) For all k ≥ k0 :


a) √
If x is a multiple of α(1 + α)k−2 , where α =
1 + ǫ − 1. then add the checkpoint c = x to
C. Set level(c) = k.
b) If there exists a checkpoint c with level(c) = k
and c < x − 2(1 + α)k , then delete c from C.
(4) For every checkpoint c ∈ C such that x−c+1 > ℓ̃,
check if S[c, x] and T [c, x] are d-near-alignments.
If S[c, x] and T [c, x] are d-near-alignments, then
set cstart = c, ℓ̃ = x − c + 1.
(5) If x = n, then report cstart and ℓ̃.
Because the checkpoints are spaced as the same as [7],
then the following properties hold:
 Observation

  10: [7] At reading S[x], for all k ≥ k0 =




(1+α)2
α

log(1+α)

S[2d]

The BZ sketch mimics dynamic programming (essentially Figure 4 in [6])

the returned d-near-alignment, to be zero. The algorithm in
full appears below.

log

S[d]

, let Cx,k = {c ∈ C | level(c) = k}.



(1) Cx,k ⊆ [x − 2(1 + α)k , x].
(2) The distance
betweentwo consecutive checkpoints of

Cx,k is α(1
+
α)k−2 m.
l
k

2(1+α)
(3) |Cx,k | = ⌊α(1+α)
k−2 ⌋ .
(4) At any point
the number of check
 in the algorithm,
log n
.
points is O ǫ log(1+ǫ)

Proof of Theorem 3: Let ℓmax be the length of the longest
d-near-alignment, between indices imax and jmax . Let k be
k−1
the
< ℓmax , where α =
√ largest integer so that 2(1 + α)
1 + ǫ − 1. Therefore, jmax − 2(1 + α)k−1 > imax .
By Observation 10, there exists a checkpoint in
the interval [jmax − 2(1 + α)k−1 , jmax ]. Moreover,
Observation 10 also implies that consecutive checkpoints of



level k − 1 are separated by distance α(1 + α)k−2 .
a checkpoint c in the interval
Thus, there exists
jmax − 2(1 + α)k−1 , jmax − 2(1 + α)k−1 + α(1 + α)k−3 .
Hence, the output ℓ̃ of the algorithm is at least
2(1 + α)k−1 − α(1 + α)k−3 . Thus, the output of the
algorithm satisfies the approximation guarantee
2(1 + α)k
ℓmax
≤
2(1 + α)k−1 − 2α(1 + α)k−3
ℓ̃
=

(1 + α)3
≤ (1 + α)2 = 1 + ǫ.
(1 + α)2 − α

log n
checkpoints at any
Since there are at most ǫ log(1+ǫ)
point, and each sketch S[ci , x]
uses
O
(d

 log n) space, then
log2 n
the total space used is O ǫ dlog(1+ǫ)
. As each sketch

2
requires
O n+
d update time, the total update time is

(nd+d3 ) log2 n
.
✷
O
ǫ log(1+ǫ)

III. T HE A DDITIVE A PPROXIMATION A LGORITHM
In this section,
we prove Theorem 4, giving a

n
O E
d log n
space, one-pass streaming algorithm
returning the length of the longest d-near-alignment under
the edit distance, with additive error at most E. Unlike the
previous algorithm that uses a series of dynamic checkpoints,
this algorithm creates and maintains a checkpoint for every
multiple of E. Again, the checkpoints “sandwich” the
longest d-near-alignment within an additive window of size
E. Before the stream begins, we initialize ℓ̃, the current
estimate of the length of the longest d-near-alignment to
be zero and cstart , the beginning position of the returned
d-near-alignment, to be zero. Then upon seeing characters
S[x] and T [x] in the stream:
Maintenance:
(1) Read S[x], T [x].
(2) For each checkpoint c, update the sketches of
ed(S[c, x − 1], T [c, x − 1]) to
ed(S[c, x], T [c, x]), respectively.
(3) If x is a multiple of E, then add the checkpoint

c = x to C.
(4) For every checkpoint c ∈ C such that x − c +
1 > ℓ̃, we check if S[c, x] and T [c, x] are dnear-alignments. If S[c, x] and T [c, x] are d-nearalignments, then set cstart = c, ℓ̃ = x − c + 1.
(5) If x = n, then report cstart and ℓ̃.
We now show correctness of Theorem 4.
Proof of Theorem 4:
Let ℓmax be the length of the
longest d-near-alignment, between indices imax and jmax . If
jmax − imax ≤ E, then the result holds trivially. Otherwise,
imax + E < jmax and there exists a checkpoint in the
interval [imax , imax + E], since the checkpoints are spaced
distance E apart. From the correctness of the BZ sketch, the
checkpoint will find a d-near-alignment, and so the output
of the algorithm will be at least jmax − (imax + E) + 1 ≥
ℓmax − E. Thus, the correctness of the algorithm follows.
Since we keep a sketch for each multiple of E, there are
n
E checkpoints. Each sketch
 is of size
 O (d log n) bits, so the
n
d log n .
✷
total space used is O E
IV. T HE L ONGEST d-N EAR -A LIGNMENT A LGORITHM

In this section, we present a one-pass streaming algorithm that returns
 the longest d-near-alignment with space
O d2 + d log n bits, thus proving Theorem 5. We emphasize that the algorithm is deterministic.
The idea is to distinguish between the following two cases:
either all edit operations corresponding to the longest d-nearalignment are close to each other, or there is at least one pair
of consecutive edit operations that are at least d indices apart.
We show that if the second case holds, so that there is at least
one pair of consecutive edit operations that are at least d
indices apart, it suffices to keep the locations of the d most
recent edit operations before this region. To this end, our
algorithm stores the information of the optimal alignment for
the region of the input before a long-enough gap of identical
substrings, along with all the characters in a sliding window
of a length at most (d + 1)2 .
Consider a sliding window beginning at some position b
and ending with the most recent position, x. We enforce an
invariant for this window: the edit operations corresponding
to the optimal alignment within this window are always at
most d positions apart from each other. We ultimately show
in Lemma 12 that this property ensures the sliding window
has size at most (d + 1)2 .
However, naı̈vely recovering the edit operations in the
sliding window takes O d2 log n bits. Thus, we detail
modifications of the classical Hirschberg algorithm, called
procedure ModifiedHirschberg,
in Theorem 11 to guarantee

O d2 + d log n space. While the classical Hirschberg algorithm is a dynamic programming algorithm that finds the
optimal sequence alignment between two strings, the promise
that our alignment contains at most d edits allow us to greatly
narrow the search space.
Let A denote the set of the most recent d edit operations
corresponding to the optimal alignment between for S[0, b]
and T [0, b].

In summary, the algorithm stores the following data:
•
•
•
•

The indices b and x.
The characters of S[b, x] and T [b, x].
The set of at most d edit operations A, in a queue data
structure.
The information of the longest d-near-alignment found
so far, namely:
◦ is , js : the two ends of the d-near-alignment, so that
ℓ = js − is + 1 is the length of the longest d-nearalignment
◦ L: the set of edit operations.

Maintenance:
(1) Read S[x], T [x].
(2) Construct the optimal alignment between S[b, x]
and T [b, x] using ModifiedHirschberg algorithm.
If there exist d + 1 consecutive positions in S that
are aligned to d+1 consecutive positions in T , i.e.,
S[i1 , j1 ] = T [i2 , j2 ] with j1 − i1 = j2 − i2 > d,
then
a) Append the at most d latest edit operations
corresponding to indices before i1 and i2 to A
from the optimal alignment between S[b, x] and
T [b, x].
b) Remove earlier operations from A, until |A| ≤
d.
c) Update b = min{j1 , j2 }.
(3) Identify whether ed(S[b, x], T [b, x]) is greater than
d using ModifiedHirschberg algorithm.
(4) If ed(S[b, x], T [b, x]) > d, then define c
to be the smallest index in [b, x] such that
ed(S[c, x], T [c, x]) ≤ d. Note that c is also computable with ModifiedHirschberg algorithm.
(5) Else if ed(S[b, x], T [b, x]) ≤ d, let f =
ed(S[b, x], T [b, x]), and define c be the index of
(d − f )th operation from the end in A.
(6) In either case, check if x − c + 1 > ℓ, then update
is , js , ℓ, L accordingly.
(7) If x = n, then report L and ℓ.
Theorem 11 (ModifiedHirschberg): Given two strings S
and T of length m and a parameter d, there exists an
algorithm that either states that ed(S, T ) > d or recovers
the locations of the edit operations if ed(S, T ) ≤ d, using
O (m + d log m) space and O (md log m) time.
Proof: The classic Hirschberg’s algorithm [17], [19]
returns the locations of the optimal edit operations between
S and T in O (m log m) space. However, if we do not care
about the locations of the edit operations for ed(S, T ) > d,
then we can optimize the space down to O (m + d log m)
bits using ideas from [30].
In the classic Hirschberg algorithm, the edit distance is
computed for multiple alignments. Specifically, the entry
ij in the dynamic programming lookup table contains the
edit distance between the substrings S[1, i] and T [1, j].
However, if |j − i| > d, then the edit distance between

S[1, i] and T [1, j] is greater than d. Therefore, at each
level of Hirschberg’s algorithm, we only keep 2d − 1 cells
around the main diagonal (a similar idea is used for the BZ
sketch in Figure 2). If ed(S, T ) > d, then some optimal edit
operation will appear outside of the cells that we keep. Thus,
the algorithm recognizes that it cannot recover the optimal
operations, and instead declares ed(S, T ) > d. Hence, if
ed(S, T ) ≤ d, the algorithm will return the locations of the
optimal edit operations, whereas if ed(S, T ) > d, the algorithm outputs ed(S, T ) > d. Since each cell contains a score
using log m bits, the total space used is O (m + d log m).
Recall that Hirschberg’s algorithm uses a divide-andconquer approach, splitting the dynamic programming table
into two subproblems, roughly of equal size, say q and m−q,
′
where q − m
2 ≤ d. At each level, with input size m , the
′
algorithm takes O (m d) time. Hence, the algorithm satisfies
the recursion T (m) = O (md) + T (m − q) + T (q) so that
the overall running time is O (md log m).
Lemma 12: Let x, y ∈ Σh be two strings of length h.
Also let A be the set of all edit operations corresponding
to the optimal alignment between x and y. If e is the maximum distance between two operations among all consecutive
operations in A, then we have: h ≤ (|A| + 1)(e + 1).
Proof: Suppose, by way of contradiction, h > (|A| +
1)(e + 1). Since e is the maximum distance between the
locations of two operations among all consecutive operations
in A, then any group of e+1 consecutive characters contains
an edit operations. But there are at least |A| + 1 disjoint
groups of e + 1 consecutive characters, so there are at least
|A| + 1 edit operations. This contradicts the definition that
A is the set of all edit operations.
We now show the correctness of Theorem 5.
Proof of Theorem 5: Let i and j be the two endpoints of
the longest d-near-alignment. Also, let L be the set of edit
operations corresponding to the optimal alignment between
S[i, j] and T [i, j]. There are two cases for this alignment.
Either no two consecutive operations in L have distance
farther than d + 1 or there exist d + 1 consecutive positions
in S which are aligned to d + 1 consecutive positions in T .
In the first case, the correctness follows from the correctness of Theorem 9 and Lemma 12. In this case, S[i, j] and
T [i, j] will be covered by the sliding window after reading
S[j] and T [j]. This means that in line (3), x = j and the
algorithm will assign c = i. Thus, the algorithm will report
the correct d-near-alignment.
Suppose the second case occurs. So, there exist d + 1
consecutive positions in S[i, j] are aligned to d + 1 consecutive positions in T [i, j], i.e., S[i1 , j1 ] = T [i2 , j2 ] with
j1 −i1 = j2 −i2 > d. We claim that no character before i1 (i2 ,
respectively) in S (T , respectively) could be aligned to any
character after j2 (j1 , respectively) in an optimal alignment
between S[i, j] and T [i, j], as in Figure 3.
Otherwise, more than d insertions or deletions are required.
Therefore, the algorithm will recover the alignment between S[i, i1 ] and T [i, i2 ] from what it has already stored in

A. In addition, the alignment between S[i1 , j] and T [i2 , j]
is constructed at line (2) and these two alignments are
combined in line (4).
The space needed to store A and L is O (d log n) as there
are at most 2d operations in each data structure. Taking
|A| ≤ d and e = (d+1)in Lemma 12 implies that the sliding
window [b, x] is O d2 bits long. Taking m = (d + 1)2 in
Theorem 11 implies that recovery
 of the edit operations can
be done using O d2 + d log n space. Hence,
 the overall
memory of the algorithm is O d2 + d log n bits. Again
taking m = (d + 1)2 in Theorem 11 shows
 that the running
time per arriving symbol is O d2 log d .
✷
We observe that the running
time per arriving symbol can

be improved to O d2 by creating a BZ sketch for the
entire sliding
 window. However, this implementation uses
O d2 log d space instead.
V. L OWER B OUNDS

To prove Theorem 7, we first create a distribution between
two strings, over which calculating the edit distance is
equivalent to calculating the Hamming distance. We then
show that any deterministic algorithm that approximates long
length d-near-alignments under Hamming distance with high
probability requires a certain amount of space through a
simple counting argument. By Yao’s Minimax Principle, any
randomized algorithm with the same probability of success
requires the same amount of space.
To prove Theorem 7, we define X be the set of binary
strings of length n with d many 1’s. We pick x independently
and uniformly at random from X and y independently and
uniformly at random from the set of binary strings of length
n with either HAM(x, y) = d or HAM(x, y) = d + 1. Define
transformation s(x) = x1 1d+1 x2 1d+1 . . . 1d+1 xn 1d+1 . Thus,
we pick (S, T ) ∼ (s(x), s(y)).
Claim 13: If ed(x, y) = d, then there exist a sequence
of d insertions, deletions, or substitutions on x to obtain
y. Furthermore, we may perform the substitutions first,
followed by the insertions, then the deletions.
Proof: First, we fix a sequence of d operations to
obtain y from x, and note that no character can be inserted
and subsequently deleted, or else the edit distance between
x and y would be less than d by avoiding these operations. Similarly, any character which undergoes a substitution
should not be involved in either an insertion or a deletion.
Hence, any character is involved in at most one operation.
But since a character is not affected by operations on other
characters, we may first perform the substitutions, followed
by the insertions, then the deletions.
Lemma 14: ed(s(x), s(y)) = HAM(x, y)
Proof: By Claim 13, we may perform the substitutions
first, followed by the insertions, then the deletions to obtain
s(y) from s(x). Let s1 (x) be s(x) following the sequence
of substitutions. Suppose there exists a position in s1 (x)
which does not equal the corresponding position in s(y).
Then the position is zero in one of s1 (x) or s(y). However,
the nearest zero in the other string is at least d + 1 positions

Length ≥ d + 1

Fig. 3. If there exists some alignment in which the red regions are aligned, then nothing before the region can be aligned to anything after the region
(the dashed alignment can never exist). Thus, it suffices to keep the locations of the d most recent edit operations before the region (for example, the blue
lines)

away, requiring at least d + 1 additional operations. Since
ed(s(x), s(y)) ≤ HAM(s(x), s(y)) ≤ d + 1, then it follows
that every single operation to obtain s(y) from s(x) must be
a substitution, and so ed(s(x), s(y)) ≥ HAM(s(x), s(y)). By
construction, HAM(s(x), s(y)) = HAM(x, y) and the result
follows.
n
bits
Lemma 15: Any algorithm D using less than d log
3
of memory cannot distinguish between HAM(x, y) = d and
HAM(x, y) > d with probability at least 1 − 1/n.

Proof: Note that |X| = nd . By Stirling’s approxima
√
d
d/2
tion, |X| ≥ nd . Since d = o( n), then |X| ≥ (n) .

n
If D uses less than d log
bits of memory, then D has at
3
d log n
most 2 3 = nd/3 unique memory configurations. Since
|X| ≥ (n)d/2 , then there are at least 21 (|X| − nd/3 ) ≥ |X|
4
pairs x, x′ such that D has the same configuration after
reading x and x′ . We show that D errs on a significant
fraction of these pairs x, x′ .

Let I be the positions where either x or x′ take value 1, so
that d + 1 ≤ |I| ≤ 2d. Observe that if HAM(x, y) = d, but x
and y do not differ in any positions of I, then HAM(x′ , y) >
d. Recall that D has the same configuration after reading x
and x′ , but since HAM(x, y) = d and HAM(x′ , y) > d,
then the output of D is incorrect for either HAM(x, y) or
HAM(x′ , y).


For each pair (x, x′ ), there are n−|I|
≥ n−2d
such
d
d
y with HAM(x, y) = d, but x and y do not differ in any
n−2d
strings s(x, y) for
positions of I. Hence, there are |X|
4
d
which D errs. We note that there is no overcounting because
the output of D can be correct for at most one HAM(xi , y)
for all xi mapped to the same configuration. Recall that y
satisfies either HAM(x,
  y) = dor HAM(x, y) = d + 1 so
n
that there are |X| nd + d+1
pairs (x, y) in total. Thus,
the probability of error is at least

|X| n−2d
n−2d
1
d
4  d

 = 4 · n+1
n
|X| nd + d+1
d+1
=
Since

n−3d+1
n−d+1

(d + 1) (n − 3d + 1) . . . (n − 2d)
4
(n − d + 1) . . . (n + 1)
≤

n−3d+i
n−d+i

for all i ≥ 1, it follows that the

probability of error is at least

d

d
2d
n − 3d + 1
d+1
d+1
1−
=
4(n + 1) n − d + 1
4n + 4
n−d+1

Then by Bernoulli’s Inequality (which states that (1 + x)r ≥
1 + rx for x ≥ −1 and r ≥ 1), the probability of error is at
least


d+1
2d2
1
1−
≥
4n + 4
n−d+1
n
√
Since d = o( n), then for large n, it follows that 1 −
2
1
2d
n−d+1 ≥ 2 . Hence, for d > 7, the probability of error is at
1
least n .
Therefore, Ω(d log n) bits of memory are necessary to
distinguish between HAM(x, y) = d and HAM(x, y) > d
with probability at least 1 − 1/n.
Now, we use a simple trick to show that any sketch
providing a (1+ǫ)-approximation to the length of the longest
d-near-alignment under the edit distance with probability at
least 1 − 1/n requires Ω(d log n) space.
Proof of Theorem 7:
Recall that s(x)
=
x1 1d+1 x2 1d+1 . . . 1d+1 xn 1d+1 . Define string t(x) =
1(d+1)n/2 x1(d+1)n/2 so that the longest d-near-alignment of
t(s(x)) and t(s(y)) has length 2(d + 1)n if ed(x, y) ≤ d.
On the other hand, if ed(x, y) > d, then the longest dnear-alignment of t(s(x)) and t(s(y)) has length at most
(d + 1)n. Thus, a (1 + ǫ)-approximation to the length of the
longest d-near-alignment of t(s(x)) and t(s(y)) differentiates
whether HAM(x, y) ≤ d or HAM(x, y) > d. Since t(s(x))
has length 2(d+1)n, any sketch which √
achieves this requires
Ω(d log(n/d)) bits. Because d = o( n), then the result
follows.
✷
We now turn our attention to Theorem 6, which states
that any algorithm computing a (1 + ǫ)-multiplicative or Eadditive approximation of the length of the longest d-near
alignment under the edit distance and outputs the necessary
edit operations requires Ω(d log n) bits, even in the simultaneous streaming model. Furthermore, simply determining
the length of the longest d-near alignment also requires
Ω(d log n) bits.
Proof of Theorem 6: We first prove that any algorithm
that computes a (1 + ǫ)-multiplicative approximation of the

length of the longest d-near alignment under the edit distance
requires Ω(d log n) bits using a reduction from the corresponding problem from communication complexity. Namely,
in the communication complexity model, Alice receives the
first half of both S and T , and Bob receives the second half
of S and T ; their goal is to find the longest
 d-near-alignment


between S and T . Now, suppose S 1, n2 and T 1, n2 have
edit distance
 d, andnone of the edit operations occur within
1
the first 1 − 1+ǫ
n positions of S and T . Thus, Alice
must communicate the locations of all edit operations (i.e.,
Ω(d log n) bits.), as any one of these locations could be the
beginning of the longest d-near-alignment.
We observe that an algorithm that computes a E-additive
approximation of the length of the longest d-near alignment
under the edit distance and outputs the necessary edit operations also forces Alice to communicate the locations
 n  of
the d most
recent
edit
operations,
provided
that
S
1, 2 and

T 1, n2 have edit distance d and none of the edit operations
occur in the first E locations of Alice’s input.
Finally, if Alice and Bob must output
 the length

of the
longest d-near-alignment, and S 1, n2 and T 1, n2 have
edit distance d, then Alice must output the locations of the
d most recent edit operations.
✷
R EFERENCES
[1] Noga Alon, Yossi Matias, and Mario Szegedy. The space complexity
of approximating the frequency moments. In Proceedings of the
twenty-eighth annual ACM symposium on Theory of computing, pages
20–29. ACM, 1996.
[2] Srinivas Aluru, Alberto Apostolico, and Sharma V. Thankachan. Efficient alignment free sequence comparison with bounded mismatches.
In Research in Computational Molecular Biology - 19th Annual
International Conference, RECOMB, Proceedings, pages 1–12, 2015.
[3] Alexandr Andoni, Assaf Goldberger, Andrew McGregor, and Ely
Porat. Homomorphic fingerprints under misalignments: sketching edit
and shift distances. In Proceedings of the Forty-Seventh Annual ACM
on Symposium on Theory of Computing, STOC, pages 931–940, 2013.
[4] Alberto Apostolico and Zvi Galil, editors. Pattern Matching Algorithms. Oxford University Press, Oxford, UK, 1997.
[5] Arturs Backurs and Piotr Indyk. Edit distance cannot be computed in
strongly subquadratic time (unless SETH is false). In Proceedings
of the Forty-Seventh Annual ACM on Symposium on Theory of
Computing, STOC, pages 51–58, 2015.
[6] Djamal Belazzougui and Qin Zhang. Edit distance: Sketching,
streaming and document exchange. In 57th Annual Symposium on
Foundations of Computer Science, FOCS, pages 51–60, 2016.
[7] Petra Berenbrink, Funda Ergün, Frederik Mallmann-Trenn, and Erfan
Sadeqi Azer. Palindrome recognition in the streaming model. In 31st
International Symposium on Theoretical Aspects of Computer Science
(STACS), pages 149–161, 2014.
[8] Amit Chakrabarti. Data stream algorithms. Computer Science, 49:149,
2015.
[9] Diptarka Chakraborty, Elazar Goldenberg, and Michal Koucký.
Streaming algorithms for computing edit distance without exploiting
suffix trees. CoRR, abs/1607.03718, 2016.
[10] Diptarka Chakraborty, Elazar Goldenberg, and Michal Koucký.
Streaming algorithms for embedding and computing edit distance in
the low distance regime. In Proceedings of the 48th Annual ACM
SIGACT Symposium on Theory of Computing, STOC, pages 712–725,
2016.
[11] Raphaël Clifford, Allyx Fontaine, Ely Porat, Benjamin Sach, and
Tatiana A. Starikovskaya. The k-mismatch problem revisited. In
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on
Discrete Algorithms, SODA, pages 2039–2052, 2016.

[12] Funda Ergün, Elena Grigorescu, Erfan Sadeqi Azer, and Samson Zhou.
Streaming periodicity with mismatches. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
- 21st International Workshop, RANDOM (to appear), 2017.
[13] Tomás Flouri, Emanuele Giaquinta, Kassian Kobert, and Esko Ukkonen. Longest common substrings with k mismatches. Inf. Process.
Lett., 115(6-8):643–647, 2015.
[14] Pawel Gawrychowski, Oleg Merkurev, Arseny M. Shur, and Przemyslaw Uznanski. Tight tradeoffs for real-time approximation of longest
palindromes in streams. In 27th Annual Symposium on Combinatorial
Pattern Matching, CPM, pages 18:1–18:13, 2016.
[15] Anna C. Gilbert and Piotr Indyk. Sparse recovery using sparse
matrices. Proceedings of the IEEE, 98(6):937–947, 2010.
[16] Elena Grigorescu, Erfan Sadeqi Azer, and Samson Zhou. Streaming for aibohphobes: Longest palindrome with mismatches. CoRR,
abs/1705.01887, 2017.
[17] Daniel S. Hirschberg. A linear space algorithm for computing maximal
common subsequences. Commun. ACM, 18(6):341–343, 1975.
[18] Lucas Chi Kwong Hui. Color set size problem with application to
string matching. In Combinatorial Pattern Matching, Third Annual
Symposium, CPM Proceedings, pages 230–243, 1992.
[19] Jon Kleinberg and Eva Tardos. Algorithm design, 2006.
[20] Tomasz Kociumaka, Tatiana A. Starikovskaya, and Hjalte Wedel
Vildhøj. Sublinear space algorithms for the longest common substring
problem. In Algorithms - ESA. Proceedings, pages 605–617, 2014.
[21] Chris-Andre Leimeister and Burkhard Morgenstern. kmacs: the
k-mismatch average common substring approach to alignment-free
sequence comparison. Bioinformatics, 30(14):2000–2008, 2014.
[22] David Liben-Nowell, Erik Vee, and An Zhu. Finding longest increasing and common subsequences in streaming data. J. Comb. Optim.,
11(2):155–175, 2006.
[23] S Muthukrishnan. Data stream algorithms, 2004.
[24] Saul B. Needleman and Christian D. Wunsch. A general method
applicable to the search for similarities in the amino acid sequence
of two proteins. Journal of Molecular Biology, 48(3):443–53, 1970.
[25] Benny Porat and Ely Porat. Exact and approximate pattern matching in
the streaming model. In 50th Annual IEEE Symposium on Foundations
of Computer Science, FOCS, pages 315–323, 2009.
[26] David Sankoff. Matchings sequences under deletion/insertion constraints. Proceedings of the National Academy of Sciences, 69(1):1–4,
1972.
[27] Peter H. Sellers. On the theory and computation of evolutionary
distances. SIAM Journal on Applied Mathematics, 26(4):787–793,
1974.
[28] Tatiana A. Starikovskaya. Longest common substring with approximately k mismatches. In 27th Annual Symposium on Combinatorial
Pattern Matching, CPM, pages 21:1–21:11, 2016.
[29] Xiaoming Sun and David P. Woodruff. The communication and
streaming complexity of computing the longest common and increasing subsequences. In Proceedings of the Eighteenth Annual ACMSIAM Symposium on Discrete Algorithms, SODA, pages 336–345,
2007.
[30] Esko Ukkonen. Finding approximate patterns in strings. J. Algorithms,
6(1):132–137, 1985.
[31] Taras Vintsiuk. Speech discrimination by dynamic programming.
Kibernetika, 4(1):81–88, 1968.
[32] Robert A. Wagner and Michael J. Fischer. The string-to-string
correction problem. Journal of the ACM, 21:168–178, 1974.
[33] Peter Weiner. Linear pattern matching algorithms. In 14th Annual
Symposium on Switching and Automata Theory,SWAT (FOCS), pages
1–11, 1973.

