Exp 6 - Bloom filter (bloom.R)

what it answers : "have I seen this item before?"  (set membership) using little memory
how             : bit array of m bits (all 0) + k hash functions
  insert x  -> compute k hashes, set those k bits to 1
  check  x  -> compute k hashes, if ANY bit is 0 -> definitely not present
                                  if ALL bits are 1 -> maybe present
no false negatives (bits are never reset) but false positives can happen
normal bloom filter cannot delete (clearing a bit may remove other items) -> counting bloom filter can
uses: spam / url blacklist, hbase & cassandra skip disk reads, caches, username taken check

formulas (n = items inserted, m = bits, k = hashes)
  false positive p = (1 - e^(-k*n/m))^k
  best k           = (m/n) * ln 2
  bits needed      = -n * ln p / (ln 2)^2

-------- dry run of bloom.R (m = 16, k = 3) --------
word     h1  h2  h3
hadoop    8   6  14
spark    14  11  11      (two hashes same -> allowed)
hive      4   5  14
kafka     9   3  16
bits = 1 at : 3 4 5 6 8 9 11 14 16   -> 9 of 16

check
pig   -> 1 3 5     bit 1 is 0      -> definitely not present
mongo -> 2 13 11   bit 2 is 0      -> definitely not present
avro  -> 16 11 14  all are 1       -> maybe present  = FALSE POSITIVE
         (16 set by kafka, 11 by spark, 14 by hadoop) never inserted, bits set by other words

theoretical p = (1 - e^(-3*4/16))^3 = 0.1469 ; observed rate on 2000 random words ~ 0.19

-------- integer version (second part of bloom.R) --------
m = 10, h1(x) = x mod 10, h2(x) = (2x + 3) mod 10
insert 5  -> 5, 3
insert 11 -> 1, 5
insert 17 -> 7, 7          bits set: 1 3 5 7
check 20  -> 0, 3   bit 0 is 0  -> not present
check 15  -> 5, 3   both 1      -> maybe present (false positive, 15 never inserted)
check 7   -> 7, 7   both 1      -> maybe present (false positive)

viva
- false negative possible? no
- why no delete? clearing a bit can make another item look absent
- filter fills up -> more 1s -> false positive rate goes up towards 100%
- bigger m -> fewer false positives, more items n -> more false positives
