Bloom Filter

data-structures

Definition

Bloom Filter

The bloom filter is a probabilistic data structure for testing whether a set contains a certain element. It operates using $k$ hash functions.

It’s probabilistic because the bloom filter might cause false-positives with a certain probability.

Operations

Insertion

To insert an element $x$ into the bloom filter, the element must be hashed by every hash function of the bloom filter:

$$j_1=h_1(x),j_2=h_2(x),\dots ,j_k=h_k(x)$$

All values at the indices $j_1,j_2,\dots ,j_k$ are set to $1$.

Query

To test whether an element $x$ exists in the bloom filter, hash the element using all hash functions:

$$j_1=h_1(x),j_2=h_2(x),\dots ,j_k=h_k(x)$$

Then, element $x$ is contained iff:

$$j_1=j_2=\cdots =j_k=1$$