  We introduce a new computational model for data streams: asymptotically exact
streaming algorithms. These algorithms have an approximation ratio that tends
to one as the length of the stream goes to infinity while the memory used by
the algorithm is restricted to polylog(n) size. Thus, the output of the
algorithm is optimal in the limit. We show positive results in our model for a
series of important problems that have been discussed in the streaming
literature. These include computing the frequency moments, clustering problems
and least squares regression. Our results also include lower bounds for
problems, which have streaming algorithms in the ordinary setting but do not
allow for sublinear space algorithms in our model.
