Bloom Filters

Bloom Filters#

Several common data structures exploit randomness to achieve efficiency and good average-case performance. We’ll learn about two of them, Bloom Filters and Skip Lists.

A Bloom filter is a space-efficient probabilistic data structure used to quickly test whether an element is a member of a large set without accessing a hard drive or network. A Bloom filter can be kept in RAM, when a full Set cannot. The properties of a Bloom filter are:

  • It does not store the items themselves, but instead stores a bit array which is altered in ways reminiscent of hash tables.

  • It can definitively say, “this item is definitely not in the set.”

  • It can only say “this item is probably in the set.” It occasionally returns false positives.

How Bloom Filters Work#

1. Initialization#

A Bloom filter is initialized by first allocating an array of \(m\) bits, with all bits set to 0. Next, \(k\) different, independent hash functions are selected. Each of these functions must map any input item to an index within the array’s range, \([0, m-1]\).

2. Insertion#

To add an item to the set, the item is hashed by all \(k\) hash functions to generate \(k\) different indices. The bits at all \(k\) of these positions in the array are then set to 1.

3. Membership Query#

To check if an item is in the set, the same process is followed: the item is hashed with the same \(k\) functions to get \(k\) indices. The filter then checks the bits at all \(k\) positions. If any of those bits is 0, the item is definitely not in the set, because all corresponding bits would have been set to 1 during insertion. If all the bits are 1, the item is probably in the set. This check is probabilistic because the bits may have been set to 1 by the insertion of other items, resulting in a false positive.

4. Deletion#

Standard Bloom filters do not support deletion. This is because clearing a bit from 1 to 0 could inadvertently affect the membership status of another item that hashes to the same bit. A variant called a Counting Bloom Filter can support deletion by replacing each bit with a small counter, but this solution comes at the cost of significantly more space.

False Positive Rate#

The probability that a specific bit is not set to 1 by a single hash function during one insertion is:

\[p = 1 - \frac{1}{m}\]

The probability it is not set by any of the \(k\) hash functions during one insertion is:

\[p^k = \left(1 - \frac{1}{m}\right)^k\]

After \(n\) elements have been inserted, the probability that a specific bit is still 0 is:

\[\left(p^k\right)^n = \left(1 - \frac{1}{m}\right)^{kn}\]

Therefore, the probability that the bit is 1 (has been set by at least one insertion) is:

\[q = 1 - \left(1 - \frac{1}{m}\right)^{kn}\]

A false positive occurs when checking for a new item, and all \(k\) bits it hashes to happen to be 1 from previous insertions. The probability of this event is:

\[\text{False Positive Rate} \approx q^k = \left(1 - \left(1 - \frac{1}{m}\right)^{kn}\right)^k\]

Trade-offs#

The design of a Bloom filter involves balancing space, time, and accuracy. Increasing \(m\) (the size of the array) reduces the likelihood of hash collisions, thereby decreasing the false positive rate at the cost of more space.

Increasing \(k\) (the number of hash functions) initially decreases the false positive rate as more bits must be incidentally set to 1 in order to trigger a false positive. After reaching an optimal point, however, it starts to increase the false positive rate, as each insertion sets so many bits to 1 that false positive rates increase. An increase in \(k\) also increases the computational cost for insertions and queries.

Typically, a designer will estimate the expected number of items (\(n\)), decide on an acceptable false positive rate, and then calculate the optimal values for \(m\) and \(k\) to meet those requirements.

Implementation#

Here’s an example implementation of a bloom filter.

from bitarray import bitarray
import hashlib

class BloomFilter:
  # Sets a bit_array at the given bit capacity (default 1000 bits)
  def __init__(self, capacity=1000):
    self.capacity = capacity
    self.bit_array = bitarray(capacity)
    self.bit_array.setall(0)

  # Standard Python hash function
  def _hash1(self,key):
    return hash(key)

  # sha256 hash function
  def _hash2(self,key):
    m = hashlib.sha256()
    m.update(key.encode())
    h = m.hexdigest()
    return int(h,16)

  # md5 hash function
  def _hash3(self,key):
    m = hashlib.md5()
    m.update(key.encode())
    h = m.hexdigest()
    return int(h,16)

  # Calculates all hashes and returns them as a tuple
  def _allhashes(self,key):
    h1 = self._hash1(key)
    h2 = self._hash2(key)
    h3 = self._hash3(key)

    return (h1, h2, h3)

  # Calculates all hashes and mods them by the capacity of the bitarray
  # Returns a tuple
  def _modder(self,key):
    return tuple(h % self.capacity for h in self._allhashes(key))

  # Insert k into the Set
  def insert(self, k):
    indices = self._modder(k)
    for i in indices:
      self.bit_array[i] = 1

  # Searches for k in the set.
  # False means "definitely not in the set"
  # True means "probably in the set"
  def contains(self, k):
    indices = self._modder(k)
    for i in indices:
      if self.bit_array[i] == 0:
        return False
    return True