Bloom Filters: Difference between revisions
No edit summary |
|||
| (One intermediate revision by the same user not shown) | |||
| Line 1: | Line 1: | ||
=External= | |||
* https://www.coursera.org/learn/algorithms-graphs-data-structures/lecture/riKfa/bloom-filters-the-basics | |||
* https://www.coursera.org/learn/algorithms-graphs-data-structures/lecture/QSHNY/bloom-filters-heuristic-analysis | |||
=Internal= | =Internal= | ||
* [[Data_Structures#Bloom_Filters|Data Structures]] | * [[Data_Structures#Bloom_Filters|Data Structures]] | ||
=Overview= | =Overview= | ||
A Bloom filter is a data structure that can be used to remember if a specific element has been "seen" already, in an extremely space efficient manner. The idea is that we apply a hash function to the object (key) and project the result on a set of bits. The Bloom filter starts with all bits set to 0 and over time, some of the bits are turned to 1, depending on the object that have been "seen" by the filter. | |||
A fundamental characteristic is that the filter can produce false positives - it can report that an object has been "seen" when it fact the object has not been seen. This is a consequence of the fact that a large number of objects are "projected" onto a limited space, and collisions or partial collisions may occur. The Bloom filter will never produce a false negative: if an object has been actually seen by the filter, the filter will never report that the object has not been seen. | |||
It can be proved using discrete probabilities that the Bloom filters are useful data structures and the advantages of using space efficiently outweigh the fact that the filter produces false positives. | |||
Latest revision as of 21:42, 17 October 2021
External
- https://www.coursera.org/learn/algorithms-graphs-data-structures/lecture/riKfa/bloom-filters-the-basics
- https://www.coursera.org/learn/algorithms-graphs-data-structures/lecture/QSHNY/bloom-filters-heuristic-analysis
Internal
Overview
A Bloom filter is a data structure that can be used to remember if a specific element has been "seen" already, in an extremely space efficient manner. The idea is that we apply a hash function to the object (key) and project the result on a set of bits. The Bloom filter starts with all bits set to 0 and over time, some of the bits are turned to 1, depending on the object that have been "seen" by the filter.
A fundamental characteristic is that the filter can produce false positives - it can report that an object has been "seen" when it fact the object has not been seen. This is a consequence of the fact that a large number of objects are "projected" onto a limited space, and collisions or partial collisions may occur. The Bloom filter will never produce a false negative: if an object has been actually seen by the filter, the filter will never report that the object has not been seen.
It can be proved using discrete probabilities that the Bloom filters are useful data structures and the advantages of using space efficiently outweigh the fact that the filter produces false positives.