Introduction to Bloom Filters

Table of Contents

• Introduction to Bloom Filters
• Operation on the Bloom Filter
• Example
• Advantages of a Bloom Filter Over a Set Data Structure
• Choosing a Hash Function
• Tuning a Bloom Filter
• Example Use Cases

Introduction to Bloom Filters

Bloom filter is a probabilistic data structure used to solve the set membership problem. A relaxed constraint here is that false positives are tolerated to an acceptable level.

Bloom filter uses a bit array to store the presence of items. Bloom filter uses hash functions to save the presence of an item without saving the actual item.

Bloom filters can give false positives, but never false negatives. This means that if the bloom filter returns positive, it means that the element may be present in the set, but if it returns negative, it means that the element is definitely not present in the set.

Now let us define a few variables before jumping into the algorithm:

1. n - The number of elements to be added in to the set.
2. k - The number of hash functions we use.
3. m - The length of the bit array we will use.

Let us assume we have n elements to insert into the set. Before inserting elements, let us create a bit array of size m with all values set to 0, and k hash functions which return values in the range of (0, m-1).

Operation on the Bloom Filter

Steps for Adding an Element

For each element we run k hash functions and then use the result as the index in the bit array. We mark the element at that index as 1. We will also store the elements in secondary storage for bookkeeping.

func addElement(item SetItem) {
    // Iterate over the array of hash functions
    for _, hashFunction := range hashFunctions {
        v := hashFunction(item)
        bitarray[v] = 1
    }
    // Here you'd save the item to secondary storage.
}

Steps for Looking Up an Element

Similar to above, we run k hash functions on an element and use the result as an index in the bit array. We check the value in each of those indexes and if the value is 1 in all of them, the bloom filter returns true.

func lookUpElement(item SetItem) bool {
    // Iterating over the array of hash functions
    for _, hashFunction := range hashFunctions {
        v := hashFunction(item)
        if bitarray[v] == 0 {
            return false
        }
    }
    return true
}

The bits at those indexes could be made 1 by different elements resulting in a false positive, but that is a tradeoff with bloom filter.

Steps for Deleting an Element

You cannot delete an element from the bloom filter. This is a significant drawback, but that is the tradeoff for reducing space utilization.

Example

We choose three hash functions and a bit array of size 16 with all bits as 0. Let us add elements A and B.

Flow for Adding the Elements

We take the element and get the hash value from the three functions and mark the corresponding bits as 1 in the bit array.

Let the hash values for A be 7, 1, and 14. So the array will change to:

Values	0	1	0	0	0	0	0	1	0	0	0	0	0	0	1	0
Index	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15

Let the hash values for B be 8, 1, and 15. So the array will change to:

Values	0	1	0	0	0	0	0	1	1	0	0	0	0	0	1	1
Index	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15

Flow for Looking Up an Item

Let's say we are searching for the element C, whose hash values are 1, 15, and 9. The values in the bit array at index 1, 15 are 1, but the value at index 9 is 0. So we can safely say that the C is not part of the set.

Why Array Lengths in Powers of 2?

When hashing, why do we usually take array lengths in powers of 2? This is because, usually we do a mod of the size of the array to find the index. If the array size is a power of 2, then taking a mod is simply a bitwise operation. Let's say the number is 254 which is 11111110. 254 \% 16 will be the last 4 bits which is 1110 which is 14.

Advantages of a Bloom Filter Over a Set Data Structure

1. Optimized Space Usage:

   • Usually a set data structure is maintained using a self-balancing binary tree, hash table, array, linked list, or trie.
   • These data structures require storing at least the elements themselves (except for trie). The items could be a small integer or a large string.
   • In contrast, the bloom filter takes the same amount of space for an item of any length.

2. Constant Insertion and Lookup Time:

   • Bloom filters also have the advantage that the insertion time is a constant value \mathrm{O}(k). The same is the case for lookup time.

3. Parallelizing Hash Functions:

   • There is also the advantage of parallelizing the execution of hash functions.

Choosing a Hash Function

1. Requirements for the Hash Function:

   • Fast computation
   • Uniform distribution
   • Cryptographic security to avoid reverse engineering is not a concern here.

2. Common Hash Functions:

   • In line with the above requirements, bloom filters typically use the hash functions MurmurHash, JenkinsHash, and FNV Hash.

Tuning a Bloom Filter

We can intuitively see that if we keep adding elements to a bloom filter, the collisions increase and hence the false positive rate also increases. In the worst case, the bloom filter returns true for any given element. Since we have all the elements saved in secondary storage, we need to increase the values m and k and create another bloom filter.

We can see that there is a tradeoff between the false positive probability p, the number of elements n, blooom filter T with the number of bits m, and the number of hash functions k.

For simplicity, let us assume that for any element e and hash function h_i, h_i(e) is distributed independently and uniformly over the range of values 1 to m. Let us also assume that the probabilities that the different bits in the filter T, T[l] are set to 1 are independent.

For any 1 ≤ l ≤ m, we evaluate the probability that T[l] = 0, after inserting all n elements into the table.

For each e ∈ S and 1 ≤ i ≤ k, the probability that h_i(e) ≠ l is (1 - 1/m).

The probability that T[l] = 0 after inserting all n elements with k probes each is simply (1 - 1/m)^{kn}.

Thus, the probability that an entry T[l] = 1 after n insertions is simply 1 - (1 - 1/m)^{kn}.

A false positive occurs when e' ∉ S but T[h_i(e')] = 1, for all 1 ≤ i ≤ k. Hence:

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

For a given n and m, one can find the k that minimizes the probability p by differentiating the right-hand side of Equation 1 with respect to k and setting it to zero. Solving for k provides the following.

$$k \approx (\ln 2) \cdot (m/n)$$

Plugging in the value of k from Equation 2 into Equation 1, we get the following relation.

$$p \approx 2^{-k} \approx 2^{-(m/n)\ln 2}$$

You can explore https://hur.st/bloomfilter/ to get these values.

Example Use Cases

1. Akamai's Caching Strategy:
   • Akamai uses a bloom filter to avoid caching one-hit wonders. They cache an item only when it is accessed for the second time.