Bloom filter

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 10 februari 2020; kontroller kräver 5 redigeringar .

Bloom- filter är en probabilistisk datastruktur som uppfanns av Burton Bloom 1970 [1] , som gör det möjligt att kontrollera om ett element tillhör en uppsättning . I det här fallet är det möjligt att få en falsk positiv (det finns inget element i uppsättningen, men datastrukturen rapporterar att det är det), men inte ett falskt negativt .

Bloom-filtret kan använda vilken mängd minne som helst , förinställt av användaren, och ju större det är, desto mindre sannolikt är det falskt positivt. Funktionen att lägga till nya element till uppsättningen stöds, men inte att ta bort befintliga (såvida inte modifiering med räknare används).

Beskrivning av datastrukturen

Bloom-filtret är en bitmapp av m bitar . Initialt, när datastrukturen lagrar den tomma uppsättningen , sätts alla m bitar till noll. Användaren måste definiera k oberoende hashfunktioner h 1 , …, h k , som var och en mappar en uppsättning element till en uppsättning av potens m. (Med andra ord tilldelar hashfunktionen ett tal från 1 till m till varje element.) För varje element e är bitarna i arrayen med talen h 1 ( e ), ..., h k ( e ) lika med värdena för hashfunktionerna är inställda på 1.

För att kontrollera om element e tillhör uppsättningen av lagrade element, är det nödvändigt att kontrollera tillståndet för bitarna h 1 ( e ), ..., h k ( e ). Om minst en av dem är lika med noll, kan elementet inte tillhöra mängden (annars, när det lades till, skulle alla dessa bitar sättas). Om de alla är lika med en, så säger datastrukturen att e kan tillhöra mängden. I det här fallet kan två situationer uppstå: antingen hör elementet verkligen till mängden, eller så sattes alla dessa bitar av en slump när andra element lades till, vilket är källan till falska positiva resultat i denna datastruktur.

Oberoendet av hashfunktionerna säkerställer den minsta sannolikheten för upprepning av index hk ( e ) genom att minimera antalet bitar som är satt till 1 flera gånger. (Och detta är en viktig källa till falska positiva resultat.)

Falsk positiv sannolikhet

Låt bitarrayens storlek vara lika med m bitar och k hashfunktioner ges. Antag att uppsättningen hashfunktioner väljs slumpmässigt, och för varje element x tilldelar varje hashfunktion h i den en av platserna i bitmappen med lika sannolikhet

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

och dessutom är värdena kollektivt oberoende slumpvariabler ( för att förenkla efterföljande analys). $Hej X)$

Då är sannolikheten att en enhet inte kommer att skrivas till någon p -te bit under operationen att infoga nästa element lika med

\Pr(h_{1}(x)\neq p\cap \ldots \cap h_{k}(x)\neq p)=\Pr(h_{i}(x)\neq p)^{k}= \left(1-{\frac {1}{m}}\right)^{k}.

Och sannolikheten att den p -te biten förblir lika med noll efter att ha infogat n olika element x 1 , ..., x n i det initialt tomma Bloom-filtret är lika 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}\approx e^{-kn/m}

för tillräckligt stor m med tanke på den andra anmärkningsvärda gränsen .

Ett falskt positivt är att för något element y som inte är lika med något av de infogade elementen kommer alla k bitar med siffrorna h i ( y ) att vara icke-noll, och Bloom-filtret kommer felaktigt att svara att y ingår i mängden av insatta element. Sannolikheten för en sådan händelse är ungefär lika med

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

Uppenbarligen minskar denna sannolikhet med ökande m (storleken på bitarrayen) och ökar med ökande n (antalet infogade element). För fasta m och n är det optimala antalet k (antalet hashfunktioner) som minimerar det

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

I det här fallet är sannolikheten för ett falskt positivt lika med

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

Som en konsekvens bör du notera att för att Bloom-filtret ska stödja en given gränsad falsk positiv sannolikhet måste bitmappens storlek vara linjärt proportionell mot antalet infogade element.

Egenskaper

Till skillnad från många andra datastrukturer (som hashtabeller ) som också lagrar många element, kan ett Bloom-filter representera den universella uppsättningen av alla möjliga element. I det här fallet är alla bitar i dess bitmapp lika med en.
Föreningen och skärningen av två Bloom-filter av samma storlek och med samma uppsättning hashfunktioner kan implementeras genom bitvisa ELLER- och OCH- operationer på deras bitmappar.

Applikation

Jämfört med hashtabeller kan Bloom-filtret hantera flera storleksordningar mindre minne, vilket offra determinism. Det används vanligtvis för att minska antalet förfrågningar om icke-existerande data i en datastruktur med dyrare åtkomst (till exempel placerad på en hårddisk eller nätverksdatabas), det vill säga för att "filtrera" förfrågningar till den.

Exempel på praktiska tillämpningar:

Squid- proxyn använder bloomfilter för alternativet cachesammandrag .
Google BigTable använder Bloom-filter för att minska antalet hårddiskträffar när man kontrollerar om det finns en viss rad eller kolumn i en databastabell. [2]
Datorprogram för stavningskontroll.

Se även

Blomfilter med räkning

Anteckningar

↑ Bloom, Burton H. (1970), Space/time trade-offs in hash coding with allowable errors , Communications of the ACM vol. 13 (7): 422–426 , DOI 10.1145/362686.362692
↑ Bigtable: Ett distribuerat lagringssystem för strukturerad data . Hämtad 30 juli 2012. Arkiverad från originalet 8 februari 2015. (obestämd)