The headline is misleading if you are familiar with bloom filters.
TL;DR: the interesting thing here isn't decreased false positive rate (multibit bloom filters are common), but the idea to put the relevant bits together. Basically you use a hash to pick a chunk of bits (32 bits in this case), then use more hashes to pick the bits within this chunk.
It is a tradeoff between accuracy (completely independent hashes would be less likely to have collisions leading to false positives) and performance (all relevant bits for the object you're looking up will be together and the lookup will trigger at most one cache miss / memory access).
2 Comments
Markaos@discuss.tchncs.de · 6 pts · 182d
The headline is misleading if you are familiar with bloom filters.
TL;DR: the interesting thing here isn't decreased false positive rate (multibit bloom filters are common), but the idea to put the relevant bits together. Basically you use a hash to pick a chunk of bits (32 bits in this case), then use more hashes to pick the bits within this chunk.
It is a tradeoff between accuracy (completely independent hashes would be less likely to have collisions leading to false positives) and performance (all relevant bits for the object you're looking up will be together and the lookup will trigger at most one cache miss / memory access).
MarekKnapek@programming.dev · 3 pts · 180d
Instead of 32 bits they could use the entire cache line. It is loaded from RAM to CPU anyway. It is 64 bytes / 512 bits.