Filtre de Bloom

Un filtre de Bloom és una estructura de senyes provabilística, concebuda per Burton Howard Bloom en 1970, que és usada per a verificar si un element és membre d'un conjunt. Els falsos positius són possibles pero els falsos negatius no.

Construcció

Un eixemple de filtre de Bloom, representant el conjunt Plantilla:(x, i, z}. Les fleches coloreadas mostren les posicions en el vector de bits dels resultats d'aplicar les funcions hash a cada u dels elements. L'element w no està en el conjunt Plantilla:(x, i, z}, perque té un o més dels valors hash a 0. Per a este eixemple m = 18 i k = 3.

Inicialment tenim:

• Un conjunt $x_1,\mathrm{...}{x}_n$ de $n$ elements d'un univers $X$
• Un vector $S$ de $m$ bits, inicializados en $0$.
• Un conjunt de $k$ funcions hash $h_1,\dots ,h_k$, cada una de les quals donat un element de $X$ torna un valor en el domini $\{1,\dots ,m\}$ (una posició del vector $S$).

Per a agregar un element, s'aplica cada una de les funcions hash per a conseguir $k$ posicions de vector. Eixes posicions del vector es posen a $1$ en el vector $S$. En buscar un element, verifiquem si en aplicar totes les funcions hash s'obté $1$ per a cada una d'elles en el vector $S$.

Consideracions

Lo ideal seria tindre funcions hash totalment independents i aixina tindre una baixa correlació entre els valors dels camps. L'eliminació d'un element d'un filtre de Bloom, per la forma en que està construït, és impossible. No obstant, pot ser útil tindre un segon filtre de Bloom que continga els elements eliminats. La provabilitat d'un fals positiu es pot estimar per

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

Açò nos dona una idea dels valors de $m$ i el valor de $k$ a fixar per a obtindre l'objectiu concret en cada moment.

Referències

Tesis de mestrage en Rets de Senyes. Detecció d'intrusos en rets de senyes en captura distribuïda i processament estadístic. Britos José Daniel. UNLP-Argentina. 2010

• Mastering Bitcoin. Unlocking Digital Cryptocurrencies. Andreas M. Antonopoulos. O'Reilly 2014

Tesis doctoral. Algoritmes d'agrupació per a fluix de senyes en entorns centralisats i distribuïts. Mar Callau-Zori. Universitat Politècnica de Madrit. 2012