  Given a stream of data, a typical approach in streaming algorithms is to
design a sophisticated algorithm with small memory that computes a specific
statistic over the streaming data. Usually, if one wants to compute a different
statistic after the stream is gone, it is impossible. But what if we want to
compute a different statistic after the fact? In this paper, we consider the
following fascinating possibility: can we collect some small amount of specific
data during the stream that is "universal," i.e., where we do not know anything
about the statistics we will want to later compute, other than the guarantee
that had we known the statistic ahead of time, it would have been possible to
do so with small memory? In other words, is it possible to collect some data in
small space during the stream, such that any other statistic that can be
computed with comparable space can be computed after the fact? This is indeed
what we introduce (and show) in this paper with matching upper and lower
bounds: we show that it is possible to collect universal statistics of
polylogarithmic size, and prove that these universal statistics allow us after
the fact to compute all other statistics that are computable with similar
amounts of memory. We show that this is indeed possible, both for the standard
unbounded streaming model and the sliding window streaming model.
