Implement Bloom Filter in Python for Efficient Set Membership Testing

Updated: at 04:56 AM

A Bloom filter is a probabilistic data structure designed for efficiently testing set membership. Bloom filters have wide applications in databases, network routing, and cryptography. In this comprehensive guide, we will learn how Bloom filters work and implement one in Python.

Table of Contents

Open Table of Contents

Overview

A Bloom filter is a space-efficient set data structure that enables quickly querying whether an element is a member of a set. It may yield false positives but never false negatives. Bloom filters have superior space and time complexities compared to other set data structures.

The key idea behind a Bloom filter is to allocate a bit array of size m and k independent hash functions mapping elements to random array positions. Initially, all bits are 0. To add an element, feed it to the k hashes and set those positions to 1. To query, check if all k bit positions for that element are 1. If any is 0, the element is definitely not in. If all are 1, it most likely is, but there is a small probability of false positives.

Bloom filters occupy constant space regardless of the elements added since the filter size is fixed beforehand. The false positive rate can be tuned by adjusting m and k. Larger m lowers the false positive probability for a given number of elements n. More hashes k also improves the accuracy.

In Python, we will implement a BloomFilter class supporting add(), contains(), and basic operations. Hashing will rely on the mmh3 murmurhash library. We will also analyze the false positive probability and see examples. This guide assumes basic knowledge of Python and hash tables.

Applications of Bloom Filters

Bloom filters excel in applications where space is critical and a small false positive probability is acceptable. Some common uses:

The key advantage is the minimal space overhead compared to storing elements directly. This allows fitting large whitelist or blacklist filters even on resource-constrained devices. When false positives are tolerable, Bloom filters provide immense space savings.

How Bloom Filters Work

The core mechanism behind Bloom filters relies on hash functions mapping elements to random bit array positions uniformly. Specifically, a Bloom filter requires:

  1. A bit array of size m initialized to 0.

  2. k independent hash functions, each outputting values between 0 and m-1.

To add an element, feed it to the k hashes to get k array positions. Set those bits to 1.

To check if an item is in the set, again hash it k times to get k array positions. If any of those bits are 0, the item is definitely not in. If all are 1, it most likely is, but there is a small false positive chance also due to other set members hashing to the same bits.

This approach of using multiple hashes drastically lowers the false positive probability compared to a single hash. The more hashes, the lower the probability since an element must hash to all 1 bits to be considered in the set. We will mathematically derive this probability next.

Here is a simple example to illustrate the workflow:

from mmh3 import hash as mmh3_hash

m = 16   # Size of bit array
k = 4    # Number of hash functions

bit_array = [0] * m
hashes = [lambda x: mmh3_hash(x, i) % m for i in range(k)]

# Add element 'foo'
for i in range(k):
    index = hashes[i]('foo')
    bit_array[index] = 1

# Check if 'bar' exists
if all(bit_array[h('bar')] == 1 for h in hashes):
   print('bar most likely exists')
else:
   print('bar does not exist')

This implements the core functionality in a few lines. Next, let’s analyze the probability math and tune the parameters.

Probability of False Positives

The chance of a false positive for a query depends on:

After inserting n elements, the probability that a specific bit is still 0 is (1 - 1/m) to the power kn since each of the n elements has a 1/m chance of flipping that bit to 1.

Therefore, the probability of a false positive is the chance that all k array positions for an item are 1:

False positive probability = (1 - (1 - 1/m)^(kn))^k

This can be minimized by:

Some typical values to achieve a low false positive rate:

In practice, m is first chosen based on the space available. k is adjusted to reduce false positives based on the expected n.

Next, we will implement the BloomFilter class and demonstrate these principles.

Implementing a Bloom Filter in Python

We will now implement a BloomFilter class in Python containing:

Imports and Initialization

We import mmh3 for the hash functions and math for rounding m. The constructor handles:

from mmh3 import hash as mmh3_hash
import math

class BloomFilter:

    def __init__(self, size, hash_count):

        self.size = math.ceil(size * 1.2)
        self.hash_count = hash_count
        self.bit_array = [0] * self.size
        self.n = 0  # Initialize count of elements

        # Create the hash functions
        self.hashes = [lambda x: mmh3_hash(x, i) % self.size for i in range(self.hash_count)]

size is multiplied by 1.2 due to rounding when choosing primes for m. hash_count specifies k.

Add Element Method

The add() method hashes the input element k times and sets those indices to 1:

def add(self, element):

    for i in range(self.hash_count):
        index = self.hashes[i](element)
        self.bit_array[index] = 1

    self.n += 1

This inserts the element into the filter as described earlier.

Check for Membership

To check if an item exists, we hash it k times and ensure all array positions are 1:

def contains(self, element):

    return all(self.bit_array[h(element)] == 1 for h in self.hashes)

This returns True if likely present and False if definitely not.

Helper Functions

Some other useful methods are:

def bit_array_size(self):
    return len(self.bit_array)

def hashes(self):
    return self.hashes

def elements_added(self):
    return self.n

def false_positive_probability(self):
    return (1 - (1 - 1/self.size)** (self.hash_count*self.n)) ** self.hash_count

This completes the BloomFilter implementation. Let’s see an example of adding elements and testing membership.

Bloom Filter Usage Example

Here is an example to create a Bloom filter of size 500 and 5 hashes. We add some names and test if they exist.

from bloomfilter import BloomFilter

filter = BloomFilter(500, 5)

filter.add("John")
filter.add("Mark")
filter.add("Raj")

print(filter.contains("John")) # True
print(filter.contains("Albert")) # Most likely False positive

The false positive probability is only 0.02% here. Let’s verify it by testing 1000 random names:

from random import randint

fp_count = 0
for i in range(1000):
    name = str(randint(0, 100000))
    if filter.contains(name):
        fp_count += 1

print(fp_count/1000) # 0.002 as expected

We can also precisely calculate the false positive rate:

print(filter.false_positive_probability()) # 0.00023

Tuning m and k gives full control over the accuracy vs space tradeoff. This demonstrates the core functionality and probability analysis of Bloom filters.

Applying Bloom Filters in Databases

A major application of Bloom filters is efficiently checking if database records exist before querying the disk. This reduces expensive disk lookups for non-existent elements.

For instance, consider a database storing user profiles. Instead of directly reading from disk, we first check if the user ID exists in a Bloom filter:

bloomfilter = BloomFilter(10000, 5)

# Add all existing IDs during initialization
for id in database:
    bloomfilter.add(id)

def get_user(uid):
   if bloomfilter.contains(uid):
      # ID likely exists, do disk fetch
      user = database[uid]
   else:
      # Definitely does not exist
      user = None

   return user

This prevents unnecessary disk fetches for invalid IDs. The slight false positive chance is acceptable since the disk lookup will ultimately resolve it.

Bloom filters improve caching performance and reduce latency by avoiding disk seeks for missing elements. The space overhead is also only 5-10x vs the number of elements, which is negligible compared to actual profile data.

Conclusion

Bloom filters are a probabilistic data structure providing space-efficient set membership testing suitable for large data sets. We implemented a BloomFilter class in Python using murmur hashing and probability analysis.

Key takeaways include:

I hope this guide provided a comprehensive overview of Bloom filter theory, Python implementation, probability analysis, and practical use cases. Bloom filters are a versatile technique for optimizing set membership tests across many domains. Please leave any questions or feedback in the comments!