5 ms·

Hacker news loves upvoting articles about bloom filters (and Bayesian probability - its on the front page again this evening.) Personally I've never found a us

Hacker 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.

hatred 9y ago
They are upvoted because they are extremely nifty and useful :) Check out their usage in Cassandra: http://cassandra.apache.org/doc/latest/operating/bloom_filters.html http://cassandra.apache.org/doc/latest/operating/bloom_filte... There should be many more you can find via quick googling.
deleted 9y ago
[deleted]
deleted 9y ago
[deleted]
0xCMP 9y ago
It's used in this awesome extension to know if a page has been submitted to HN before without making any network requests. https://chrome.google.com/webstore/detail/hacker-news-filter/agohmjkdphojdlhkjejgmoicdpnlajam https://chrome.google.com/webstore/detail/hacker-news-filter...
biesnecker 9y ago
I’ve used them in production several times, recently when I needed to quickly check to see if a set of numbers were likely all the IDs of a particular kind of object, where the ID space is 64-bit ints and the population is in the hundreds of millions. We didn’t need perfection, just a bound error rate and predictable memory consumption, and a pre-loaded BF was perfect in this role.
peteretep 9y ago
Any in fact anything that sounds sort of computer sciencey.
loeg 9y ago
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).
- suj1th 9y ago
  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?
  - cmurphycode 9y ago
    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!
    - loeg 9y ago
      The other half of it is, your hypothetical set contains over 2^15 individual entries (i.e., it's not sparsely populated). (My use case was tracking allocated blocks in a filesystem, in an application where probabilistic results would have been adequate. It is perfectly valid for 100% of blocks to be allocated, so the required vector size for a bloom filter would be longer than the same-size bitvector.)
  - susam 9y ago
    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 https://news.ycombinator.com/item?id=16435521 for an example of such a use case.
traek 9y ago
Bloom filters are popular mostly because they’re clever, but they can also be useful. E.g. Google Chrome’s safe browsing feature used Bloom filters to check whether a site might be flagged for malware, and if necessary query Google to check if it is actually flagged. It would have been impractical to download the full safe browsing dataset to every client, and also impractical to query Google for every single site visited. Bloom filters were a good solution (note: they’ve since moved to a custom data structure[1] which is also interesting.) [1] https://bugs.chromium.org/p/chromium/issues/detail?id=71832 https://bugs.chromium.org/p/chromium/issues/detail?id=71832
btown 9y ago
Extremely useful for anyone doing real-time analytics or filtering. Answering "has this person visited this page before" or "how many distinct people have visited this page/website" can be done exactly with map-reduce or streaming pipelines, but if you want an immediate answer with low latency and can tolerate false negatives/bounded inaccuracy, you can simply keep a Bloom filter or HyperLogLog in memory. For example, see the top comment here: https://news.ycombinator.com/item?id=12124722 https://news.ycombinator.com/item?id=12124722
deleted 9y ago
[deleted]
dsacco 9y ago
> Personally I've never found a use for either of them in practice. One of my servers batch downloads approximately 550GB of data per day. I use a bloom filter to deduplicate the file significantly faster than naive Unix sort or awk ‘!X[$0]++’. It also has superior asymptotic complexity.
cryptonector 9y ago
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.
- FreakLegion 9y ago
  They actually have other uses, like measuring file similarity in sdhash and dimensionality reduction in machine learning.
  - cryptonector 9y ago
    Interesting. Thanks!
susam 9y ago
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.
3131s 9y ago
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.
- Radim 9y ago
  Case in point, collocation detection over very large corpora: https://github.com/RaRe-Technologies/bounter#example-on-the-english-wikipedia https://github.com/RaRe-Technologies/bounter#example-on-the-... Reduces RAM requirements some 31x times when automatically detecting common multiword expressions (e.g. "New York", "network license" or "Apache Hadoop"), which is significant.
  - 3131s 9y ago
    Yep, I load an enormous list of lexemes (including multiword expressions) into a bloom filter and use it for text segmentation.
foo101 9y ago
> Hacker 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. Perhaps that speaks about the type of work you are involved in rather than about the Hacker News community?
jxub 9y ago
We use Bloom filters at Datamaran (https://www.datamaran.com https://www.datamaran.com) to check if the news site source is in one of the ones we follow quickly.

Hacker 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.

hatred 9y ago

They are upvoted because they are extremely nifty and useful :) Check out their usage in Cassandra: http://cassandra.apache.org/doc/latest/operating/bloom_filters.html http://cassandra.apache.org/doc/latest/operating/bloom_filte... There should be many more you can find via quick googling.

deleted 9y ago

[deleted]

deleted 9y ago

[deleted]

0xCMP 9y ago

It's used in this awesome extension to know if a page has been submitted to HN before without making any network requests. https://chrome.google.com/webstore/detail/hacker-news-filter/agohmjkdphojdlhkjejgmoicdpnlajam https://chrome.google.com/webstore/detail/hacker-news-filter...

biesnecker 9y ago

I’ve used them in production several times, recently when I needed to quickly check to see if a set of numbers were likely all the IDs of a particular kind of object, where the ID space is 64-bit ints and the population is in the hundreds of millions. We didn’t need perfection, just a bound error rate and predictable memory consumption, and a pre-loaded BF was perfect in this role.

peteretep 9y ago

Any in fact anything that sounds sort of computer sciencey.

loeg 9y ago

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).

