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.