I had a few ideas and was wondering if they were valid and had any real-world uses. I couldn't really find any other sources for this.
The thing is, blocked bloom filters are faster for member checks because they require only one memory access, whereas the traditional implementation (like this one) is faster for non-member checks because it can quickly reject after 1-2 bits. I was wondering: since in the bitvec implementation all calculations happen in u64 chunks, updating or checking a single bit technically requires 64 bits of computation. If we go with a hybrid approach of, let's say, 2 or 3 bits per u64 chunk, and having multiple such chunks per item, we could get, in theory, 2-3x faster member checks, as we look up that much less memory, and also faster/identical non-member checks. Could this further optimize bloom filters?
I had a few ideas and was wondering if they were valid and had any real-world uses. I couldn't really find any other sources for this.
The thing is, blocked bloom filters are faster for member checks because they require only one memory access, whereas the traditional implementation (like this one) is faster for non-member checks because it can quickly reject after 1-2 bits. I was wondering: since in the bitvec implementation all calculations happen in u64 chunks, updating or checking a single bit technically requires 64 bits of computation. If we go with a hybrid approach of, let's say, 2 or 3 bits per u64 chunk, and having multiple such chunks per item, we could get, in theory, 2-3x faster member checks, as we look up that much less memory, and also faster/identical non-member checks. Could this further optimize bloom filters?