Vectorize Bloom Filter operations for numpy

Viewed 93

How can I make use of numpy's vector operations for a Bloom Filter implementation? I started from https://www.geeksforgeeks.org/bloom-filters-introduction-and-python-implementation/ and modified for naive ndarray support.

Remark: I'm not bound to mmh3 - this was just the only library that allowed me to make use of seeded hashing for generating multiple hash functions.

import numpy as np
import math
import mmh3
from bitarray import bitarray

class BloomFilter(object):
    def __init__(self, items_count: int = 100_000, fp_prob : float = 0.01):
        self.fp_prob = fp_prob
        self.size = self.get_size(items_count, fp_prob)
        self.hash_count = self.get_hash_count(self.size, items_count)
        self.bit_array = bitarray(self.size)
        self.bit_array.setall(0)

    def add(self, item):
        if type(item) is np.ndarray:
            for i in item.reshape(-1):
                self.add(i)
        else:
            digest = self.digest(item)
            for pos in digest:
                self.bit_array[pos] = True
    
    def digest(self, item):
        return [mmh3.hash(item, seed=i) % self.size for i in range(self.hash_count)]

    def contains(self, item):
        if type(item) is np.ndarray:
            return np.array(
                [self.contains(i) for i in item.reshape(-1)], 
                dtype=np.bool8
            ).reshape(item.shape)
        else:
            return all(self.bit_array[pos] for pos in self.digest(item))

    @classmethod
    def get_size(self, n, p):
        return int(-(n * math.log(p))/(math.log(2)**2))

    @classmethod
    def get_hash_count(self, m, n):
        return int((m/n) * math.log(2))


items = np.random.randint(size=1_000_000, low=0, high=2**60, dtype=np.int64)
set_of_items = BloomFilter(items.size, 0.001)
set_of_items.add(items)

items2 = np.random.randint(size=100_000, low=0, high=2**60, dtype=np.int64)
existing = set_of_items.contains(items2)
new_items = items2[~existing]

print(f"#{len(new_items)}")
0 Answers
Related