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.
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.
Check out their usage in Cassandra: http://cassandra.apache.org/doc/latest/operating/bloom_filte...
There should be many more you can find via quick googling.
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://chrome.google.com/webstore/detail/hacker-news-filter...
Perhaps that speaks about the type of work you are involved in rather than about the Hacker News community?
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.
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.
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!
(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.)
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.
See https://en.wikipedia.org/wiki/Bloom_filter#Optimal_number_of...
> The required number of bits, m, given n (the number of inserted elements) and a desired false positive probability p (and assuming the optimal value of k is used) can be computed by substituting the optimal value of k in the probability expression above: > > This means that for a given false positive probability p, the length of a Bloom filter m is proportionate to the number of elements being filtered n
You will find that the required size (in bits) at any reasonable error (<10%) is greater than the size of the population, i.e., a bitvector is a smaller representation of the set. (It has other differing properties, too, but size is the one I am focusing on.)
Wikipedia shares this observation:
https://en.wikipedia.org/wiki/Bloom_filter#Space_and_time_ad...
> However, if the number of potential values is small and many of them can be in the set, the Bloom filter is easily surpassed by the deterministic bit array, which requires only one bit for each potential element.
(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.)