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.
1 Answer
written 2.0 years ago by |
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