Can anyone explain how the hash function maps to multiple values in the bit vector? I thought functions cant be one to many.
A function can map multiple inputs to one output but not one input to multiple outputs.
Word-Aligned Bloom Filters
71–80 of 82 posts
Re: Word-Aligned Bloom Filters
#72Earlier quoted context omitted.
Each word in this design is a little bloom filter. It has number of bits (m)=64; number of hashes (k)=5; and going for 1% false positive rate, which per formula (with n being number of items in the filter) in [1] is: fpr = (1 - e ^ -(k * n)/m ) ^ k OP solved for 1% and got n =~ 4. There is exactly 1 hash function (to compute the 64 bit key). 5 bits are pseudo-randomly selected (giving us k=5) and written to an array…
> Each word in this design is a little bloom filter. It's effectively a hash table of bloom filters. > So, you either have to keep track of elements assigned to words (3 bits / word to count 0..4), or you compute a probable value to minimize overloaded array elements One option would be to just directly limit the number of marked bits in each bucket, which seems to correlate better to false positive rate than number…
There is some p probability that a given filter with less than 24 set bits has 4 elements (since some of their bits overlapped). So this approach falls under "compute a probable value" as there is a non-zero probability that some filters have > 4, or even higher. So you will have fpr > 1%. When you count, you have the assurance of fpr For this design, it's just a step or two away from venturing into 3.5 or 7% error rates. And if you simulate it, you'll see a gaussian distribution with mean at theoretical capacity (len x 4) and some standard deviation. By capping bits, we cut a lot of possible cases that exceed the mean, but will not eliminate them. It's pretty straightforward to simulate this and get empirical data to see if their impact (of fp) is acceptable.
Re: Word-Aligned Bloom Filters
#73Earlier quoted context omitted.
> Each word in this design is a little bloom filter. It's effectively a hash table of bloom filters. > So, you either have to keep track of elements assigned to words (3 bits / word to count 0..4), or you compute a probable value to minimize overloaded array elements One option would be to just directly limit the number of marked bits in each bucket, which seems to correlate better to false positive rate than number…
There is some p probability that a given filter with less than 24 set bits has 4 elements (since some of their bits overlapped). So this approach falls under "compute a probable value" as there is a non-zero probability that some filters have > 4, or even higher. So you will have fpr > 1%. When you count, you have the assurance of fpr For this design, it's just a step or two away from venturing into 3.5 or 7% error r…
> There is some p probability that a given filter with less than 24 set bits has 4 elements (since some of their bits overlapped).
> there is a non-zero probability that some filters have > 4, or even higher.
Overlapped bits don't contribute to false positive rate. As a unlikely-but-simple example, consider a filter with 3 items, marking 15 distinct indexes, and a new 'fourth' item whose 5 indexes all align with one of the existing 15 indexes. Adding this new item does not change the filter at all, and so cannot change the false positive rate.
In general the false positive rate (assuming our hash function is good, ie H(X) is independently uniformly random for each X) is the chance that a uniformly random hash passes the filter. For a N bit filter with P bits marked, and K bits per element, that's (P/N)^K (select K random indexes, and check if they're all marked, which they will be with probability P out of N each). Since N and K are fixed, the FPR only depends on the popcount P. A straightforward bloom filter can't depend on the number of items inserted (seperately from the number of marked bits), because that information isn't even present.
Re: Word-Aligned Bloom Filters
#74Can anyone explain how the hash function maps to multiple values in the bit vector? I thought functions cant be one to many.
You're right, A hash function doesn't map to multiple values.
Bloom filters and other probabilistic set membership DS's like Cuckoo filters instead use multiple hash functions to map one input to multiple output values. [1]
The number of hash functions to use depends on the expected false positive probability rate, number of bits in the filter and the number of elements which will be inserted
[1] : https://en.wikipedia.org/wiki/Bloom_filter#Algorithm_descrip...
Re: Word-Aligned Bloom Filters
#75Earlier quoted context omitted.
The main use case I've always seen is to use bloom filters on the client side to reduce traffic to the server looking things up. As you said, you could cache 250 million integers in a gigabyte - but you don't want to bloat your client side implementation by a gigabyte for every bloom filter you use. Also, many times the items are a lot larger than an integer. For example, storing a list of malicious URLs, a common us…
I'm so confused by this use case (the traffic-saving one, not the malicious URL classifier). Why not store the "is-paying-customer" bit in a cookie? What are we using as the user identifier? Where does it come from, if not a cookie? Also, this client-side bloom filter kind of leaks your user database, supposing it's keyed on email addresses and your adversary has a gigantic list of email addresses, or is patient enou…
> Why not store the "is-paying-customer" bit in a cookie?
You shouldn't trust the client. You probably don't want people to get access to paid features with a relatively easy tweak of cookies.
The client-side filter is more suitable for listing, say, malware URLs, as mostly the response is "no" (go ahead) instead of "maybe", which would require a bit more work (like, network requests) to check if it's blocked or not.
Re: Word-Aligned Bloom Filters
#76Earlier quoted context omitted.
Each word in this design is a little bloom filter. It has number of bits (m)=64; number of hashes (k)=5; and going for 1% false positive rate, which per formula (with n being number of items in the filter) in [1] is: fpr = (1 - e ^ -(k * n)/m ) ^ k OP solved for 1% and got n =~ 4. There is exactly 1 hash function (to compute the 64 bit key). 5 bits are pseudo-randomly selected (giving us k=5) and written to an array…
> Each word in this design is a little bloom filter. It's effectively a hash table of bloom filters. > So, you either have to keep track of elements assigned to words (3 bits / word to count 0..4), or you compute a probable value to minimize overloaded array elements One option would be to just directly limit the number of marked bits in each bucket, which seems to correlate better to false positive rate than number…
> You get 6bits * 4elements = 24bits marked, so just call a bin full if it has popcount >= 24.
That should actually be 5bits * 4elements = 20bits marked; I confused bits in a index with number of indexes/bits marked.
Re: Word-Aligned Bloom Filters
#77Earlier quoted context omitted.
> I'm really suspicious about whether this would really work out in most workloads. What kinds of workloads are those? Workloads where the Bloom filter itself fits in cache? > On modern architectures, it's the random memory reference that kills performance Yeah, the whole point of the article is that moving from a traditional Bloom filter to a block Bloom filter is to improve from N random accesses per query/update t…
> to improve from N random accesses per query/update to 1 random access per query/update. I think their concern is that N (nondependent) random accesses can happen in parallel not much more slowly than 1 random access (assuming good speculation and sufficient memory bandwidth).
The N accesses don't need to happen in parallel; they are faster whenever they take place because they need one block in cache rather than the equivalent of k>1 blocks together to be fast (executed from cache) and it is unconditionally much better, even without assumptions about hot and cold keys.
Re: Word-Aligned Bloom Filters
#78I find these optimizations fascinating. Anyone familiar with Lemire likely knows about this, but I listened to a podcast episode[1] with him a few days ago and learned about `simdjson`, the tool he authored that parses JSON at 25x the speed of the standard C++ library.[2][3] It's worth looking at if you're into this sort of thing. 1. https://corecursive.com/frontiers-of-performance-with-daniel... 2. https://www.youtu…
Is this the project? https://github.com/simdjson/simdjson
If so, Ive been following it for a couple years, but I put it out of my mind recently after moving to AMD. I could sware it was an intel only project, but a quick scan of the that git suggests I'm wrong. So either I'm totally missremembering, or AMD support was added later.
Anyway, I cant wait to try that out again. I wonder why most projects don't just use this as their default json parser now?
Re: Word-Aligned Bloom Filters
#79The real reason why people don’t use the blocked bloom filter, is because it’s FPR is much higher + it requires more storage. It has the worst of both worlds.
Re: Word-Aligned Bloom Filters
#80Why 1 word instead of 1 cache line?