Bloom Filters
A Bloom filter is a space-efficient probabilistic data structure that is used to test whether an element is a member of a set.
Bloom Filters
it is a probabilistic data-strucutre and help to identify 2 major things: 1. Definitely String not exist 2. String might exist
How it works
index: 0,1,2,3,5,6,7,8,9 bits: 0,0,1,0,0,0,1,0,1,1
hash1("savage") = 2
hash2("savage") = 6
hash3("savage") = 8
hash4("savage") = 9
hash1("rocking") = 2
hash2("rocking") = 4
hash3("rocking") = 8
hash4("rocking") = 9
savage - 2 , 6 , 8 , 9 rocking - 2 , 4 , 8 , 9
savage - 2 , 6 , 8 , 9 roger - 2 , 6 , 8 , 9
definitely not exist
How instagram find there username? how spotify search a single song in a users playlist
You want to check: "Does this username exist already?"
1. if it is saying no 100% -> it is not existing in the database. 2. if it is saying yes -> maybe exist in db
Bloom Filter
we can create this username it is not in bloom filter
lets check in database/cache
Why Not 1. TRIE : good for prefix search will take lot of space and [just to tell username exist or not] 2. HASHMAP/CACHE/REDIS : need lot os space lot of memory, lot of money 3. DB : O(n) lookup very slow - after indexing also it will still be slow
Scale Mathematics
Bloom filter size depends on 3 things: n = number of items you're storing (e.g., 2 billion Gmail addresses) p = how many false positives you're okay with (e.g., 1%) From n and p, you calculate: m = size of bit array k = number of hash functions Formulas (don't worry, just for intuition): m = -(n * ln(p)) / (ln(2)^2) k = (m/n) * ln(2)