suj1th 9y ago
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?
- cmurphycode 9y ago
  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!
  - loeg 9y ago
    The other half of it is, your hypothetical set contains over 2^15 individual entries (i.e., it's not sparsely populated). (My use case was tracking allocated blocks in a filesystem, in an application where probabilistic results would have been adequate. It is perfectly valid for 100% of blocks to be allocated, so the required vector size for a bloom filter would be longer than the same-size bitvector.)
- susam 9y ago
  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 https://news.ycombinator.com/item?id=16435521 for an example of such a use case.

traek 9y ago

Bloom filters are popular mostly because they’re clever, but they can also be useful. E.g. Google Chrome’s safe browsing feature used Bloom filters to check whether a site might be flagged for malware, and if necessary query Google to check if it is actually flagged. It would have been impractical to download the full safe browsing dataset to every client, and also impractical to query Google for every single site visited. Bloom filters were a good solution (note: they’ve since moved to a custom data structure[1] which is also interesting.) [1] https://bugs.chromium.org/p/chromium/issues/detail?id=71832 https://bugs.chromium.org/p/chromium/issues/detail?id=71832

btown 9y ago

Extremely useful for anyone doing real-time analytics or filtering. Answering "has this person visited this page before" or "how many distinct people have visited this page/website" can be done exactly with map-reduce or streaming pipelines, but if you want an immediate answer with low latency and can tolerate false negatives/bounded inaccuracy, you can simply keep a Bloom filter or HyperLogLog in memory. For example, see the top comment here: https://news.ycombinator.com/item?id=12124722 https://news.ycombinator.com/item?id=12124722

deleted 9y ago

[deleted]

dsacco 9y ago

> Personally I've never found a use for either of them in practice. One of my servers batch downloads approximately 550GB of data per day. I use a bloom filter to deduplicate the file significantly faster than naive Unix sort or awk ‘!X[$0]++’. It also has superior asymptotic complexity.

cryptonector 9y ago

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.

FreakLegion 9y ago
They actually have other uses, like measuring file similarity in sdhash and dimensionality reduction in machine learning.
- cryptonector 9y ago
  Interesting. Thanks!

susam 9y ago

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.

3131s 9y ago

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.

Radim 9y ago
Case in point, collocation detection over very large corpora: https://github.com/RaRe-Technologies/bounter#example-on-the-english-wikipedia https://github.com/RaRe-Technologies/bounter#example-on-the-... Reduces RAM requirements some 31x times when automatically detecting common multiword expressions (e.g. "New York", "network license" or "Apache Hadoop"), which is significant.
- 3131s 9y ago
  Yep, I load an enormous list of lexemes (including multiword expressions) into a bloom filter and use it for text segmentation.

foo101 9y ago

> Hacker 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. Perhaps that speaks about the type of work you are involved in rather than about the Hacker News community?

jxub 9y ago

We use Bloom filters at Datamaran (https://www.datamaran.com https://www.datamaran.com) to check if the news site source is in one of the ones we follow quickly.