We wish to use the Flajolet Martin algorithm to count the number of distinct ele

Question

We wish to use the Flajolet Martin algorithm to count the number of distinct elements in a stream. Assume that there are 10 possible elements {1, 2, …, 10} that could appear in the stream but only 4 of them have actually appeared. To make our estimate of the count of distinct elements, we hash each element to a 4-bit binary number. Element X is hashed to {(3X + 7) modulo 11}. For example element 8 hashes to 3*8+7 = 31 modulo 11 = 9 which maps into the 4-bits (1001). A set of 4 of the elements 1 through 10 could give an estimate that is exact (if the estimate is 4) or too high or too low. Figure out under what circumstances a set of the following 4 elements give the exact correct estimate:

a. (2,6,8,10)

b. (1,3,9,10)

c. (3,7,8,10)

d. (1,6,7,10)

e. (4,5,6,7)

f. (2,5,7,10)

g. (4,5,6,10)

h. (1,3,6,8)

i. (1,2,3,9)

Explanation / Answer

Hi, I have mapped each set to it's hashed value. Pleas find youe desired set according to youe question.

a. (2,6,8,10) (2,3,9,4)
b. (1,3,9,10)   (10,5,1,4)
c. (3,7,8,10)   (5,6,9,4)
d. (1,6,7,10)   (10,3,6,4)
e. (4,5,6,7)   (8,0,3,6)
f. (2,5,7,10)   (2,0,6,4)
g. (4,5,6,10)   (8,0,3,4)
h. (1,3,6,8)   (1,5,,3,9)
i. (1,2,3,9)   (10,2,5,1)

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.