Bloom-suodatin – määritelmä, toiminta ja hash-funktiot

Bloom-suodatin on tietorakenne, jonka avulla tietokoneet voivat nopeasti testata, esiintyykö tietty elementti joukossa. Bloom-suodattimet käyttävät tässä apuna hash-funktioita ja yksinkertaista bittitaulukkoa. Suodatin on todennäköisyysperusteinen: kysely voi antaa väärän positiivisen tuloksen (ilmoittaa elementin olevan joukossa, vaikka sitä ei ole), mutta väärää negatiivista tulosta ei voi syntyä (jos suodatin sanoo, että elementti ei ole joukossa, sitä ei todellakaan ole). Tämän vuoksi kyselyn tulos esitetään yleensä muotoina "ei varmasti joukossa" tai "mahdollisesti joukossa". Joukkoon voidaan lisätä elementtejä, mutta perus-Bloom-suodatin ei salli poistamista ilman muutoksia; jokaisen lisätyn elementin myötä väärän positiivisen tuloksen todennäköisyys yleensä kasvaa.

Edward Bloom ehdotti Bloom-suodatinta vuonna 1970 artikkelissaan, jossa hän tarkasteli algoritmeja rivin lopussa olevien sanojen yhdistämiseen (esimerkiksi väliviivaustapojen tallentamiseen). Bloomin käyttämä lähestymistapa salli huomattavasti pienemmän muistijalanjäljen vaihtokustannusten ja hakujen vähentämiseksi: hyvin pieni hash-alue pystyi silti eliminoimaan suuren osan levy- tai hakukäynneistä verrattuna virheettömiin hajautustauluihin.

Toimintaperiaate

Perus-Bloom-suodatin koostuu:

• bittitaulukosta (pituus m), ja
• k kappaletta riippumattomia hash-funktioita, jotka mappaavat syötteen m:n välille.

Lisättäessä elementti x lasketaan k hash-arvoa ja asetetaan bittitaulukon vastaavat bitit arvoon 1. Kyselyssä testataan näitä samoja k bittiä: jos jokin niistä on 0, elementti ei voi olla joukossa; jos kaikki ovat 1, elementti on mahdollisesti joukossa (tällöin voi olla kyse väärästä positiivisesta).

Parametrit ja virheiden todennäköisyys

Keskeiset muuttujat ovat:

• m = bittitaulukon pituus (bitteinä),
• n = odotettu lisättävien elementtien määrä, ja
• k = hash-funktioiden määrä.

Väärän positiivisen todennäköisyyden p voi arvioida kaavalla

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

Optimaalinen k, joka minimoi p annetulla m ja n, on noin

k ≈ (m / n) ln 2

Jos halutaan saavuttaa tietty väärän positiivisen todennäköisyys p, tarvittava bittien määrä per elementti on

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

esimerkiksi yhden prosentin (p = 0.01) väärän positiivisen todennäköisyyden vaatimus on alle 10 bittiä per elementti, kuten yleisesti todetaan.

Hash-funktiot käytännössä

Teoriassa hash-funktiot oletetaan riippumattomiksi, mutta käytännössä riittää usein käyttää kahta tehokasta hajautusta (esim. MurmurHash tai SipHash) ja kombinoida niitä ns. double hashing -menetelmällä:

h_i(x) = (h1(x) + i · h2(x)) mod m

Tämä tuottaa k eri arvoa ilman k täysin erillistä laskentaa. Hash-funktioiden laatu vaikuttaa tarkasti väärien positiivisten ja mahdollisten klusteroitumisten todennäköisyyteen.

Variantit ja rajoitukset

• Counting Bloom Filter: käyttää bittien sijaan pieniä laskureita, jolloin poistaminen on mahdollista vähentämällä laskuria. Tämä kuitenkin lisää muistinkulutusta.
• Scalable Bloom Filter: laajenee automaattisesti kun elementtejä tulee lisää, säilyttäen halutun virhetason.
• Cuckoo-filter: tarjoaa usein alemmat muistivaatimukset ja tukee poistamista sekä tallentaa avaimia osittain eri tavalla kuin Bloom.

Rajoituksia: perus-Bloom ei salli poistoja eikä palauta tallennettuja arvoja; se mahdollistaa vain jäsenyyden testaamisen. Lisäksi väärien positiivisten todennäköisyys kasvaa lisäysten myötä ellei bittitaulukkoa ole mitoitettu oikein.

Sovelluskohteita

Bloom-suodattimia käytetään laajasti, kun tarvitaan tilaa säästävää nopeaa yli- / jäsenyystestiä:

• välimuistit (cache lookups),
• tietokannat ja hajautetut järjestelmät (esim. Bigtable, Cassandra),
• verkkosovellukset ja reititys (pakettien suodatus),
• etähaut ja verkkohakemistot,
• Bitcoinin BIP37 Bloom-suodattimet (kevyt-asiakkaiden suodatus),
• oletusarvoiset virheelliset hyväksynnät (esim. spam-suodatus ja esikarsinta).

Esimerkki

Yksinkertainen esimerkki: bittitaulukko m = 20 ja k = 3 hash-funktiota. Lisättäessä elementti A asetetaan kolme bittiä indekseihin, jotka hash-funktiot määrittävät. Kun kysytään, onko B joukossa, lasketaan B:n kolme indeksiä ja tarkistetaan bittitaulukko. Jos joku bitti on 0, B ei voi olla joukossa. Jos kaikki ovat 1, B on mahdollisesti joukossa — voi olla, että nämä bitit ovat jo 1 toisten lisäysten takia.

Käytännön vinkkejä

• Valitse m ja k ennustetun n:n ja sallitun p:n mukaan.
• Käytä tehokkaita, hyvin testattuja hash-funktioita ja mahdollisesti double hashing -lähestymistapaa.
• Harkitse laskuripohjaista (counting) tai skaalautuvaa versiota, jos tarvitset poistamista tai dynaamista laajentamista.
• Seuraa käyttöä: jos lisäysten määrä kasvaa odotettua suuremmaksi, väärien positiivisten todennäköisyys voi nousta merkittävästi.

Bloom-suodattimet tarjoavat tehokkaan kompromissin tilan ja tarkkuuden välillä ja soveltuvat hyvin suuriin, luku-painotteisiin sovelluksiin, joissa pieni määrä vääristä positiivisista on hyväksyttävä.

Kysymyksiä ja vastauksia

K: Mikä on Bloom-suodatin?

K: Minkä tyyppinen tietorakenne on Bloom-suodatin?

K: Kuka ehdotti Bloom-suodatinta?

K: Mikä oli Edwardin esimerkki tekniikan käytöstä?

K: Kuinka monta bittiä per elementti tarvitaan 1 %:n väärän positiivisen todennäköisyyden saavuttamiseksi?

K: Onko mahdollista poistaa elementtejä bloom-suodattimesta sen jälkeen, kun ne on lisätty?

K: Lisääkö vai vähentääkö useampien elementtien lisääminen väärän positiivisen tuloksen todennäköisyyttä?

Hae kirjaimella