Bloom filter

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 10. februar 2020; checks kræver 5 redigeringer .

Bloom - filter er en probabilistisk datastruktur opfundet af Burton Bloom i 1970 [1] , som gør det muligt at kontrollere, om et element tilhører et sæt . I dette tilfælde er det muligt at få en falsk positiv (der er intet element i sættet, men datastrukturen rapporterer, at det er det), men ikke en falsk negativ .

Bloom-filteret kan bruge en hvilken som helst mængde hukommelse , forudindstillet af brugeren, og jo større det er, jo mindre sandsynligt er det, at det bliver falsk positiv. Operationen med at tilføje nye elementer til sættet er understøttet, men ikke sletning af eksisterende (medmindre ændring med tællere bruges).

Beskrivelse af datastrukturen

Bloom-filteret er en bitmap på m bits . Til at begynde med, når datastrukturen gemmer det tomme sæt , sættes alle m bit til nul. Brugeren skal definere k uafhængige hash-funktioner h 1 , …, h k , som hver afbilder et sæt elementer til et sæt af potens m. (Med andre ord tildeler hash-funktionen et tal fra 1 til m til hvert element.) For hvert element e er bits af arrayet med tallene h 1 ( e ), ..., h k ( e ) lig med værdierne for hash-funktionerne er sat til 1.

For at kontrollere, om element e hører til sættet af lagrede elementer, er det nødvendigt at kontrollere tilstanden af bit h 1 ( e ), …, h k ( e ). Hvis mindst en af dem er lig med nul, kan elementet ikke tilhøre mængden (ellers ville alle disse bits blive sat, når det blev tilføjet). Hvis de alle er lig med én, så siger datastrukturen, at e kan tilhøre mængden. I dette tilfælde kan der opstå to situationer: enten hører elementet virkelig til sættet, eller også blev alle disse bit sat tilfældigt, da andre elementer blev tilføjet, hvilket er kilden til falske positiver i denne datastruktur.

Uafhængigheden af hash-funktionerne sikrer den minimale sandsynlighed for gentagelse af indeks hk ( e ) ved at minimere antallet af bit sat til 1 flere gange. (Og dette er en vigtig kilde til falske positiver.)

Falsk positiv sandsynlighed

Lad størrelsen af bitarrayet være lig med m bit, og der gives k hashfunktioner. Antag, at sættet af hashfunktioner er valgt tilfældigt, og for ethvert element x tildeler hver hashfunktion h i det et af stederne i bitmap'et med lige stor sandsynlighed

\Pr(h_{i}(x)=p)={\frac {1}{m)),\quad p=1\ldots m,

og derudover er værdierne kollektivt uafhængige tilfældige variable (for at forenkle efterfølgende analyse). $h_{i}(x)$

Så er sandsynligheden for , at en enhed ikke bliver skrevet til en eller anden p -te bit under operationen med at indsætte det næste element lig med

\Pr(h_{1}(x)\neq p\cap \ldots \cap h_{k}(x)\neq p)=\Pr(h_{i}(x)\neq p)^{k}= \venstre(1-{\frac {1}{m}}\højre)^{k}.

Og sandsynligheden for, at den p -te bit forbliver lig nul efter indsættelse af n forskellige elementer x 1 , ..., x n i det oprindeligt tomme Bloom-filter er lig med

\Pr \left(\forall i\in \{1\dots k\},\ \forall j\in \{1\ldots n\},\ h_{i}(x_{j})\neq p\right)=\left(1-{\frac {1}{m}}\right)^{kn}\ca. e^{-kn/m}

for tilstrækkeligt store m i betragtning af den anden bemærkelsesværdige grænse .

En falsk positiv er, at for et element y , der ikke er lig med nogen af de indsatte elementer, vil alle k bits med tallene h i ( y ) være ikke-nul, og Bloom-filteret vil fejlagtigt svare, at y er inkluderet i sættet af indsatte elementer. Sandsynligheden for en sådan hændelse er omtrent lig med

(1-e^{-kn/m})^{k}.

Det er klart, at denne sandsynlighed falder med stigende m (størrelsen af bitarrayet) og stiger med stigende n (antallet af indsatte elementer). For faste m og n er det optimale antal k (antallet af hash-funktioner), der minimerer det

\textstyle k={\frac {m}{n}}\ln 2\ca. 0{,}6931{\frac {m}{n}}.

I dette tilfælde er sandsynligheden for en falsk positiv lig med

2^{{-k}}\ca. {0{,}6185}^{{m/n}}.

Som en konsekvens skal du bemærke, at for at Bloom-filteret kan understøtte en given afgrænset falsk positiv sandsynlighed, skal størrelsen af bitmappet være lineært proportional med antallet af indsatte elementer.

Egenskaber

I modsætning til mange andre datastrukturer (såsom hash-tabeller ), der også gemmer mange elementer, kan et Bloom-filter repræsentere det universelle sæt af alle mulige elementer. I dette tilfælde er alle bits i dens bitmap lig med én.
Foreningen og skæringen af to Bloom-filtre af samme størrelse og med det samme sæt hash-funktioner kan implementeres ved bitvise OR- og AND - operationer på deres bitmaps.

Ansøgning

Sammenlignet med hash-tabeller kan Bloom-filteret klare sig med flere størrelsesordener mindre hukommelse, hvilket ofrer determinisme. Det bruges typisk til at reducere antallet af anmodninger om ikke-eksisterende data i en datastruktur med dyrere adgang (f.eks. placeret på en harddisk eller netværksdatabase), det vil sige at "filtrere" anmodninger til den.

Eksempler på praktiske anvendelser:

Squid- proxyen bruger bloom-filtre til muligheden for cache-opsamling .
Google BigTable bruger Bloom-filtre til at reducere antallet af harddiskhits, når der kontrolleres for eksistensen af en given række eller kolonne i en databasetabel. [2]
Computerprogrammer til stavekontrol.

Se også

Bloom filter med optælling

Noter

↑ Bloom, Burton H. (1970), Space/time trade-offs in hash coding with allowable errors , Communications of the ACM bind 13 (7): 422–426 , DOI 10.1145/362686.362692
↑ Bigtable: Et distribueret lagringssystem til strukturerede data . Hentet 30. juli 2012. Arkiveret fra originalen 8. februar 2015. (ubestemt)