@pacote/bloom-filter

A Bloom filter is a space-efficient probabilistic data structure that allows testing whether an element belongs to a set.

Bloom filters relax result accuracy for this efficiency. With Bloom filters, false positive matches are possible, but false negatives are not. That is to say, while it can tell you with certainty when an element is not in a set, any positive responses indicate only a possibility.

This false positive error rate can be lowered — but never completely eliminated — by increasing the size of the filter and/or the number of hashes computed for each element.

Installation

yarn add @pacote/bloom-filter
Copy

Sizing formulas

The optimal() helper function calculates the optimal Bloom filter size and hashes options based on the number of items in the filter (n) and the desired false positive error rate (ε).

The size of the filter, or m, is calculated with:

The number of hashes, or k, is determined by the formula:

License

MIT © Luís Rodrigues.