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

• Autorzy: Augustynowicz Paweł , Augustynowicz Aneta

Identyfikatory

DOI

10.15199/59.2019.7.12

Warianty tytułu

EN

Hardware implementation of Bloom filter based on one-hashing approach

• Konferencja: Krajowe Sympozjum Telekomunikacji i Teleinformatyki (26-28.06.2019 ; Wrocław, Polska)
• Języki publikacji: PL

Abstrakty

PL

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.

EN

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.

Słowa kluczowe

PL

filtr Blooma; FNV Hash; FPGA; błąd pierwszego rodzaju

EN

Bloom Filter; false positive; FNV Hash; FPGA

• Wydawca: Wydawnictwo SIGMA-NOT
• Czasopismo: Przegląd Telekomunikacyjny + Wiadomości Telekomunikacyjne
• Rocznik: 2019
• Tom: nr 7
• Strony: 557--560, CD
• Opis fizyczny: Bibliogr. 4 poz., tab.

Twórcy

autor

Augustynowicz Paweł

• Wojskowa Akademia Techniczna, ul. Urbanowicza 2, 01-476 Warszawa
• Politechnika Warszawska ul. Koszykowa 75, 00-662 Warszawa

autor

Augustynowicz Aneta

• Wojskowa Akademia Techniczna, ul. Urbanowicza 2, 01-476 Warszawa
• Politechnika Warszawska ul. Koszykowa 75, 00-662 Warszawa

Bibliografia

• [1] Augustynowicz Paweł. 2018. ,,Dobór funkcji skrótu spełniających wymagania sprzętowej implementacji filtru Blooma”, Przegląd Telekomunikacyjny – Wiadomości Telekomunikacyjne, 8-9
• [2] Bloom Burton. 1970. ,,Space/Time Trade-offs in Hash Coding with Allowable Errors”, Communications of ACM, 13(7): 422-426
• [3] Fowler Glenn, Noll Landon, Vo Phong. 1991. ,,Fowler/Noll/Vo (FNV) Hash”, http://isthe.com/chongo/tech/comp/fnv/
• [4] Lu Jianyuan, Yang Tong, Wang Yi. 2018. ,,Low Computational Cost Bloom Filters”, IEEE/ACM Transactions on Networking, 26(5): 2254-2267

Uwagi

PL

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2019).