Bloom filter

I datavitenskap , og mer presist i algoritmer , er et Bloom-filter en datastruktur oppfunnet av Burton Howard Bloom i 1970 . Det er en implementering av den abstrakte typen Ensemble . Denne strukturen er sannsynlig , det vil si at den bruker sannsynligheter, og korreksjonen er sannsynlig. Mer presist, når man tester for tilstedeværelsen av et element i et sett, gjør et Bloom-filter det mulig å vite:

med sikkerhet fraværet av et element (det kan ikke være en falsk negativ );
med en viss sannsynlighet tilstedeværelsen av et element (det kan være falske positive ).

Størrelsen på et Bloom-filter er fast og uavhengig av antall elementer som finnes, noe som gjør det til en veldig kompakt struktur. Ulempen er imidlertid at det er flere falske positive enn det er elementer i strukturen. Prinsippet for filteret er det samme som for hashing .

Beskrivelse

Et Bloom-filter består av en rekke bits med størrelse m, samt en samling k hash-funksjoner . Hver hashfunksjon knytter ethvert element til en celle i matrisen. Generelt er k en konstant som avhenger av ønsket falsk positiv hastighet, mens m er proporsjonal med k og antall elementer som skal legges til. ${\ displaystyle h_ {1}, \ prikker, h_ {k}}$

Formell beskrivelse

La U være universet av alle elementene som settet som vurderes kan inneholde. For eksempel er U settet med 32-biters heltall, eller et sett med ord. Filteret har to komponenter:

T: et utvalg av biter med størrelse m hver boks er initialisert til 0. (indeksert fra 1 til m)
$(h_ {i}) _ {{1 \ leq i \ leq k}}$ : k hash-funksjoner av . ${\ displaystyle U \ rightarrow [\! [1, m] \!]}$

Operasjoner

For å legge til et element legger vi 1s i ledetrådene . ${\ displaystyle e}$ ${\ displaystyle h_ {1} (e), \ dots, h_ {k} (e)}$

For å teste om et element er til stede, sjekker vi at indekscellene alle inneholder en 1. Medlemskapstesten kan komme tilbake når elementet er fraværende, det er en falsk positiv. ${\ displaystyle e}$ ${\ displaystyle h_ {1} (e), \ dots, h_ {k} (e)}$

Elementene kan ikke fjernes fra helheten (selv om det er mulig med noen varianter som Bloom-filtre ved å telle (in) ).

Eiendommer

Minne plass

Blooms filter bruker konstant plass. Dette er hans hovedinteresse.

Andel av falske positive

Det er mulig å vurdere andelen falske positive som en funksjon av forskjellige parametere. Så hvis vi vurderer en hash-funksjon som velger et element i settet likt, og m representerer antall bits i matrisen, er sannsynligheten for at en gitt bit blir igjen ved 0 av en funksjon av hash gitt når du setter inn et element er verdt . ${\ displaystyle 1- {1 \ over m}}$

La oss generalisere dette til et sett som inneholder nøyaktig k hash-funksjoner . Sannsynligheten for at en gitt bit blir igjen ved 0 av en av hashfunksjonene når du setter inn et element er . ${\ displaystyle \ left (1- {1 \ over m} \ right) ^ {k}}$

Hvis vi nå vurderer at vi setter inn n- elementer (for eksempel tegnstrenger osv.), Er sannsynligheten for at en gitt bit er verdt 0 verdt . Vi utleder at sannsynligheten for at denne biten er lik 1 er ${\ displaystyle \ left (1- {1 \ over m} \ right) ^ {kn}}$ ${\ displaystyle 1- \ left (1- {1 \ over m} \ right) ^ {kn}}$

Således, hvis vi tester sannsynligheten for tilstedeværelse av et element som ikke er i settet, har hver posisjon k sannsynligheten ovenfor til å være 1. Hvis vi antar (og denne antagelsen er falsk) at disse hendelsene er uavhengige, er sannsynligheten for at alle k er lik 1 (utløser en falsk-positiv) følger av forrige beregninger: $\ left (1- \ left [1- {1 \ over m} \ right] ^ {{nk}} \ right) ^ {k} \ approx \ left (1-e ^ {{- kn \ over m} }} \ høyre) ^ {k}$

