Bloomi filter
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.
Küsimused ja vastused
K: Mis on Bloomi filter?
V: Bloomi filter on andmestruktuur, mis võimaldab arvutitel näha, kas mingi element esineb mingis kogumis. See kasutab selleks hash-funktsioone, arvutades iga lisatud elemendi hash-väärtuse ja võrreldes seda teiste elementidega kogumis.
K: Millist tüüpi andmestruktuur on Bloomi filter?
V: Bloomi filter on tõenäosuslik andmestruktuur, mis tähendab, et on olemas võimalus saada valepositiivseid, kuid mitte valenegatiivseid tulemusi.
K: Kes pakkus välja Bloomi filtri?
V: Edward Bloom pakkus Bloomi filtri välja 1970. aastal.
K: Milline oli Edward Bloomi näide tema tehnika kasutamise kohta?
V: Edward Bloomi näide oli umbes 500 000 sõna ühendamine; ta leidis, et tema tehnikat kasutades sai ta kõrvaldada enamiku otsingutest ja vähendada kettakasutust 15% võrra.
K: Mitu bitti elemendi kohta on vaja 1% valepositiivse tõenäosuse saavutamiseks?
V: 1% valepositiivse tõenäosuse saavutamiseks on vaja vähem kui 10 bitti elemendi kohta, sõltumata kogumi elementide suurusest või arvust.
K: Kas pärast elementide lisamist on võimalik neid bloom-filtrist eemaldada?
V: Ei, elemente saab ainult lisada, kuid mitte eemaldada.
K: Kas rohkemate elementide lisamine suurendab või vähendab valepositiivse tulemuse saamise tõenäosust?
V: Rohkemate elementide lisamine suurendab valepositiivse tulemuse saamise tõenäosust.
