Bloom Filter
Goals
Students will understand elements of the insertion and search algorithms for bloom filters in hash tables.
Video
Materials
One deck of Menagerie cards.
Setup
Give each student a set of 0-7 number cards. Set these cards in a row, ordered from 0 on the left to 7 on the right.
Shuffle the animal cards from the deck and deal each student 6 cards.
Each student will shuffle their 6 cards, and place them in a face-down pile to their left.
Give each student a pile of chits.
Algorithm
Insertion
Repeat these steps for each card in the face-down pile.
-
Flip over a card from your face-down pile, to become the face-up card.
-
On the face-up card, look at the first number with a gold background. If there is not a chit on the matching number card in your row, place a chit on it.
-
On the face-up card, look at the second number with a white background. If there is not a chit on the matching number card in your row, place a chit on it.
Lookup
-
Check the number cards in your row that match the gold number and that match the white number of the card you are looking for, and
-
If there is a chit on both number cards, the card you are looking for is likely in the bloom filter.
-
If there is one chit or no chit on either number card, the card you are looking for is not in the bloom filter.
-
Example
Insertion Example
Add Wolf
The first card flipped up is the Wolf, the first number with a gold background is 7. There is not a chit on the number card 7 in our row so we will place a chit on it. The second number with a white background is 6. There is not a chit on the number card 6 in our row so we will place a chit on it.
Add Meerkat
The next card flipped up is the Meerkat, the first number with a gold background is 7. There is already a chit on the number card 7 so we continue. The second number with a white background is 3. There is not a chit on the number card 3 in our row so we will place a chit on it.
Add Walrus
The next card flipped up is the Walrus, the first number with a gold background is 6. There is already a chit on the number card 6 so we continue. The second number with a white background is 2. There is not a chit on the number card 2 in our row so we will place a chit on it.
Add Rhinocerous
The next card flipped up is the Rhinocerous, the first number with a gold background is 5. There is not a chit on the number card 5 in our row so we will place a chit on it. The second number with a white background is 6. There is already a chit on the number card 6 so we continue.
Add Badger
The next card flipped up is the Badger, the first number with a gold background is 6. There is already a chit on the number card 6 so we continue. The second number with a white background is 5. There is already a chit on the number card 5 so we continue.
Add Lion
The next card flipped up is the Lion, the first number with a gold background is 6. There is already a chit on the number card 6 so we continue. The second number with a white background is 4. There is not a chit on the number card 4 in our row so we will place a chit on it.
Lookup Example
Lookup Walrus
When we hash the Walrus, The first number with a gold background is 6 and the second number with a white background is 2. There is a chit on the number card 6 and the number card 2 so it is likely that the bloom filter contains the Walrus.
Lookup Ladybug
When we hash the Ladybug, The first number with a gold background is 4 and the second number with a white background is 0. There is a chit on the number card 4 but not on the number card 0 so the Ladybug is not in our bloom filter.
