Bloomov filter — verjetnostna podatkovna struktura za hitro preverjanje članstva

Bloomov filter: učinkovita verjetnostna podatkovna struktura za hitro preverjanje članstva, varčna z memorijo in z nadzorovanimi lažno pozitivnimi rezultati.

Bloomov filter je podatkovna struktura, ki računalniku omogoča hitro preverjanje, ali se določen element verjetno pojavlja v množici. Bloomovi filtri uporabljajo več hash funkcij in bitno polje: za vsak dodan element se izračuna več vrednosti hasha in nastavi ustrezne bite v bitnem nizu. Pri poizvedbi se izračunajo iste hash vrednosti in preveri se, ali so vsi ustrezni biti nastavljeni. Bloomov filter je verjetnostna podatkovna struktura — omogoča le dve izhodišči: "zagotovo ni v množici" ali "morda je v množici". To pomeni, da so možni lažno pozitivni odgovori (element ni v množici, a filter jih označi kot prisotne), medtem ko lažno negativni odgovori ne obstajajo (če filter pravi, da element ni, ga res ni). Elemente lahko dodajamo, običajni (klasični) Bloomov filter pa elementov ne more zanesljivo brisati; z dodajanjem se povečuje verjetnost lažno pozitivnih odgovorov.

Kratek zgodovinski pregled

Idejo je leta 1970 predlagal Edward Bloom. V svojem članku je opisal problem iskanja pravil za členkovanje besed, kjer je opazil, da bi shranjevanje vseh pravil s klasičnim (popolnim) hashanjem zahtevalo veliko pomnilnika. Bloom je predlagal bitno-poljsko rešitev, ki pri manjši porabi pomnilnika odpravi veliko število iskanj (na primer, območje hashiranja, le okoli 15 % velikosti potrebne za idealno breznapakno hashiranje, je še vedno omogočalo odpravo približno 85 % dostopov do diska v njegovem primeru).

Osnovno delovanje (koraki)

• Inicializacija: ustvarimo bitni vektor dolžine m (vsi biti nastavljeni na 0) in izberemo število hash funkcij k.
• Dodajanje elementa x: izračunamo k hash vrednosti h1(x), h2(x), ..., hk(x) in za vsako vrednost nastavim bit na položaju hi(x) mod m na 1.
• Preverjanje članstva za x: izračunamo iste k hash vrednosti; če so vsi ustrezni biti enaki 1, vrnemo "morda je v množici" (možen lažno pozitiven rezultat); če je vsaj en bit 0, vrnemo "zagotovo ni v množici".
• Operacije množic: unija dveh Bloomovih filtrov iste velikosti in z enakim številom hash funkcij je bitni OR; presek je bitni AND.

Verjetnosti in izbira parametrov

Za dane parametre m (število bitov v filteru), n (število vstavljenih elementov) in k (število hash funkcij) je približna verjetnost lažno pozitivnega rezultata:

p ≈ (1 − e^(−k n / m))^k

Optimizacija glede na minimalno verjetnost p za dano m in n daje optimalno število hash funkcij:

k ≈ (m / n) · ln 2

Če želimo neposredno izračunati potrebno število bitov na element (m/n) za želeno verjetnost p, velja formula:

m / n ≈ −(ln p) / (ln 2)^2

Praktična posledica: za približno 1‑odstotno verjetnost lažno pozitivnih rezultatov potrebujemo manj kot 10 bitov na element (izračun: m/n ≈ 9,58 bitov za p = 0,01), kar je razlog, da so Bloomovi filtri zelo prostorsko učinkoviti.

Razširitve in različice

