Ask
Login
1
3.3kviews
Suppose a data stream consists of the integers 1,3,2,1,2,3,4,3,1,2,3,1.Let the hash function being used is h(x) = (6x+1) mod 5; estimate the number of distinct in this stream using FM algorithm.
written 2.0 years ago by gravatar for pedsangini276 pedsangini276 • 4.7k •   modified 2.0 years ago
big data analytics
ADD COMMENT EDIT
1 Answer
0
895views
written 2.0 years ago by gravatar for pedsangini276 pedsangini276 • 4.7k
Data h(x) = 6x+1 mod 5 Reminder Binary bit-String Tail Length
1 h(x) = 6 (1) +1 mod 5 2 010 1
3 h(x) = 6 (3) +1 mod 5 4 100 2
2 h(x) = 6 (2) +1 mod 5 3 011 0
1 h(x) = 6 (1) +1 mod 5 2 010 1
2 h(x) = 6 (2) +1 mod 5 3 011 0
3 h(x) = 6 (3) +1 mod 5 4 100 2
4 h(x) = 6 (4) +1 mod 5 0 000 0
3 h(x) = 6 (3) +1 mod 5 4 100 2
1 h(x) = 6 (1) +1 mod 5 2 010 1
2 h(x) = 6 (2) +1 mod 5 3 011 0
3 h(x) = 6 (3) +1 mod 5 4 100 2
1 h(x) = 6 (1) +1 mod 5 2 010 1

Tail Length = {1,2,0,1,0,2,0,2,1,0,2,1}
R = max (Tail Length) = 2
Estimation of m = 2 ^ R = 2 ^ 2 = 4
Hence we have 4 distinct elements 1,2,3,4
ADD COMMENT EDIT
Please log in to add an answer.