Sprzętowa implementacja filtru Blooma bazująca na pojedynczej funkcji skrótu

Filtrem Blooma nazywamy probabilistyczną strukturę danych o niewielkiej zajętości pamięciowej umożliwiającą szybkie sprawdzenie obecności danego elementu w zbiorze. W ramach artykułu przedstawiono problem sprzętowej implementacji filtru Blooma w oparciu o wyłącznie jedną funkcję skrótu oraz metodologię „one-hashing”. W szczególności przeanalizowano wpływ zwiększania rozmiaru pamięci na zmniejszenie prawdopodobieństwa wystąpienia błędnej odpowiedzi pozytywnej.

---

This article deals with the problem of hardware implementation of Bloom Filter based on one-hashing approach. Particularly, the dependency between the memory size and false positive ratio is examined.