Revisiting Norm Estimation in Data Streams

Understand

The problem of estimating the pth moment F_p (p nonnegative and real) in data streams is as follows.

• There is a vector x which starts at 0, and many updates of the form x_i <-- x_i + v come sequentially in a stream.
• The algorithm also receives an error parameter 0 < eps < 1.
• The goal is then to output an approximation with relative error at most eps to F_p = ||x||_p^p.