A probabilistic data structure that tracks memberships in a set.
Supports time and space efficient lookups, but may return false-positives.
Can never return false-negatives.
A bloom filter can tell us if an element is:
Definitely not in the set
Potentially in the set (with a probability depending on the false-positive rate)
A probabilistic data structure that tracks memberships in a set. Supports time and space efficient lookups, but may return false-positives. Can never return false-negatives. A bloom filter can tell us if an element is: