  We study the problem of parameterized matching in a stream where we want to
output matches between a pattern of length m and the last m symbols of the
stream before the next symbol arrives. Parameterized matching is a natural
generalisation of exact matching where an arbitrary one-to-one relabelling of
pattern symbols is allowed. We show how this problem can be solved in constant
time per arriving stream symbol and sublinear, near optimal space with high
probability. Our results are surprising and important: it has been shown that
almost no streaming pattern matching problems can be solved (not even
randomised) in less than Theta(m) space, with exact matching as the only known
problem to have a sublinear, near optimal space solution. Here we demonstrate
that a similar sublinear, near optimal space solution is achievable for an even
more challenging problem. The proof is considerably more complex than that for
exact matching.
