Determine distinct elements in the stream using Flajolet Martin Algorithm | Big Data

Determine distinct elements in the stream using Flajolet Martin Algorithm

Hash function h(a) = (3x + 1) mod 5

Sequence

1,2,4,1,2,4,4,1,2,4,4,1,7

Hash Function h(a) Substitution

h (1) = (3(1) + 1) mod 5 = 4 mod 5 = 4

h (2) = (3(2) + 1) mod 5 = 7 mod 5 = 2

h (4) = (3(4) + 1) mod 5 = 13 mod 5 = 3

h (7) = (3(7) + 1) mod 5 = 22 mod 5 = 2

Replace the sequence with the hash values

4,2,3,4,2,3,3,4,2,3,3,4,2

Convert into binary format

2 = 010

3 = 011

4 = 100

100, 010, 011, 100, 010, 011, 011, 100, 010, 011, 011, 100, 010

Calculate r(a)

Check Number of trailing zeros [i.e. number of 0’s after 1]

2,1,0,2,1,0,0,2,1,0,0,2,1

R= max(r(a))

R =2

Estimate 2^R

2² = 4 

 More Engineering Blogs