Ask
Login
1
4.9kviews
Suppose a data stream consists of the integers 3, 1, 4, 1, 5, 9, 2, 6, 5. Let the hash function being used is h(x) = 3x + 1 mod 5;
written 5.7 years ago by gravatar for swatisharma swatisharma • 1.3k modified 3.0 years ago by gravatar for binitamayekar binitamayekar ★ 6.6k

Show how the Flajolet- Martin Algorithm will estimate the number of distinct element in this stream
big data analytics
ADD COMMENT EDIT
1 Answer
0
552views
written 3.0 years ago by gravatar for binitamayekar binitamayekar ★ 6.6k •   modified 2.6 years ago

S = 3, 1, 4, 1, 5, 9, 2, 6, 5

h(x) = 3x + 1 mod 5

x h(x) Rem Binary r(a)
3 10 0 000 3
1 4 4 100 2
4 13 3 011 0
1 4 4 100 2
5 16 1 001 0
9 28 3 011 0
2 7 2 010 1
6 19 4 100 2
5 16 1 001 0

R = max( r(a) ) = 3

Therefore,

Number of Distinct Elements = $N = 2^R = 2^3 = 8$
ADD COMMENT EDIT
Please log in to add an answer.