Bloom Filter
Probabilistic data structure used like a set that provides:
- No false negatives
- Low false positive rate
What’s a bloom filter?
Simply put, a bit vector of N bits, and a set of K hash functions.
Set operations
Insertion
To insert a value X into a Bloom filter, simply hash it over each one of the K hash functions, and treating the hash outputs as indices into the bit-vector, raise the corresponding bits.
Query
To query for a value X in the Bloom filter, once again hash it over each one o f the K hash functions, and then check whether all of the corresponding bits are raised.
