Algoritmi de streaming și filtre Bloom - manechine

În centrul multor algoritmi de streaming sunt filtrele Bloom. Creat acum aproape 50 de ani de către Burton H. Bloom, într-un moment în care știința informaticii era încă destul de tânără, intenția inițială a creatorului acestui algoritm a fost aceea de a schimba spațiul (memoria) și / sau timpul (complexitatea) împotriva a ceea ce el a numit erori admise. Hârtia sa originală este intitulată Comportament spațiu / timp în codificare Hash cu erori admise.

S-ar putea să te întrebi despre spațiul și timpul pe care Bloom îl consideră motivați pentru algoritmul său. Imaginați-vă că trebuie să determinați dacă un element a apărut deja într-un flux utilizând o structură de date discutată anterior. Găsirea unui lucru într-un flux implică înregistrarea și căutarea sunt rapide, astfel că o tabelă de tip hash pare a fi o alegere ideală. Tabelele Hash trebuie doar să adăugați elementele pe care doriți să le înregistrați și să le stocați. Recuperarea unui element dintr-o tabelă hash este rapidă deoarece tabelul hash utilizează valorile ușor manipulate pentru a reprezenta elementul, mai degrabă decât elementul în sine (care ar putea fi destul de complex). Cu toate acestea, stocarea atât a elementelor, cât și a unui indice pentru aceste elemente are limitări. Dacă o tabelă de hash se confruntă cu mai multe elemente decât se poate ocupa, cum ar fi elementele dintr-un flux continuu și potențial infinit, veți termina probleme de memorie la un moment dat.

O considerație esențială pentru filtrele Bloom este că se pot produce fals pozitive, dar negative false nu pot. De exemplu, un flux de date ar putea conține date de monitorizare în timp real pentru o centrală electrică. Atunci când se utilizează un filtru Bloom, analiza fluxului de date ar arăta că citirile așteptate sunt probabil parte a setului de citiri permise, cu unele erori admise. Cu toate acestea, atunci când apare o eroare în sistem, aceeași analiză arată că citirile nu fac parte din setul de citiri permise. Falsul pozitiv este puțin probabil să provoace probleme, dar absența unor falsuri negative înseamnă că toată lumea rămâne în siguranță. Din cauza potențialului pentru rezultate pozitive false, filtrele, cum ar fi filtrul Bloom, sunt structuri probabilistice de date - ele nu oferă un anumit răspuns, ci unul probabil.

Hashes, intrările individuale într-o tabelă hash, sunt rapide deoarece se comportă ca indexul unei cărți. Utilizați o funcție hash pentru a produce hash; intrarea este un element care conține date complexe, iar ieșirea este un număr simplu care acționează ca un indice pentru acel element. O funcție hash este deterministă deoarece produce același număr de fiecare dată când o hrăniți cu o intrare specifică de date.Utilizați hash-ul pentru a găsi informațiile complexe de care aveți nevoie. Filtrele de bloom sunt utile deoarece acestea reprezintă un mod frugal de a înregistra urme ale multor elemente fără a fi nevoie să le depozitați ca o tabelă de tip hash. Ei lucrează într-un mod simplu și folosesc următoarele ingrediente principale:

• Un vector bit: O listă de elemente de biți, în care fiecare bit din element poate avea o valoare de 0 sau 1. Lista este lungă numărul de biți numiți m. Cu cât m este mai mare, cu atât mai bine, deși există modalități de a defini în mod optim dimensiunea sa.
• O serie de funcții hash: Fiecare funcție hash reprezintă o valoare diferită. Funcțiile hash pot scurta rapid datele și pot produce rezultate uniform distribuite, rezultate egale variind de la valorile minime la cele maxime de ieșire ale hash-ului.