12 ms·
Scalable Bloom Filters (2007) [pdf]
- bhouston 9y agoHacker 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 agoThey 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 agoIt'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 agoI’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 agoAny in fact anything that sounds sort of computer sciencey.
- loeg 9y agoI 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 agoI 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 agoHere'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 agoThe 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 agoYour 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 agoBloom 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 agoExtremely 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 agoThey 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 agoThey actually have other uses, like measuring file similarity in sdhash and dimensionality reduction in machine learning.
- cryptonector 9y agoInteresting. Thanks!
- susam 9y agoWe 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 agoI 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 agoCase 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 agoYep, 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 agoWe 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.
- howitworks 9y agoThis should be labeled as a PDF
- dang 9y agoYes. Added.
- stochastic_monk 9y agoThis should also be marked with a year. A cursory google search has StackOverflow answers from 2013. A lack of a year label implicitly suggests that it’s new, e.g. Hacker News. Please add a tag with the appropriate year.
- signa11 9y agothis 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 would be very welcome. <end-rant> on the subject of bloom filters, have a look at this one: https://www3.cs.stonybrook.edu/~ppandey/files/p775-pandey.pdf https://www3.cs.stonybrook.edu/~ppandey/files/p775-pandey.pd... (A General-Purpose Counting Filter: Making Every Bit Count)
- mceachen 9y agoAgreed. First time this was in HN, I wanted to understand both types of bloom filters, so I wrote https://github.com/mceachen/bloomer https://github.com/mceachen/bloomer.
- esturk 9y agoCan 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?
- cmurphycode 9y agoYes, 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.)
- bistro17 9y agoimplementation of this paper - https://metacpan.org/pod/Bloom::Scalable https://metacpan.org/pod/Bloom::Scalable
- opencoff 9y agoI used this paper for building a scalable bloom filter for use in an ad-tech stack. The performance was better than DJB's CDB. https://github.com/opencoff/portable-lib https://github.com/opencoff/portable-lib The bloom filter code is in src/bloom.c; the Header file is in inc/utils/bloom.h I implemented a serialization/deserialization of the bloom filters as well (src/bloom_marshal.c). The tests are in test/t_bloom.c.