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?
That was my thinking too, I don’t see any reason to not just mask out say 9 bits at a time to address a cache line (you could get 7 hash functions that way from a 64-bit word, and maybe one or two of them could be used to pick the cache line used by the remaining hash functions).
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:
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
That was my thinking too, I don’t see any reason to not just mask out say 9 bits at a time to address a cache line (you could get 7 hash functions that way from a 64-bit word, and maybe one or two of them could be used to pick the cache line used by the remaining hash functions).
score 1 · canonical