Since the submitter is the author:<p>> 6 days after I started to write this post, it is proved that the math behind false positive probability was wrong for 50 years<p>This isn't true.<p>The "Bloom math is wrong!" clamor started at least 12 years ago with [1], which brazenly cites Bloom, then proceeds to give an analysis of Knuth's subtly different filter from TAOCP instead.<p>There are issues with [1], but its exact false positive formula was eventually proven correct. Its argument is incompatible with Bloom's original filter, though, and Knuth explicitly states that the false positive formula he gives is approximate.<p>In other words, nothing was proved wrong. The analysis doesn't apply to Bloom and doesn't contradict Knuth.<p>Now, [1] may be the first paper to give the exact false positive formula for Knuth's filter (and Bloom's was given in 1979 by [2]), so it's not entirely without merit. But in practice none of this matters anyway. At useful sizes the approximations are accurate. Knuth's is a lower, Bloom's an upper bound, and the two become functionally equivalent very quickly.<p>1. <a href="https://cglab.ca/~morin/publications/ds/bloom-submitted.pdf" rel="nofollow">https://cglab.ca/~morin/publications/ds/bloom-submitted.pdf</a><p>2. Algorithm-A in <a href="https://sci-hub.tw/10.1109/proc.1979.11543" rel="nofollow">https://sci-hub.tw/10.1109/proc.1979.11543</a>
The article has a good implemenetation, but when reading about Bloom filters, I often see claims about optimality, but it does not say optimial for what. In this example, an optimal Bloom filter for 1M elements does 7 lookups in a bitvector of 1.14MB, which is usually 3 to 5 L2 cache misses (with 256KB or 512KB cache).<p>But looking up the 1M elements directly in a BTree will usually lead to 1-2 cache misses and depending on the data element size, may even fit in the L3 cache. Then, what is this bloom filter saving me from?
Bing's BitFunnel paper is a pretty interesting read. The parts about scaling bloom filters by flipping their axis and using multiply filter layers is particularly of note if you are actually interested in production use.<p><a href="https://danluu.com/bitfunnel-sigir.pdf" rel="nofollow">https://danluu.com/bitfunnel-sigir.pdf</a>
“This looks really promising! A Bloom Filter that represents a set of million items with a false-positive rate of 0.01 requires only 9585059 bits and 7 hash functions.“<p>My immediate thought here was that this wasn't very space efficient as it requires over 9 bits per item?<p>I'd have to dig more into this though to confirm or deny my intuition!<p>Edit: this page agrees with the blog post and shows some interesting graphs <a href="https://hur.st/bloomfilter/?n=1000000&p=0.01&m=&k=" rel="nofollow">https://hur.st/bloomfilter/?n=1000000&p=0.01&m=&k=</a>
Bloom filters confused me at first, but they're really cool. I like to think of bloom filters with a (oversimplified) physics analogy. When you collide two particles together, other smaller particles come flying out of the explosion. You measure their tracks with a film. If you keep smashing particles together, eventually the film will be saturated and you will basically lose the ability to ascertain with confidence whether or not two specific particles were smashed together.
I've read that some old factories used bloom filters to quickly look up where a worker is. At the morning they pressed three buttons on a wall that represented a workshop, and with a knowledge of these numbers one could check if that person was not in the workshop.<p>The similar technique but in a reverse I've seen in a factory myself, when 5-7 closest people at the gate queue pressed their buttons, and a controller collected their outstanding passes from the other side and then checked against their faces very quickly. That greatly saved time in a queue.
> hashers: [DefaultHasher; 2],<p>Bikeshedding a little, but that probably shouldn't be an array. hashers[0] and hashers[1] aren't semantically equivalent and the only usage that array gets is just getting element by index. Something like `startHasher` and `stepHasher` would probably better convey intent.
Very nice read. I knew bloom filters but the detailed explanation and the rust code (almost Greek to me) were very nicely explained. I also read through the linked page of Kiran.
I think most people who took CS classes in college are familiar with hash table implementations, but perhaps not bloom filters.<p>Bloom filters are just chaining hash tables, without the chain.
I like hand drawn diagrams and use them a lot, especially since work gave me an ipad, but whenever I see them in ‘high-production-value’, well researched and edited blog posts like this, I am reminded that it still seems to be a hard problem to quickly produce good quality vector diagrams (with foss software).<p>Has the state of the art moved on recently, or is it still a case of fighting TikZ?