Wyniki 1-1 spośród 1 dla zapytania: authorDesc:"Aneta Augustynowicz"

SPRZĘTOWA IMPLEMENTACJA FILTRU BLOOMA BAZUJĄCA NA POJEDYNCZEJ FUNKCJI SKRÓTU DOI:10.15199/59.2019.7.12


  1. WSTĘP Probabilistyczna struktura danych, jaką jest filtr Blooma została po raz pierwszy zaprezentowana w roku 1970 za sprawą B. H. Blooma [2]. Jest ona tak zaprojektowana, aby operacja sprawdzenia obecności zadanego elementu w zbiorze przebiegała szybko i efektywnie. Niestety sprawdzenie to jest jednak obarczone nietrywialnym prawdopodobieństwem otrzymania błędnej odpowiedzi pozytywnej, którą można utożsamiać z popełnieniem błędu pierwszego rodzaju (ang. false positive). Dlatego też z konstrukcyjnego punktu widzenia bardzo ważnym jest, by wspomniane prawdopodobieństwo utrzymywać na możliwie jak najniższym poziomie przy jednoczesnym zachowaniu małej złożoności pamięciowej i obliczeniowej. Wspomniane parametry małej złożoności i akceptowalnego prawdopodobieństwa błędnej odpowiedzi pozytywnej uzyskiwano zazwyczaj dzięki zastosowaniu kilku różnych funkcji skrótu w ramach jednego filtru Blooma, tak by wyznaczyć dla każdego elementu zbioru kilka możliwie niezależnych wartości funkcji skrótu. W praktyce jednak okazywało się, iż otrzymywane wartości są z sobą skorelowane, co sprawiało, iż przy zapełnianiu filtru Blooma kolejnymi elementami zbioru prawdopodobieństwo otrzymania błędnej odpowiedzi pozytywnej bardzo szybko wzrastało. Trochę inne podejście do konstrukcji filtrów Blooma zostało zaprezentowane ostatnio przez zespół badaczy z Pekinu pod przewodnictwem Jianyuan Lu [4]. Wspomniani badacze zaproponowali, iż zamiast wykorzystania kilku różnych funkcji skrótu, można wyjścia z jednej funkcji skrótu rozpatrywać modulo różne liczby pierwsze, z których każda będzie posiadać osobny element pamiętający. Podejście to określa się mianem filtru Blooma typu "one-hashing". Autorzy wykazali wiele argumentów przemawiających za poparciem hipotezy, iż rozwiązanie takie jest wydajniejsze i w praktycznych zastosowaniach pozwala na uzyskanie mniejszego prawdopodobieństwa błędnej odpowiedzi pozytywnej, niż tradycyjny filtr Blooma. W ninie[...]

 Strona 1