Bloomi filter — mälusäästlik probabilistlik andmestruktuur hash-funktsioonidega

Bloomi filter — mälusäästlik probabilistlik andmestruktuur hash-funktsioonidega: kiire elementide olemasolu kontroll, madal mälukulu ja võimalikud valepositiivsed tulemused.

Bloomi filter on andmestruktuur, mis võimaldab arvutitel näha, kas mingi element esineb mingis kogumis. Bloomi filtrid kasutavad selleks hash-funktsioone. Iga lisatud elemendi jaoks arvutatakse hash-väärtus. Uue elemendi lisamisel võrreldakse selle hash-väärtust kogumi teiste elementide väärtusega. Bloomi filter on tõenäosuslik andmestruktuur. On võimalik saada valepositiivne, kuid mitte valenegatiivne. Teisisõnu, päring tagastab kas "võimalik, et kuulub kogumisse" või "kindlasti ei kuulu kogumisse". Elemente võib komplekti lisada, kuid mitte eemaldada. Iga lisatud elemendi puhul kasvab valepositiivse tulemuse saamise tõenäosus.

Edward Bloom pakkus Bloomi filtri välja 1970. aastal. Artiklis oletab Bloom, et on olemas algoritm, mis võimaldab sidekriipsu sõnade sidumist rea lõpus. Näite kohaselt on enamik sõnu lihtsate sidekriipsude mustritega. Kuid umbes 10% sõnadest nõuab õige reegli leidmiseks aeganõudvaid otsinguid. Tema puhul oli tegemist umbes 500 000 sõna sidekriipsuühendusega. Ta nägi, et "tavaliste" vigadeta hashing-tehnikate kasutamine, sidekriipsimustrite salvestamine, nõuaks palju mälu. Ta leidis, et tema tehnikat kasutades saaks ta enamiku otsingute tegemise välistada. Näiteks hash-ala, mis on ainult 15% ideaalse veavaba hashi jaoks vajalikust suurusest, kõrvaldab ikkagi 85% kettakäikudest.

Üldisemalt on 1% valepositiivse tõenäosuse saavutamiseks vaja vähem kui 10 bitti elemendi kohta, sõltumata kogumi elementide suurusest või arvust.

Kuidas Bloomi filter töötab

Bloomi filter koosneb bitivektorist (m bitti) ja k sõltumatust hash-funktsioonist. Kui lisatakse element, arvutatakse selle k hash'i ja iga hash-väärtuse tulemusena määratakse bitivektoris vastav indeks, mille väärtus seatakse 1-ks. Päringu (membership test) puhul arvutatakse samad k hash'i: kui mõni vastav bitt on 0, siis element kindlasti ei kuulu kogumisse; kui kõik k bitti on 1, siis element võib kuuluda — see on koht, kus tekib valepositiivne tulemus (biti(de) kattumine teiste elementidega), kuid valenegatiivne tulemus ei ole võimalik (kuna lisamisel seatakse bitti kunagi 0-ks tagasi ei lükata).

Peamised parameetrid ja tõenäosused

Olulised parameetrid on m (bittide arv), n (lisatud elementide arvestus) ja k (hash-funktsioonide arv). Nende vahel kehtib ligikaudne valepositiivse tõenäosuse valem:

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

Optimaalne k, mis minimeerib p antud m ja n korral, on k ≈ (m / n) · ln 2. Kui soovitakse saavutada etteantud tõenäosus p, saab hinnata vajaliku m suuruse:

m ≈ −(n · ln p) / (ln 2)²

Praktiline näide: 1% (p = 0.01) valepositiivse tõenäosuse jaoks on m/n ≈ 9.6 bitti elemendi kohta ja optimaalseks k-ks tuleb umbes 7 hash-funktsiooni.

Eelised ja piirangud

• Eelised: väga mäluefektiivne võrreldes täpsete struktuuridega, kiire (päring ja lisamine O(k)), lihtne bitivektorit kombineerida (nt OR-iga mitme filtri ühendamisel).
• Piinangud: ei toeta elementide lihtsat eemaldamist (tavalisest Bloom-filtrist), olemasolevad valepositiivsed tulemused; valepositiivse tõenäosus kasvab, kui lisatakse rohkem elemente kui ette nähtud.

Lahendused piirangutele ja variandid

Kui on vaja eemaldamist, kasutatakse loendavat Bloom-filtrit (counting Bloom filter), kus iga bitt on väikse loenduriga (nt 4 bitti), mis inkrementitakse lisamisel ja dekrementitakse eemaldamisel. Teised variandid ja täiustused:

• Skaleeritav Bloom-filter (scalable Bloom filter) — lisab uusi filtreid, kui originaalne filter läheb "täis", säilitades kontrolli valepositiivsuse üle.
• Partitsioneeritud Bloom-filter — jaotab bitivektori osadeks, mis mõnikord parandab sooritust ja hajutuse omadusi.
• Cuckoo filter — alternatiiv, mis toetab eemaldamist ja võib vähendada valepositiivseid vastuseid mõnel juhul.

Rakendused ja praktilised näpunäited

• Kasutatakse andmebaasides ja indekseerimissüsteemides (nt Bigtable-laadsed süsteemid), et vältida tarbetuid kettalugemisi.
• Veebi- ja võrguvahemälud, rämpsposti tuvastus, andmeedastuse kadu vähendamine ja kiire eelisotsustus, kas üksus on tõenäoliselt olemas.
• Algne Bloomi näide: ortograafia ja sidekriipsud, kus väike filtrimudel vähendab aeglasemate otsingute arvu.

Rakendamisel kasutatakse sageli mitte-kõiki sõltumatuid hash-funktsioone, vaid kahte kiiret hash'i ja neist tuletatakse ülejäänud (double hashing): h_i(x) = (h1(x) + i · h2(x)) mod m — see vähendab hashide arvutamise kulusid ilma oluliselt mõjutamata valepositiivset tõenäosust. Levinud hash-variantideks on MurmurHash, xxHash jm.

Järeldus

Bloomi filter on lihtne, kiire ja mäluefektiivne vahend liikuvate ja suurte elementide arvude esinemise kontrollimiseks, millel on aktsepteeritav kompromiss valepositiivsete vastuste kujul. Õige parameetrite (m, k) valimisega ning vajadusel variantide kasutamisega saab seda kohandada mitmetele praktilistele ülesannetele.

Küsimused ja vastused

K: Mis on Bloomi filter?

K: Millist tüüpi andmestruktuur on Bloomi filter?

K: Kes pakkus välja Bloomi filtri?

K: Milline oli Edward Bloomi näide tema tehnika kasutamise kohta?

K: Mitu bitti elemendi kohta on vaja 1% valepositiivse tõenäosuse saavutamiseks?

K: Kas pärast elementide lisamist on võimalik neid bloom-filtrist eemaldada?

K: Kas rohkemate elementide lisamine suurendab või vähendab valepositiivse tulemuse saamise tõenäosust?

Otsing