We address the problem of preserving privacy in streams,
which has received surprisingly limited attention. For static
data, a well-studied and widely used approach is based on
random perturbation of the data values. However, streams
pose additional challenges. First, analysis of the data has to
be performed incrementally, using limited processing time
and buffer space, making batch approaches unsuitable. Sec-
ond, the characteristics of streams evolve over time. Conse-
quently, approaches based on global analysis of the data are
not adequate. We show that it is possible to efficiently and
effectively track the correlation and autocorrelation struc-
ture of multivariate streams and leverage it to add noise
which maximally preserves privacy, in the sense that it is
very hard to remove. Our techniques achieve much better
results than previous static, global approaches, while re-
quiring limited processing time and memory. We provide
both a mathematical analysis and experimental evaluation
on real data to validate the correctness, efficiency, and ef-
fectiveness of our algorithms.