Streaming algorithm

This is the process of data streaming with less memory.

x∈R^n

This is high dimensional vector.

You update it.

xi←xi+v

You have O(n) space, and the whole stream is O(m).

You compress the data by streaming.

A=(1±ε)B

(1-ε)B≦A≦(1＋ε)B

∴

σi,j = ±1, E[σi,j] = 0