2. Given a stream of updates about items drawn from a universe {1,..., n}, the stream's...

 

Transcribed Image Text:

2. Given a stream of updates about items drawn from a universe {1,..., n}, the stream's fre- quency vector fe R is the vector whose i'th component fi equals the frequency of item i in the stream. For example, for the stream ((add, 5), (add, 7), (add, 5), (add, 7), (delete, 7)) with universe {1,..., 7}, its frequency vector is (0, 0, 0, 0, 2, 0, 1). A streaming algorithm is said to maintain a linear sketch of size k if it stores in memory Af for a matrix A e Rkxn that is fixed at the initialization. (a) Show that the algorithm discussed in class for frequency estimation is a linear sketch. What is the matrix A in this case? (b) Suppose a streaming algorithm is a linear sketch. Assume the matrix A mentioned above is explicitly known to the algorithm. Explain how the algorithm should update its storage each time a stream update comes of the form (add, i) or (delete, i). 2. Given a stream of updates about items drawn from a universe {1,..., n}, the stream's fre- quency vector fe R is the vector whose i'th component fi equals the frequency of item i in the stream. For example, for the stream ((add, 5), (add, 7), (add, 5), (add, 7), (delete, 7)) with universe {1,..., 7}, its frequency vector is (0, 0, 0, 0, 2, 0, 1). A streaming algorithm is said to maintain a linear sketch of size k if it stores in memory Af for a matrix A e Rkxn that is fixed at the initialization. (a) Show that the algorithm discussed in class for frequency estimation is a linear sketch. What is the matrix A in this case? (b) Suppose a streaming algorithm is a linear sketch. Assume the matrix A mentioned above is explicitly known to the algorithm. Explain how the algorithm should update its storage each time a stream update comes of the form (add, i) or (delete, i).