Exploring Bloom Filters
A data structure that tells you whether a desired item is definitely not in the set you're searching. Used as a first-point-of-contact in retrieving information because the dataset is small and fast compared with a direct search.
Exercise
Go to this lovely visualisation https://www.jasondavies.com/bloomfilter/ .
This particular bloom filter has 50 bits and uses three functions – every time you add a key, the filter will (deterministically) set 3 of the 50 bits. The check on the right lets you see whether a particular key is NOT in the set, by seeing whether the bits for that key are set, or not.
Play with it – add keys, see the graph, check the response of the algorithm with the keys you've added and with terms you've not added.
Track how your experiments change with what you see – keep an eye on what you're doing, and what you're looking for, and any model (hypothesis, rational, plausible guess) that you might be holding in mind.
Debrief
What did you observe? How did that change your experiment? How did you lean from your experiments?
Let's reflect on this from the point of view of testing and exploring.
OR
What do you know now about bloom filters – how might you test them?
Sources
Contributors to Wikimedia projects
Comments
Sign in or become a Workroom Productions member to read and leave comments.