Ovennevnte formel forutsetter at sannsynligheten for at hver bit er 1 er uavhengig av de andre bitene, noe som er falsk, og kan føre til betydelig forskjellige resultater når den er høy. Tvert imot, når forholdet er lavt, har feilfrekvensen faktisk en tendens til den ovennevnte verdien. ${\ displaystyle {\ frac {m} {n}}}$ ${\ frac {m} {n}}$

Den eksakte formelen er mer kompleks, og er verdt:

${\ displaystyle P = {\ frac {m!} {m ^ {k (n + 1)}}} \ sum _ {i = 1} ^ {m} \ sum _ {j = 1} ^ {i} ( -1) ^ {ij} {\ frac {j ^ {kn} i ^ {k}} {(mi)! J! (Ij)!}}}$

Denne verdien kan beregnes rekursivt. Imidlertid er det enkelt å bruke følgende rammeverk, gitt av Bose et al. :

${\ displaystyle \ left (1- \ left [1- {1 \ over m} \ right] ^ {nk} \ right) ^ {k} <P <\ left (1- \ left [1- {1 \ over m} \ høyre] ^ {nk} \ høyre) ^ {k} \ ganger \ venstre (1 + O \ venstre ({\ frac {k} {p}} {\ sqrt {\ frac {\ ln nk \ ln p } {m}}} \ høyre) \ høyre)}$

Bruker

Database

Et Bloom-filter gjør det mulig å unngå unødvendige anrop til en veldig stor database ved umiddelbart å sjekke fraværet av en ønsket rad. Siden filteret ikke er perfekt, vil unødvendig forskning imidlertid finne sted i visse tilfeller, men en stor del vil likevel unngås, og dermed multiplisere antall nyttige forespørsler som er mulig for gitt materiale. Denne metoden brukes av Google i deres distribuerte database, BigTable .

Bioinformatikk

Bloom-filtre brukes i bioinformatikk for raskt å søke etter mønstre i store genomiske datasett.

Pakkeinspeksjon

Denne typen filter brukes også til å utføre dyp pakkeinspeksjon , Av årsakene ovenfor. Deres implementering på maskinvarenivå har gjort det mulig å utføre dyp pakkeinspeksjon i nettverkshastighet.

Peer-to-peer flow

Det optimaliserer også flyten mellom jevnaldrende I et peer-to-peer-datanettverk, som Gnutella .

HTML-gjengivelse

Dette filteret brukes i HTML-gjengivelsesmotorer for å øke ytelsen til CSS- velgerne .

Referanser

" Bloom-filtre, streamingalgoritmer, count-min-skissen " , på University of Illinois ,2016.
Antoine Genitrini, “ Advanced Algorithmics: Hash Method ” , om Pierre-et-Marie-Curie University ,2016.
(i) Ken Christensen, Allen Roginsky Miguel Jimeno, " En ny analyse av falske positive av en Bloom filter " , Information Processing Letters , vol. 110, n o 212010, s. 944-949 ( les online ).
(in) Prosenjit Bose, Hua Guo Evangelos Kranakis Anil Maheshwari, Pat Morin, Jason Morrison, Michiel Smid, Yihui Tang, " On the false-positive rate of Bloom filters " , Information Processing Letters , vol. 108, n o 4,2008, s. 210-213 ( les online ).
Fay Chang, Jeffrey Dean, Sanjay Ghemawat, Wilson C Hsieh, Deborah A Wallach, Mike Burrows, Tushar Chandra, Andrew Fikes og Robert E Gruber, " Bigtable: Et distribuert lagringssystem for strukturerte data, ", ACM Transactions on Computer Systems ( TOCS) , ACM, vol. 26, n o to2008, s. 4 ( les online )
Camille Marchet, " Datastrukturer basert på k-merer for spørring av store samlinger av sekvenseringsdatasett " ,2019
Inspeksjon av dyp pakke ved bruk av parallelle Bloom-filtre
Sasu Tarkoma, “ Overlay and P2P Networks Unstructured networks ” ,2014.
(i) Nicole Sullivan, " CSS Selector Performance har endret seg! (For det bedre) ”, i Performance Calendar ,29. desember 2011.

Bibliografi

Burton H. Bloom , " Space / Time avveininger i Hash-koding med tillatte feil ", Commun. ACM , vol. 13, n o 7,1970, s. 422-426 ( online presentasjon )

Eksterne linker

Andel av falske positive i henhold til parametrene til et Bloom-filter