3 ms·
For those who are new to Bloom filters, the article doesn't quite finish connecting the dots to a common use case: Bloom filters give no false negatives but a
by saidajigumi 10y ago
For those who are new to Bloom filters, the article doesn't quite finish connecting the dots to a common use case:
Bloom filters give no false negatives but a controllable rate of false positives. If a Bloom filter indicates that an item has not been seen before, we can be certain that’s the case; but if it indicates an item has been seen, it’s possible that’s not the case (a false positive).
This style of probabilistic data structure can be used to achieve a significant speedup when the full test for set membership is very expensive. For example, run the test using the Bloom filter. A negative result can be taken as truth, while only positive results will have to be tested against the expensive algorithm to weed out false positives. Obviously, the expectation should be that negative results are far more common than positive results.
- lilyball 10y agoAs a practical example of this, consider searching a corpus of texts for a phrase. You can build a bloom filter from each text ahead of time, using each individual word as the elements to put in the filter. Then when searching, you can split the search phrase into words and check if all the words occur in the bloom filters. If any word does not occur, then you know the phrase won't match that text. But if the bloom filter can't rule out any of the words, then you can do the more expensive full-text search. This means you can search the whole corpus much quicker, as you can skip any text that doesn't match the words.
- sk5t 10y agoI might be inclined to use a lightly massaged prefix tree (adding an "end of word" symbol) instead of a bloom filter in this particular case, depending on the size of dictionary and cost of a false-maybe.