Exp 7 - Flajolet-Martin algorithm (fm.R)

what it answers : how many DISTINCT elements are in the stream, using O(log n) memory
idea : hash every element to a binary number. a random hash ends in r zeros with prob 1/2^r,
       so if we see a hash with R trailing zeros there are probably about 2^R distinct elements
steps
  1. pick hash h(x) = (a*x + b) mod 2^L
  2. for each element find tail length = no. of trailing zeros of h(x) in binary
  3. R = max tail length over whole stream
  4. estimate = 2^R      (original paper divides by 0.77351)
duplicates give same hash -> do not change R -> that is why it counts distinct items
one estimate is always a power of 2, can be off a lot -> use many hash fns,
  average inside small groups, then take median of the group averages
  (average smooths, median removes one big outlier)
good hash: a should be odd. h(x) = 2x+1 always gives odd values -> tail always 0 -> useless

-------- dry run of fm.R --------
stream = 4 2 5 4 9 2 5 7 4 9 2 7   distinct = {2,4,5,7,9} = 5

h1(x) = (x + 6) mod 32
x   h   binary  tail
4   10  01010    1
2    8  01000    3
5   11  01011    0
9   15  01111    0
7   13  01101    0
R = 3 -> estimate 2^3 = 8

all 6 hash fns give R = 3 4 2 2 3 3 -> estimates 8 16 4 4 8 8
groups (8,16,4) avg 9.33 , (4,8,8) avg 6.67 -> median = 8
with correction 8 / 0.77351 = 10.34 ; actual = 5
(small stream so estimate is rough, method is meant for millions of items)

common mistakes
- counting leading zeros instead of trailing
- writing estimate as R instead of 2^R
- taking R of one element instead of max over stream

viva
- bloom vs fm : bloom = is x in set ; fm = how many distinct
- memory : only max R per hash function
- other stream algos : DGIM (count 1s in window), count-min sketch, reservoir sampling
