Bloom filter

Creator

Creator

Seonglae Cho

Created

Created

2023 Dec 9 8:27

Editor

Editor

Seonglae Cho

Edited

Edited

2023 Dec 9 14:34

Refs

Refs

Probabilistic data structure

probabilistic 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 Vector

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/

Recommendations

/////