Zvi
Galil
Georgia
Institute
of
Technology
Real-Time
Streaming
String-Matching
A key area of application is in inspecting messages as they “stream by,” perhaps through a switch in the Internet. Under this streaming model neither the pattern nor parts of the text are stored and only small amount of space is available. Simple information theoretic arguments imply that no deterministic algorithm is possible in the streaming model and one can only hope for a randomized algorithm which makes errors with small probability. The algorithms mentioned above are not streaming since they store the pattern.
In 2009 Porat and Porat described a surprising result: a randomized O(n log m) streaming algorithm that uses O(log m) space. Each space unit is a register of O(log n) bits. The pattern is first preprocessed and certain information is computed and stored in O(log m) space. Porat and Porat do not give a streaming algorithm for the preprocessing and it is not clear whether such an algorithm is possible for their preprocessing. In addition their randomized algorithm may have two sided errors with small probability; it may miss occurrences of the pattern as well as report occurrences that do not occur.
We
design
two
algorithms
for
the
problem.
The
first
one,
like
Porat
and
Porat,
is
an
O(n
log
m)
time
streaming
randomized
algorithms
using
O(log
m)
space.
The
preprocessing
of
our
algorithm
is
a
trivial
real-time
streaming
algorithm.
Our
algorithm
allows
with
small
probability
only
one
sided
(false
positive)
errors,
which
are
unavoidable.
In
particular,
it
never
misses
an
occurrence.
We
then
modify
this
algorithm
to
obtain
a
real-time
O(log
m)
space
streaming
algorithm
that
uses
a
real
time
streaming
preprocessing
and
allows
only
one
sided
errors.
Porat
and
Porat
used
their
algorithm
as
a
black
box
to
obtain
streaming
algorithms
for
the
1-mismatch
and
k-mismatch
string
matching
problem.
Using
our
algorithm
we
shave
an
O(log
m)
factor
(an
order
of
magnitude)
from
their
time
bounds.
This work
is
joint
with
Danny
Breslauer.
Biography: Zvi Galil was born in Tel-Aviv, Israel. He earned his BS and MS degrees in Applied Mathematics from Tel Aviv University, both summa cum laude. He then obtained a PhD in Computer Science from Cornell University. After a post-doctorate in IBM's Thomas J. Watson research center, he returned to Israel and joined the faculty of Tel-Aviv University. He served as the chair of the Computer Science department in 1979-1982. In 1982 he joined the faculty of Columbia University. He served as the chair of the Computer Science Department in 1989-1994 and as dean of The Fu Foundation School of Engineering & Applied Science in 1995-2007.
Galil was appointed Julian Clarence Levi Professor of Mathematical Methods and Computer Science in 1987, and Morris and Alma A. Schapiro Dean of Engineering in 1995. In 2007 Galil returned to Tel Aviv University and served as president. In July 2010 he became The John P. Imlay, Jr. Dean of Computing at Georgia Tech.
Galil's research areas have been the design and analysis of algorithms, complexity, cryptography and experimental design. In 1983-1987 he served as chairman of ACM SIGACT, the Special Interest Group of Algorithms and Computation Theory.