  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\in
\Sigma^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
$\mathcal{O}(d^2+d\log n)$ bits of space. We couple these results with
comparable lower bounds.
