2 Data Stream Algorithms
2.1 Misra-Gries Algorithm [1 mark]
Given the data stream below, perform the Misra-Gries algorithm with k = 3 counters and present the summary, including the elements and its counter values, when the execution of the algorithm is finished.
S = {4,36,14,36,57,36,22,57,5,57}
2.2 CountMin Sketch Algorithm [4 marks]
Given the following three hash functions, perform the CountMin Sketch al- gorithm on the same data stream S in Section 2.1 and present the (i) hash table, (ii) counter matrix, and (iii) estimated frequency of each element in a stream after processing all elements.
h1(x) = x mod 3
h2(x)=(3x+1) mod3
h3(x)=(5x+2) mod3
2.3 Count Sketch Algorithm [4 marks]
Consider the same data stream S and hash functions in Section 2.2. Given the sign hash functions below, perform the Count Sketch algorithm and present the (i) hash table, (ii) counter matrix, and (iii) estimated frequency of each element in a stream after processing all elements.
s1(x)=((2x+1) mod3) mod2
s2(x)=((3x+2) mod3) mod2
s3(x)=((5x+2) mod3) mod2
