The linked paper describes a “Standard Bloom Filter” as using k hash functions and a modulo.

If I was to build a simple Bloom filter:

• Size my bit array to a power of two so I can use a truncation / mask instead of a comparatively expensive modulo. (Obviously less flexible, but if you have a use case where the next lower power of two bit array size has too high a false positive rate and the next larger uses too much memory… your cache sizing is way more precise than anything I’ve worked on.)
• Shift and mask the output of one hash function to generate my “k” hashes. E.g. the lowest 16 bits are h1, next higher 16 are h2, etc. Can get three 21 bit numbers from a 64 but hash, and if that’s not enough, many hash functions can output 128 bits or more for no extra cost. For a good hash function, any positions should be as independent as different hash functions would be.

Perhaps those are mentioned later in the paper or in the references, but weren’t in the related work or the beginning of the design section before the math got too dense for me to skim on my phone.

While there might be other e.g. locality benefits to this scheme, making a “one hash Bloom filter” seems trivial. Is there something I’m missing where the simple scheme wouldn’t actually work?

score 1 · canonical

For the Bluesky backend, we essentially do a SELECT * FROM blocks, mutes, list items, etc. every time one the processes starts, and add all the items to the bloom filter

If you’re constructing a bloom filter but not querying it yet, I think you can split that across many threads without contended locks or atomics, by having each thread have its own private bitmap and setting bits in that. Then when all threads have finished inserting items, you bitwise OR together all the bitmaps.

There’s also a real time atproto firehose consumer inserting items in to bloom filters (even during process startup), so there is a race condition if you’re not careful.

Add another bitmap for events that are showing up during process start and bitwise OR that in at the end, too.

Alternatively if you happen to have two bitmaps and no opportune time to merge them, you could keep querying both and returning 1 where either bitmap has a 1.

score 1 · canonical

There’s another fun optimization from Daniel Lemire that allows you to select which block to check with a single MUL instruction rather than modulo, which requires an expensive division instruction.

I’m pretty sure this doesn’t work together with using one hash.

I haven’t even glanced at the paper, but I would assume that it claims that (x % p, x % q) is a good pair of hashes because x % p and x % q are independent for p, q coprime, or something along those lines. In other words, knowing x % p doesn’t tell you anything about the distribution of x % q. (You can prove that via Chinese Remainder Theorem or more elementary methods.)

But Lemire’s approach with using (x * p / 2^n, x * q / 2^n) doesn’t have this property. Say, if p < q, x * q / 2^n = 0 implies x * p / 2^n = 0. So your hashes are dependent and the bounds break down.

I also think it’s worth talking about hash sizes here. (x % p, x % q) are only independent if x is a multiple of p * q (though it’s practically independent if x is much greater than p * q). If you use k levels in the Bloom filter, each of size approx. m, that means the hash space should be at least close to m^k, i.e. k log m bits. But with double hashing, you only need 2 log m bits in total (log m for each hash). So you might be weakening some bounds if you use modulo with an insufficiently large hash space.

score 1 · canonical