Ever searched for a word in a dictionary and hoped it wouldn't lead to a wild goose chase?
Image: Nandanupadhyay, CC BY-SA 3.0, via Wikimedia Commons
Bloom filter
Ever searched for a word in a dictionary and hoped it wouldn't lead to a wild goose chase?
Imagine you're trying to find a specific word in a massive dictionary with limited memory on your computer.
You want to quickly check if a word is in the dictionary without loading the whole thing into memory. A Bloom filter helps by using less space and letting you know if a word might be there or definitely isn't.
Example
You have a Bloom filter with a memory capacity for 100 words. You add 90 words with simple rules and 10 with complex ones. When you search for a word, the filter tells you if it's possibly in the dictionary or definitely not, saving you from a memory overload.
Remember this
A Bloom filter lets you quickly guess if a word is in your dictionary without needing all the words stored in memory.
Text adapted from Wikipedia, licensed under CC BY-SA 4.0.
Related concepts
Hierarchical navigable small world
HNSW is an efficient ANN search algorithm
classifier-free guidance does: interpolates between conditional and unconditional generation
"Classifies samples as either conditioned or unconditioned, guiding generation towards desired outcomes."
Large language model
LLMs can generate, summarize, translate, and analyze text in many contexts
WordPiece tokenization does: similar to BPE but uses likelihood instead of frequency
WordPiece tokenization splits words into subwords based on token likelihood rather than frequency
rejection sampling does: samples from target by accepting/rejecting proposals
How do you randomly pick a number following a strange rule?
Greedy vs beam search decoding: greedy picks best token, beam maintains k candidates
Ever wondered why Google Search sometimes shows you the top results first?
Swipe through 100 ML concepts daily
Open Pocket Polymath