Filtrul Bloom Scalabil

FILTRUL BLOOM SCALABIL

Filtrele Bloom permit interogari ale elementelor unei multimi cu erori admisibile. Acestea sunt utilizate pe scara larga în baze de date, retele si sisteme distribuite si au un mare potential pentru aplicatiile distribuite în cazul în care sistemele trebuie sa imparta informatii cu privire la datele disponibile. Cu toate acestea, probabilitatile de detectie falsa sunt inevitabile, iar rata de detectie a acestora creste împreuna cu multimea de date. Pentru a rezolva problema scalabilitatii filtrelor Bloom, aceasta lucrare prezinta un design nou al unui filtru scalabil Bloom (SBF) pentru o multime de date in crestere. Filtrul Bloom scalabil pastreaza o rata scazuta a erorii prin adaugarea de vectori filtru Bloom cu lungimea dubla atunci când este necesar. Documentul propune algoritmi pentru introducerea elementelor si operatia de interogare a filtrului Bloom scalabil cu ajutorul clasei H3 de functii hash universale. Rezultatele teoretice si experimentale au demonstrat ca noul filtru Bloom scalabil furnizeaza rate ale erorilor scazute, de 21,3% din filtru dinamic Bloom.

I.INTRODUCERE

Un filtru Bloom este o excelenta structura compacta de date care poate reprezenta succint o multime de date cu scopul de a oferi interogari ale elementelor sale, si de a filtra în mod efectiv orice element care nu apartine multimii stabilite. A fost introdus de B. Bloom in anul 1970. Filtrele Bloom au fost utilizate în baze de date, dictionare si aplicatii cu mult timp in urma. Recent, filtrele Bloom au fost folosite pe scara larga în sisteme distribuite si retele impreuna cu tehnologile de retea avansate. Aplicatiile legate de retea includ retele peer-to-peer, rutarea resurselor, rutarea pachetelor, masurarea si managementul retelei.

O data cu dezvoltarea tehnologiei, a Internetului si a comunicatiilor in retea s-a generat o cantitate mare de date operationale, care pot creste la ordinul a mai multor Terabytes pe an. Cresterea tot mai mare de date operationale face problema scalabilitatii sistemelor de stocare cruciala. Prin urmare, un filtru Bloom scalabil pentru reprezentarea unei multimi dinamice de date este semnificativ cat si pentru extinderea computerelor, a mediilor de retea si a cerintelor de reprezentare compacta.

Exista mai multe variante de filtru Bloom standard, cum ar fi: filtrul Bloom de numarare, filtrul Bloom comprimat, filtrul Bloom spectral, filtru Bloom dinamic si filtrul Bloom scalabil. Cu toate acestea, toate variantele cu exceptia filtrului Bloom dinamic sunt potrivite pentru reprezentarea unei multimi statice, a carei marime poate fi estimata bine înainte de concepere si de implementare. Aceste filtre Bloom cu parametri fixi pot reprezenta o multime statica. Dar, probabilitatea de detectei falsa va creste, ajungand chiar la 1 atunci când multimea de date devine foarte mare. Filtru dinamic Bloom (DBF), se ocupa de problema scalabilitatii. Filtrul Bloom dinamic reprezinta o multime de date dinamice, prin crearea si adaugarea unui filtru Bloom standard nou, cu aceeasi marime în mod repetat, pentru a regla numarul de filtre Bloom standard în functie de dimensiunea reala a unei multimi de date. Dar, performantele filtrelor Bloom dinamice scad pe masura ce numarul de filtre Bloom standard creste, care pastreaza cresterea cu o functie monoton lineara a unei multimi de date. Scalabilitatea este apoi o necesitate pentru îmbunatatire. Astfel, ceea ce consideram aici este construirea unui filtru scalabil Bloom, cu o pierdere de performanta mica în cazul în care multimea de date se extinde.

Acest document se concentreaza pe problema scalabilitatii filtrelor Bloom si prezinta o functie hash H3 bazata pe filtrul Bloom scalabil. O data cu cresterea multimii de date, filtrul Bloom scalabil poate controla probabilitatea de detectiei false la un nivel scazut prin adaugarea unor vectori noi de filtru Bloom, cu o lungime dubla. Cu scopul de a face filtrul Bloom scalabil, am proiectat functii hash H3 scalabile cu intervalul de adrese hash reglabil. Acest document propune, de asemenea algoritmi ai filtrului Bloom scalabil pentru introducerea si interogarea elementelor. Rezultate teoretice si experimentale demonstreaza ca proiectarea filtrului Bloom scalabil prezentat în aceasta lucrare ofera o performanta mai buna, scalabilitate, si timpi de interogare mai mici decât filtrul Bloom dinamic.

II.FILTRELE BLOOM

A.Filtrele Bloom standard

Sa facem o scurta recapitulare a filtrelor Bloom. Un filtru Bloom este folosit pentru a reprezenta o multime S={s1,s2,…,sn} n elemente dintr-un univers U, si consta intr-un sir de m vectori de biti notati BF[0],BF[1],…,BF[m-1], initial setati toti pe 0, pentru a descrie toate aceste elemente din multime. Filtrul foloseste k functii hash independente h1,h2,…,hk cu valori in intervalul {0,1,…,m-1}, presupunand ca aceste functii hash mapeaza independent fiecare element din universul U la un numar aleatoriu din afara intervalului. Pentru fiecare element x∈S, bitii BF[hi(x)] sunt setati pe 1 pentru 1 i k. Dandu-se un element y, verificam apartenenta lui la multime prin examinarea filtrului Bloom daca bitii de pe pozitiile h1(y),h2(y),…,hk(y) sunt setati pe 1. Daca nu, elementul y cu siguranta nu este un membru al multimii S. Daca toti hi(y) (1 i k) sunt setati pe 1, presupunem ca y apartine lui S, desi poate sa nu fie adevarat cu o anumita probabilitate. De aceea un filtru Bloom poate produce o probabilitate de detectie falsa.

Pentru o descriere simpla este utilizat un numar de 3-tuple {n, m, k} pentru a desemna filtrul Bloom standard. Probabilitatea de detectie falsa pentru un element care nu face parte din multime poate fi exprimata dupa cum urmeaza:

fBF(m,k,n)=(1-p)k=(1-e-kn/m)k .

Sa presupunem ca rata maxima a erorii este f0 si numarul maxim de elemente pe care filtrul Bloom standard il poate avea este n0. Asadar, n0 poate fi calculat dupa cum urmeaza:

n0 = -(ln(1-elnf0/k)m)/k .

Filtrul Bloom standard este de baza pentru diferitele tipuri de filtre Bloom. De acum, el este numit filtru Bloom de baza(BBF).