• Counting Bloom filter: namesto posameznih bitov se uporablja polje števcov (na primer 4‑bitni števec) — to omogoča brisanje (zmanjšanje števcov), saj se bit ne izbriše, dokler števec ne pade na 0.
• Scalable Bloom filter: sestavljen iz več Bloomovih filtrov, ki se dinamično dodajajo, ko se povečuje število elementov, s čimer ohranja kontrolirano stopnjo lažno pozitivnih rezultatov.
• Partitioned Bloom filter: bitno polje je razdeljeno na k segmentov, vsaka hash funkcija naslavlja svoj segment — lahko izboljša lokalnost in porazdelitev bitov.
• Cuckoo filter: alternativa, ki podpira učinkovito brisanje in v mnogih primerih manjšo verjetnost lažno pozitivnih rezultatov za enako količino pomnilnika.
• Blocked/Compressed Bloom filters: optimizacije za predpomnilnik (cache) in stiskanje bitnega polja.

Implementacijski napotki

• Uporaba več neodvisnih hashov je idealna, v praksi pa se običajno uporablja dvojno hashanje (dva različna hash-a h1, h2), iz katerih s formulo h_i(x) = h1(x) + i·h2(x) dobimo k vrednosti — to zmanjša stroške izračunov brez velike izgube kakovosti (metoda Kirsch & Mitzenmacher).
• Pomembno je izbrati primerne hash funkcije, da se izognemo nezaželenim korelacijam; pri varnostno občutljivih aplikacijah je morda potrebna kriptografsko varna hash funkcija.
• Bloomovi filtri so občutljivi na število vstavljenih elementov: če jih vstavimo več, kot je bilo načrtovano, se p poveča — zato je merjenje in spremljanje pomembno ali pa uporaba skalabilne različice.
• Za združevanje dveh filtrov mora biti enaka velikost m in enaki parametri (ali pa uporabimo njihove razširitve/osnovne filtre pri skalabilnih strukturah).

Prednosti in slabosti

• Prednosti: izjemno varčna raba pomnilnika glede na shranjevanje celih elementov, hitre operacije (izračun k hash-ev in dostop do k bitov), preprosta reprezentacija množice, enostavno združevanje (OR) in presekanje (AND).
• Slabosti: obstajajo lažno pozitivni odgovori, ne moremo natančno preveriti števila pojavitev elementa (razen pri števec izvedbi), običajni Bloomov filter ne omogoča brisanja, občutljivost na napake pri izbiri parametrov in hash funkcijah.

Uporabe

Bloomovi filtri so uporabni v številnih področjih, kjer je pomembna hitra odločitev o verjetni prisotnosti elementa z nizko prostorsko porabo, na primer:

• filtriranje poizvedb v bazah podatkov in iskalnikih (da se preprečijo nepotrebni dostopi na disk),
• porazdeljeni sistemi in protokoli (npr. pri deduplikaciji, sinhronizaciji stanja med vozlišči),
• omrežje (filteri paketov, opozorila za širjenje neželene pošte),
• spletni pajki in preverjanje, ali je URL že obiskan,
• spremljanje besedil (npr. slovnični ali pravopisni filtri) — kar je bil tudi Bloomov izvirni motiv.

Bloomov filter je preprost, hiter in pogosto zelo učinkovit pristop za težave, kjer je dovoljena določena raven lažno pozitivnih rezultatov, a so lažno negativni rezultati nesprejemljivi. Pri načrtovanju je ključna pravilna izbira velikosti m in števila hash funkcij k glede na pričakovano število elementov n in sprejemljivo verjetnost p lažno pozitivnih odgovorov.

Vprašanja in odgovori

V: Kaj je Bloomov filter?

V: Katera vrsta podatkovne strukture je Bloomov filter?

V: Kdo je predlagal Bloomov filter?

V: Kakšen je bil Edwardov primer uporabe njegove tehnike?

V: Koliko bitov na element je potrebnih za 1-odstotno verjetnost lažno pozitivnih rezultatov?

V: Ali je mogoče odstraniti elemente iz cvetočega filtra, ko so bili dodani?

V: Ali dodajanje več elementov poveča ali zmanjša verjetnost lažno pozitivnega rezultata?

Išči po črki