Bloom Filters
February 26, 2024
Everyone has a set of tools they use to solve problems. Growing this set helps you to solve ever more difficult problems. In this post, I’m going to teach you about a tool you may not have heard of before. It’s a niche tool that won’t apply to many problems, but when it does you’ll find it invaluable. It’s called a “bloom filter.”
Source: Bloom Filters
Via (as is not uncommon around these parts) Simon Willison this is a deep dive into a type of data structure Bloom Filters. The explanation uses JavaScript.
Bloom filters are a lot like Sets, but they are probabilistic. So when you ask “does this Bloom Filter contain this item” you can answer no definitively, but yes only probabilistically. What good is that? well that probability can be high, and for large sets of items, you can get very significant reductions in size.
So we can trade off the small chance we are wrong with a very significant performance gain.
A great read.
