Dobór funkcji skrótu spełniających wymagania sprzętowej implementacji filtru Blooma

• Autorzy: Augustynowicz P.

Identyfikatory

DOI

10.15199/59.2018.8-9.12

Warianty tytułu

EN

Hash functions for hardware implementation of Bloom filter

• Konferencja: Krajowe Sympozjum Telekomunikacji i Teleinformatyki (12-14.09.2018 ; Bydgoszcz, Polska)
• Języki publikacji: PL

Abstrakty

PL

Filtr Blooma to probabilistyczna struktura danych pozwalająca na szybkie sprawdzenie, czy dany element jest obecny we wcześniej zadanym zbiorze. W artykule przedstawiono problem wyboru funkcji skrótu dla sprzętowej implementacji filtru Blooma w układach FPGA, biorąc pod uwagę takie czynniki jak efektywność i zajętość. Podczas badań zaimplementowano i zrewidowano aplikacyjność w rozwiązaniach sprzętowych kilku popularnych algorytmów.

EN

This article deals with the problem of optimal choice of hash functions with application to hardware Bloom Filter implementation. Particularly, the efficiency of Bloom Filter implementation and its area occupancy for several common algorithms were investigated.

Słowa kluczowe

PL

filtr Blooma; FPGA; błąd pierwszego rodzaju

EN

Bloom Filter; FPGA; false positive

• Wydawca: Wydawnictwo SIGMA-NOT
• Czasopismo: Przegląd Telekomunikacyjny + Wiadomości Telekomunikacyjne
• Rocznik: 2018
• Tom: nr 8-9
• Strony: 605--608, CD
• Opis fizyczny: Bibliogr. 7 poz., tab.

Twórcy

autor

Augustynowicz P.

• Wojskowa Akademia Techniczna, ul. Urbanowicza 2, 01-476 Warszawa

Bibliografia

• [1] Appleby Austin. 2008. "MurmurHash, first announcement", LiveJournal, https://tanjent.livejournal.com/
• [2] Bloom Burton. 1970. "Space/Time Trade-offs in Hash Coding with Allowable Errors", Communications of ACM, 13(7):422-426
• [3] Muvley Bret. 2007. "Hash functions", http://papa.bretmulvey.com
• [4] Saibal Pal, Sardana Puneet. 2012. "Bloom Filters and their applications", International Journal of Computer Applications and Technology, 1:25-29
• [5] Pankaj Gupta, Goel Ashish. 2010. "Small subset queries and bloom filters using ternary associative memories with applications", ACM Sigmetrics, 38:143
• [6] Mazurkiewicz Tomasz, Łuba Tadeusz 2017. "Redukcja Liczby Zmiennych do Reprezentacji Funkcji Generowania Indeksów", Przegląd Telekomunikacyjny - Wiadomości Telekomunikacyjne, 8-9
• [7] Zhang Wentao, Zhenzhen Bao, Rijmen Vincent, Liu Meicheng "

Uwagi

PL

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