Bloom-Filter er
Et Bloom-filter er en datastruktur, der gør det muligt for computere at se, om et givet element forekommer i et sæt. Bloom-filtre anvender hash-funktioner til dette formål. For hvert element, der tilføjes, beregnes en hash-værdi. Når et nyt element tilføjes, sammenlignes dets hash-værdi med hash-værdien for de andre elementer i mængden. Et Bloom-filter er en probabilistisk datastruktur. Det er muligt at få et falsk positivt svar, men ikke at få et falsk negativt svar. Med andre ord returnerer en forespørgsel enten "muligvis i mængden" eller "helt sikkert ikke i mængden". Elementer kan tilføjes til mængden, men ikke fjernes. For hvert tilføjet element vokser sandsynligheden for at få et falsk positivt resultat.
Edward Bloom foreslog Bloom-filteret i 1970. I artiklen antager Bloom, at der findes en algoritme til at sætte bindestreger på ord i slutningen af en linje. I henhold til eksemplet har de fleste ord enkle bindingsmønstre. Men ca. 10 % af ordene kræver tidskrævende opslag for at hente den korrekte regel. Hans sag drejede sig om afbinding af ca. 500.000 ord. Han så, at det ville kræve meget hukommelse at bruge de "normale" fejlfrie hashing-teknikker til lagring af bindingsmønstre. Han fandt ud af, at han ved hjælp af sin teknik kunne eliminere de fleste opslag. F.eks. eliminerer et hash-område, der kun er 15 % af den størrelse, der er nødvendig for en ideel fejlfri hash, stadig 85 % af disktilgangene.
Mere generelt kræves der mindre end 10 bits pr. element for at opnå en falsk positiv sandsynlighed på 1 %, uafhængigt af størrelsen eller antallet af elementer i mængden.
Spørgsmål og svar
Spørgsmål: Hvad er et Bloom-filter?
A: Et Bloom-filter er en datastruktur, der gør det muligt for computere at se, om et givet element forekommer i et sæt. Det bruger hash-funktioner til at gøre dette ved at beregne hash-værdien af hvert element, der tilføjes, og sammenligne den med de andre elementer i mængden.
Spørgsmål: Hvilken type datastruktur er et Bloom-filter?
Svar: Et Bloom-filter er en probabilistisk datastruktur, hvilket betyder, at der er mulighed for at få falske positive, men ikke falske negative resultater.
Spørgsmål: Hvem foreslog Bloom-filteret?
Svar: Edward Bloom foreslog Bloom-filteret i 1970.
Spørgsmål: Hvad var Edwards eksempel på brugen af hans teknik?
Svar: Edwards eksempel var en afbinding af ca. 500 000 ord; han fandt ud af, at han ved hjælp af sin teknik kunne eliminere de fleste opslag og reducere diskadgangen med 15 %.
Spørgsmål: Hvor mange bits pr. element er der behov for for 1 % falsk positiv sandsynlighed?
Svar: Der kræves mindre end 10 bits pr. element for at opnå 1 % falsk positiv sandsynlighed, uafhængigt af størrelsen eller antallet af elementer i mængden.
Spørgsmål: Er det muligt at fjerne elementer fra et bloom-filter, når de først er blevet tilføjet?
Svar: Nej, elementer kan kun tilføjes til mængden, men ikke fjernes.
Spørgsmål: Øger eller mindsker tilføjelsen af flere elementer sandsynligheden for at få et falsk positivt resultat?
Svar: Ved at tilføje flere elementer øges sandsynligheden for at få et falsk positivt resultat.
