- The filter can yield false positives (told element is in the set but it isn't) but not false negatives (told element is not in set but it is)
- Typically implemented using a bit vector
- The more elements added to the filter, the higher the chance for false positives (assuming no resize)
- Is space compact with respect to the set it represents (can represent all possibilities with little space)

## 2007-06-10

### Bloom Filters for Everyone

A Bloom filter according to wikipedia, "is a space-efficient probabilistic data structure that is used to test whether an element is a member of a set." Named for the computer scientist Burton Bloom, the Bloom filter has the following informal attributes:

Subscribe to:
Post Comments (Atom)

## No comments:

Post a Comment