This should be labeled as a PDF
Yes. Added.
Scalable Bloom Filters (2007) [pdf]
21–30 of 39 posts
Re: Scalable Bloom Filters (2007) [pdf]
#22Can someone help me understand the query part?
It says that a query is done on each BF, even on the ones that were added after the initial storage. So suppose we have only 2 iterations. In the first BF, there's k0 hash functions and in the 2nd (iteration) BF, there's now k1 hash functions.
So naturally, an item is stored using the k0 hash functions. But in order to query, I run against k1 hash functions which is a larger set. If any one of the k1-k0 extra hash functions returns 0, won't that be a false negative?
Re: Scalable Bloom Filters (2007) [pdf]
#23this is a kind of tangential comment/rant : but to me it seems that research papers _must_ be, for lack of a better term, runnnable . i would, and hopefully others as well, like to, replicate all these wonderful results that are advertised in these papers. without that, they are all just advertisements of scholarship rather than scholarship themselves. a set of instructions + environment which generated these figures…
Agreed. First time this was in HN, I wanted to understand both types of bloom filters, so I wrote https://github.com/mceachen/bloomer.
Re: Scalable Bloom Filters (2007) [pdf]
#24Hacker news loves upvoting articles about bloom filters (and Bayesian probability - its on the front page again this evening.) Personally I've never found a use for either of them in practice.
I thought I might have a use for them in practice, but it turns out they are only useful for sparse datasets — if your dataset can be fully populated, a bitmap is more efficient (for any reasonable degree of accuracy).
I don't see how this is true. The bitmap vs bloom-filters argument is more about accuracy (BFs have a one-way error, Bitmaps do not). The datasets' density/sparsity has no bearing on efficiency, AFAIK. Would you elaborate your reasoning?
Re: Scalable Bloom Filters (2007) [pdf]
#25Can someone help me understand the query part? It says that a query is done on each BF, even on the ones that were added after the initial storage. So suppose we have only 2 iterations. In the first BF, there's k0 hash functions and in the 2nd (iteration) BF, there's now k1 hash functions. So naturally, an item is stored using the k0 hash functions. But in order to query, I run against k1 hash functions which is a la…
Yes, you are right - you have to query each filter.
To keep the contract of the bloom filter, a "no" can only come if ALL filters return no. So if one of the filters return 0 and the other returns 1, the answer is maybe (i.e. a yes with some false positive probability). If we instead answered no, it would be a false negative as you stated, so we can't do that. This paper doesn't defeat this property of bloom filters.
The cool insight in this paper is that how you choose the new filter size allows for a relatively nice tradeoff of "wasted" size, and a target for the effective false positive ratio, even in the face of growth. We are increasing the probability for false positives, but depending on how you pick the sizes, you can do better than if you simply allocated another bloom of the same size, forever and ever.
(When I say "wasted" size, I mean the extra bits you need to get a certain false positive ratio, when you compare it to a properly sized filter from the get-go. In essence, you're paying some overhead when you get to a certain size. In exchange, you do not need to have guessed the size correctly / allocated all that memory from the get-go.)
Re: Scalable Bloom Filters (2007) [pdf]
#26Earlier quoted context omitted.
I thought I might have a use for them in practice, but it turns out they are only useful for sparse datasets — if your dataset can be fully populated, a bitmap is more efficient (for any reasonable degree of accuracy).
I don't see how this is true. The bitmap vs bloom-filters argument is more about accuracy (BFs have a one-way error, Bitmaps do not). The datasets' density/sparsity has no bearing on efficiency, AFAIK. Would you elaborate your reasoning?
Here's a reduced example. I want to ask whether an incoming 16 bit number is in my set. I can make a bitmap that answers that question perfectly in 8KB :)
So I'm assuming what the parent meant by sparse is, things where the universe is much much bigger, and therefore the things in your set are a sparse proportion of the universe. For instance, in deduplication, we use at least 160 bit hash functions...and that bitmap isn't looking good for us!
Re: Scalable Bloom Filters (2007) [pdf]
#27Earlier quoted context omitted.
They have one use: as a fast check for whether you should bother with a slower check. Bloom filters are basically a sort of a pre-cache.
They actually have other uses, like measuring file similarity in sdhash and dimensionality reduction in machine learning.
Interesting. Thanks!
Re: Scalable Bloom Filters (2007) [pdf]
#28Hacker news loves upvoting articles about bloom filters (and Bayesian probability - its on the front page again this evening.) Personally I've never found a use for either of them in practice.
We used bloom filters at RSA Security to develop space-efficient indexing.
Problem: For a network security product, we stored security data in a distributed, hierarchical, time-series, key-value database. Creating a full inverted index to improve the performance of our SQL-like querying engine would increase storage space requirements forcing customers to buy more storage hardware.
Solution: Bloom filters helped us to perform fast probabilistic lookups to check whether a specific value for a specific key has a high likelihood of being in a particular database block while requiring lesser storage. During query time, if the bloom filter says that the value does not exist in a specific block, we safely skip that block thus reducing search time. If the bloom filter says that the value might exist in a specific block, then we parse that block to see if the value indeed exists. With 4 hash functions (k = 4), 10007 bits per bloom filter (m = 10007), and a new bloom filter for every 1000 values (n = 1000), we achieved a theoretical false-positive rate of only 1.18% ((1 - e(-k * n / m)) k = 0.0118). In practice, over a period of 5 years, we found that the actual false positive rate varied between 1.13% and 1.29%.
Summary: Overall, bloom filters led to a 30-fold increase in query performance while requiring only 1/25th the space a full inverted index would take.
Re: Scalable Bloom Filters (2007) [pdf]
#29Earlier quoted context omitted.
I thought I might have a use for them in practice, but it turns out they are only useful for sparse datasets — if your dataset can be fully populated, a bitmap is more efficient (for any reasonable degree of accuracy).
I don't see how this is true. The bitmap vs bloom-filters argument is more about accuracy (BFs have a one-way error, Bitmaps do not). The datasets' density/sparsity has no bearing on efficiency, AFAIK. Would you elaborate your reasoning?
Your parent comment is correct.
Consider the use case of space-efficient indexing. A negative response from bloom filter would help the querying engine to skip blocks of data that do not contain the value being searched.
If the density of the value is low (i.e., occurs in a small percentage of data blocks), then we can skip a large number of data blocks with the help of bloom filters. But if the density of the value is very high, it implies that the value occurs in most of the data blocks, therefore we would be forced to look at most of the data blocks. In the high density scenario, bloom filters would not provide a significant advantage in reducing the query time, although it would still provide a significant advantage in reducing storage space requirements.
See https://news.ycombinator.com/item?id=16435521 for an example of such a use case.
Re: Scalable Bloom Filters (2007) [pdf]
#30Hacker news loves upvoting articles about bloom filters (and Bayesian probability - its on the front page again this evening.) Personally I've never found a use for either of them in practice.
I use them for natural language processing. There are cases where the performance increase is enormous (as in I wouldn't be able to afford the computation without them) and the downside of false positives is or can be made irrelevant.