1

4.7kviews

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.6 years ago by pedsangini276 • 4.8k

•   modified 2.6 years ago

big data analytics

ADD COMMENT FOLLOW SHARE EDIT

1 Answer

0

1.2kviews

written 2.6 years ago by pedsangini276 • 4.8k

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 SHARE EDIT