Deterministically estimating data stream frequencies

[smart paper boy]

Abstract.
We consider updates to an n-dimensional frequency vector of a data stream, that is, the vector f is updated coordinate-wise by means of insertions or deletions in any arbitrary order. A fundamental problem in this model is to recall the vector approximately, that is to return an estimate ^ f of f such that j ^ fi