Can anyone tell me about a use case in game design?
That's an interesting question. I wonder if there's some potential application in collision detection.
Bloom Filters for the Perplexed
21–30 of 46 posts
Re: Bloom Filters for the Perplexed
#22Earlier quoted context omitted.
you scoff but this is a very thorough presentation of a bloomfilter - very few of these sorts of articles actually cover the computation of the probability bounds.
Yeah, there have been a good number [1] and a steady stream of submissions about Bloom filters (and truly, the inevitable re-riff about Cuckoo filters), but this article is toward the higher end of the quality scale. It's a bit odd that a data structure attracts this kind of attention, but not all of it is about self-discovery, and the fact that people feel writing about them belies the fact that they either consider…
I want to say it started a while ago because some hiring manager asked a question about how someone would do something but had the intended answer as a bloom filter. The interviewee turned to hacker news to vent about it and then it brought enough eyeballs to a somewhat fringe algorithm to self-sustain these types of articles.
Re: Bloom Filters for the Perplexed
#23Can anyone tell me about a use case in game design?
That's an interesting question. I wonder if there's some potential application in collision detection.
If you have a large number of moving parties you could make bloom filters of the tiles they're going to move through and then compare them to cull pairs which will never share tiles along their paths perhaps?
Re: Bloom Filters for the Perplexed
#24How does a Bloom filter with k hash functions hashing to a shared table of m bits compare to just using k hash functions each hashing into its own separate hash table of m/k bits?
Re: Bloom Filters for the Perplexed
#25How does a Bloom filter with k hash functions hashing to a shared table of m bits compare to just using k hash functions each hashing into its own separate hash table of m/k bits?
What you're suggesting sounds like a count min sketch, like a 2D bloom filter.
Re: Bloom Filters for the Perplexed
#26Bloom filters are a nice data structure, and you should absolutely have them in your toolbox, but if you go looking for a reason to use one you are likely to wind up making things worse. The following is not valid reasoning: "Bloom filters are efficient. Therefore if I can find a way to use a bloom filter, my solution will be efficient." The "SSH keys" protocol in the article seems like an example of this. It doesn't…
> The "SSH keys" protocol in the article seems like an example of this. It doesn't make any sense. Why would the server send the client a Bloom filter if the client has already told it what key it wants to check? The server only has to send one bit back to the client! And if the goal is to not trust the server with the client's (public) key, this protocol doesn't accomplish that either.
There is a footnote on the sequence diagram that the key is not sent to the server on the initial request. Rather the client just does a simple GET. Since it's just sending a static file the client could cache the bloom filter.
Re: Bloom Filters for the Perplexed
#27Can anyone tell me about a use case in game design?
This link[0] has an example; so basically almost anything in a game where it has to lookup massive amounts of data (e.g. logs), the example in the article is to quickly check if the user has already seen an item (in a game with thousands of items [e.g because those were pseudo-randomly generated, think RPGs]). But it's easy to think further applications: quickly check if the player already played this chess game before (all pieces where in the same position) to make sure the enemy does something smarter this time (because that time the enemy lost), and such.
[0] https://blog.demofox.org/2015/02/08/estimating-set-membershi...
Re: Bloom Filters for the Perplexed
#28How does a Bloom filter with k hash functions hashing to a shared table of m bits compare to just using k hash functions each hashing into its own separate hash table of m/k bits?
It leads to more false positives. Following the derivation from wikipedia (https://en.wikipedia.org/wiki/Bloom_filter), if we have a bloom filter with k hash functions, m bits, and contains n elements, the probability of a false positive is
(1 - (1 - 1/m)^(kn))^n ~ (1 - exp(-nk/m))^k
With your idea (let's call that Bloom Filter'), we have k hash tables with m/k bits each, so the probability of an element of one of the hash tables being 1 with n elements is 1 - (1 - k/m)^n, so the odds that 1 random position in each of the k hash sets is 1 (i.e. a false positive) is:
(1 - (1 - k/m)^n)^k ~ (1 - exp(-nm/k))^k
Which is very similar, we just switched k/m with m/k inside that exponential. So which has a lower false positive rate for m and k? We do some algebra, assuming that your Bloom Filter' has a lower false positive rate than the regular Bloom Filter, and try to get a contradiction:
(1 - exp(-nm/k))^k 1 - exp(-nm/k) exp(-nk/m) -nk/m m/k m^2 m This is a contradiction, because if we have fewer bits than hash functions, we'll wind up with hash tables of size 0. Thus, Bloom Filter' leads to a worse false positive rate than regular Bloom Filters.
P.S. I just did the math in the last 10 minutes, so there could be mistakes. This also only shows your system is less accurate if it has the same m and k as a regular bloom filter, but maybe your system becomes more accurate if using a different value of k. I'm checking that possibility now.
UPDATE: interesting. I tried to find the optimum value of k given n and m for bloom filter' (for regular bloom filters the optimum k = m / n log(2)). But for bloom filter' there is no local or global minimum, only a maximum at k = m (where everything is a false positive). For k 1 - (1 - 1/m)^n ~ 1 - exp(-n/m)
Re: Bloom Filters for the Perplexed
#29Earlier quoted context omitted.
So, bloom filters are the equivalent of Monads? https://byorgey.wordpress.com/2009/01/12/abstraction-intuiti...
They both seem like fairly easy concepts. I'm not sure why they get so much coverage.
The problem is that Haskell developers like to push monads as the solution to a problem most developers in other languages don't actually have, so discovering the problem that's being solved is the difficult bit.
Of course, this doesn't happen with other niche solutions because other niche solutions don't have an entire popular language which nearly-precisely encodes the problems monads are good at solving.
Re: Bloom Filters for the Perplexed
#30How does a Bloom filter with k hash functions hashing to a shared table of m bits compare to just using k hash functions each hashing into its own separate hash table of m/k bits?
Having many filters is worse, but not hugely so. I believe the problem is reducible to the fact that you'll have many smaller filters thus the random distribution hurts you a bit more.
The key word to google is "blocked bloom filter" e.g. as proposed in http://algo2.iti.kit.edu/documents/cacheefficientbloomfilter...
Here's a nice paper with some improvements http://tfk.mit.edu/pdf/bloom.pdf
We use blocked bloom filters for a couple of reasons, but one major benefit is the memory locality (our "bloom filter" is 32GB or larger, so it's handy & fast to be able to address it with separate "pages" which are really just individual bloom filters.)