COMPSCI 753 Algorithms for Massive Data - Semester2 2021- Final Exam - Q2 Data Stream Algorithms
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
Get the Solution to This Question
WeChat (微信)
WhatsApp
