Interactive Demo of Bloom Filters
jasondavies.com
Interactive Demo of Bloom Filters
1–10 of 56 posts
Re: Interactive Demo of Bloom Filters
#2If you're interested in using Bloom filters in the backend, we (at DCSO) have written efficient and interoperable open-source implementations in Python and Go, also using FNV-1 hashing:
https://github.com/DCSO/bloom (Go version)
https://github.com/DCSO/flor (Python version)
The Go version comes with a command line tool that allows you to use Bloom filters on the shell.
Re: Interactive Demo of Bloom Filters
#3You don't need more than one hash function. Just append an incrementing token onto the input before each successive hash.
Re: Interactive Demo of Bloom Filters
#4obligatory mention that if you are interested in this you should also know about cuckoo filters:
Re: Interactive Demo of Bloom Filters
#5If anyone just wanted to see a collision:
a
2
c
fRe: Interactive Demo of Bloom Filters
#6obligatory mention that if you are interested in this you should also know about cuckoo filters: https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf https://en.wikipedia.org/wiki/Cuckoo_hashing
...and a shameless plug for my (WIP) Redis Module that doesn't implement a "bloomy" interface, for once
Re: Interactive Demo of Bloom Filters
#7If anyone just wanted to see a collision: a 2 c collides with: f
Another one is
1111
collides with
ab
Re: Interactive Demo of Bloom Filters
#8> Unfortunately I can't use the 64-bit trick in the linked post as JavaScript only supports bitwise operations on 32 bits.
This could be a good use case for WebAssembly, which supports 64-bit math natively.
Re: Interactive Demo of Bloom Filters
#9You don't need more than one hash function. Just append an incrementing token onto the input before each successive hash.
> Just append an incrementing token onto the input before each successive hash.
But that's a new hash function then.
Re: Interactive Demo of Bloom Filters
#10obligatory mention that if you are interested in this you should also know about cuckoo filters: https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf https://en.wikipedia.org/wiki/Cuckoo_hashing
Do you have a tldr for how/when it is better than bloom filters?