Bloom Filters: Students at Some State University (SSU) select very bad passwords
ID: 3751455 • Letter: B
Question
Bloom Filters: Students at Some State University (SSU) select very bad passwords. The system administrator decided to use a Bloom Filter to prevent students from using the passwords “cat, dog, fish, and bear”. The Bloom Filter uses 3 hash functions (H1, H2, H3) and 10 bits in the hash table. When the hash functions are applied to the prohibited passwords, the results are:
H1(cat) = 8 H2(cat) = 1 H3(cat) = 2
H1(dog) = 1 H2(dog) = 9 H3(dog) = 1
H1(fish) = 2 H2(fish) = 8 H3(fish) = 2
H1(bear) = 2 H2(bear) = 4 H3(bear) = 1
Question 1A) Show the resulting Bloom Filter by marking each bit as either 0 or 1.
Bit 0
Bit 1
Bit 2
Bit 3
Bit 4
Bit 5
Bit 6
Bit 7
Bit 8
Bit 9
A student selects the password “mouse”. Note this not a prohibited password. Before the password is accepted, it will be checked against the Bloom Filter. Hash functions H1 and H2 are applied to “mouse” and the results are:
H1(mouse) = 4 H2(mouse) = 8 H3(mouse) = ______
Bit 0
Bit 1
Bit 2
Bit 3
Bit 4
Bit 5
Bit 6
Bit 7
Bit 8
Bit 9
Explanation / Answer
Solution for the problem is given below, please comment if any doubts:
1A)
The Bloom Filter initially contains all bits set as 0.
Bit 0
Bit 1
Bit 2
Bit 3
Bit 4
Bit 5
Bit 6
Bit 7
Bit 8
Bit 9
0
0
0
0
0
0
0
0
0
0
Adding each word to the bloom filter sets the corresponding bits produced by the hash functions as 1.
Here the first word cat produces hash values 8, 1, 2` for H1, H2 and H3 respectively.
Thus set the bit 1,2 and 8 in the bloom filter as 1.
Now the blue filter looks like as below.
Bit 0
Bit 1
Bit 2
Bit 3
Bit 4
Bit 5
Bit 6
Bit 7
Bit 8
Bit 9
0
1
1
0
0
0
0
0
1
0
Now the addition of “dog” will make the bit 9 as “1” since other hash values corresponding bits are set already.
The adding “fish” will not add any extra bits as “1” since “2” and 8” are set already.
Adding “bear” will add bit 4 as 1.
Now final bloom filter will be:
Bit 0
Bit 1
Bit 2
Bit 3
Bit 4
Bit 5
Bit 6
Bit 7
Bit 8
Bit 9
0
1
1
0
1
0
0
0
1
1
The “mouse” produces the H1 hash as “2” and H2 hash function as “8”.
Now since it is not prohibited password, the H3 should be either “0”, “3” “6” or “7”.
Bit 0
Bit 1
Bit 2
Bit 3
Bit 4
Bit 5
Bit 6
Bit 7
Bit 8
Bit 9
0
0
0
0
0
0
0
0
0
0