Bloom Filter

data-structures algorithms probability

Definition

Bloom Filter

A Bloom filter is a space-efficient, probabilistic data structure used to test whether an element is a member of a set. It is designed to be incredibly fast and use minimal memory, at the cost of providing false positive results.

• False Positives: The filter may report that an element is in the set when it is not.
• False Negatives: The filter never reports that an element is not in the set if it has been inserted (i.e., it is 100% accurate for negative results).

Mechanism

A Bloom filter consists of a bit array of $m$ bits, all initially set to 0. It also requires $k$ different hash functions, each of which maps an element to one of the $m$ array positions.

Insertion

To insert an element $x$, it is hashed by each of the $k$ hash functions to get $k$ array indices. The bits at all these indices are set to 1.

$$j\ast i=h\ast i(x)(\mathrm{mod}m)\text{for }i=1,\dots ,k$$

Query

To query for an element $x$, hash it using the same $k$ functions. If all bits at these indices are 1, the element is possibly in the set. If any bit is 0, the element is definitely not in the set.

Mathematical Properties

False Positive Probability

The probability of a false positive $\epsilon$ depends on the number of elements $n$ inserted, the size of the bit array $m$, and the number of hash functions $k$:

$$\epsilon \approx {\left(1-e^{-kn/m}\right)}^k$$

For a given $m$ and $n$, the value of $k$ that minimises the false positive probability is:

$$k=\frac{m}{n}\ln 2$$

Complexity

Operation	Time Complexity
Insertion	$O(k)$
Query	$O(k)$

Space complexity is $O(m)$, which is independent of the size of the elements themselves, making Bloom filters ideal for large-scale data processing.