Bloom-Suodatin
Bloom-suodatin on tietorakenne, jonka avulla tietokoneet näkevät, esiintyykö tietty elementti joukossa. Bloom-suodattimet käyttävät tähän hash-funktioita. Jokaiselle lisättävälle elementille lasketaan hash-arvo. Kun uusi elementti lisätään, sen hash-arvoa verrataan joukon muiden elementtien arvoon. Bloom-suodatin on todennäköisyysperusteinen tietorakenne. Väärän positiivisen tuloksen saaminen on mahdollista, mutta väärän negatiivisen tuloksen saaminen ei ole mahdollista. Toisin sanoen kysely palauttaa joko "mahdollisesti joukossa" tai "ei varmasti joukossa". Joukkoon voidaan lisätä elementtejä, mutta ei poistaa. Jokaisen lisätyn elementin kohdalla väärän positiivisen tuloksen todennäköisyys kasvaa.
Edward Bloom ehdotti Bloom-suodatinta vuonna 1970. Artikkelissa Bloom olettaa, että on olemassa algoritmi, jolla rivin lopussa olevat sanat voidaan yhdistää. Esimerkin mukaan useimmilla sanoilla on yksinkertaiset väliviivamallit. Mutta noin 10 prosenttia sanoista vaatii aikaa vieviä hakuja oikean säännön hakemiseksi. Hänen tapauksessaan oli kyse noin 500 000 sanan yhdysmerkitsemisestä. Hän näki, että "normaalien" virheettömien hashing-tekniikoiden käyttäminen väliviivakuvioiden tallentamiseen vaatisi paljon muistia. Hän huomasi, että hänen tekniikkaansa käyttämällä hän pystyi eliminoimaan suurimman osan hakuja. Esimerkiksi hash-alue, joka on vain 15 prosenttia ihanteellisen virheettömän hashin tarvitsemasta koosta, eliminoi silti 85 prosenttia levykäynneistä.
Yleisemmin voidaan todeta, että yhden prosentin väärän positiivisen tuloksen todennäköisyys edellyttää alle 10 bittiä elementtiä kohti, riippumatta joukon koosta tai elementtien lukumäärästä.
Kysymyksiä ja vastauksia
K: Mikä on Bloom-suodatin?
A: Bloom-suodatin on tietorakenne, jonka avulla tietokoneet voivat nähdä, esiintyykö tietty elementti joukossa. Se käyttää tähän hash-funktioita laskemalla jokaisen lisätyn elementin hash-arvon ja vertaamalla sitä joukon muihin elementteihin.
K: Minkä tyyppinen tietorakenne on Bloom-suodatin?
V: Bloom-suodatin on todennäköisyyspohjainen tietorakenne, mikä tarkoittaa, että on mahdollista saada vääriä positiivisia tuloksia, mutta ei vääriä negatiivisia.
K: Kuka ehdotti Bloom-suodatinta?
V: Edward Bloom ehdotti Bloom-suodatinta vuonna 1970.
K: Mikä oli Edwardin esimerkki tekniikan käytöstä?
V: Edwardin esimerkkinä oli noin 500 000 sanan yhdyssanojen yhdistäminen; hän havaitsi, että hänen tekniikkaansa käyttämällä hän pystyi poistamaan suurimman osan hakuista ja vähentämään levykäyntejä 15 prosenttia.
K: Kuinka monta bittiä per elementti tarvitaan 1 %:n väärän positiivisen todennäköisyyden saavuttamiseksi?
V: Alle 10 bittiä per elementti tarvitaan 1 prosentin väärän positiivisen tuloksen todennäköisyyteen, riippumatta joukon koosta tai elementtien lukumäärästä.
K: Onko mahdollista poistaa elementtejä bloom-suodattimesta sen jälkeen, kun ne on lisätty?
V: Ei, elementtejä voidaan vain lisätä joukkoon, mutta ei poistaa.
K: Lisääkö vai vähentääkö useampien elementtien lisääminen väärän positiivisen tuloksen todennäköisyyttä?
V: Useampien elementtien lisääminen lisää väärän positiivisen tuloksen todennäköisyyttä.
