Seonglae ChoProbabilistic data structure used to represent a set of elements
A Bloom filter is a data structure designed to tell you, rapidly and memory-efficiently, whether an element is present in a set.
- Bit Array and Hash functions
- Probabilistic based Insert and Query operation
- There are False positive and no False negative
Bloom filter
A Bloom filter is a space-efficient probabilistic data structure, conceived by Burton Howard Bloom in 1970, that is used to test whether an element is a member of a set. False positive matches are possible, but false negatives are not – in other words, a query returns either "possibly in set" or "definitely not in set". Elements can be added to the set, but not removed (though this can be addressed with the counting Bloom filter variant); the more items added, the larger the probability of false positives.
https://en.wikipedia.org/wiki/Bloom_filter
Let’s implement a Bloom Filter
I am planning to create a series of blog posts that includes some literature research, implementation of various data structures and our journey of creating a distributed datastore in distrentic.io.
https://onatm.dev/2020/08/10/let-s-implement-a-bloom-filter/
Bloom Filters by Example
A Bloom filter is a data structure designed to tell you, rapidly and memory-efficiently, whether an element is present in a set.
https://llimllib.github.io/bloomfilter-tutorial/