Filtro de Bloom

From Wikipedia, the free encyclopedia

Un filtro de Bloom es una estructura de datos probabilística, concebida por Burton Howard Bloom en 1970, que es usada para verificar si un elemento es miembro de un conjunto. Los falsos positivos son posibles pero los falsos negativos no.

Un ejemplo de filtro de Bloom, representando el conjunto { $x$ , $y$ , $z$ }. Las flechas coloreadas muestran las posiciones en el vector de bits de los resultados de aplicar las funciones hash a cada uno de los elementos. El elemento $w$ no está en el conjunto { $x$ , $y$ , $z$ }, porque tiene uno o más de los valores hash a 0. Para este ejemplo $m$ = 18 y $k$ = 3.

Inicialmente tenemos:
- Un conjunto ${x_{1},...x_{n}}$ de $n$ elementos de un universo $X$
- Un vector $S$ de $m$ bits, inicializados en $0$ .
- Un conjunto de $k$ funciones hash ${h_{1},\ldots ,h_{k}}$ , cada una de las cuales dado un elemento de $X$ devuelve un valor en el dominio $\{1,\ldots ,m\}$ (una posición del vector $S$ ).
Para agregar un elemento, se aplica cada una de las funciones hash para conseguir $k$ posiciones de vector. Esas posiciones del vector se ponen a $1$ en el vector $S$ .
Al buscar un elemento, verificamos si al aplicar todas las funciones hash se obtiene $1$ para cada una de ellas en el vector $S$ .

Consideraciones

Lo ideal sería tener funciones hash totalmente independientes y así tener una baja correlación entre los valores de los campos.
La eliminación de un elemento de un filtro de Bloom, por la forma en que está construido, es imposible. Sin embargo, puede ser útil tener un segundo filtro de Bloom que contenga los elementos eliminados.
La probabilidad de un falso positivo se puede estimar por

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

Esto nos da una idea de los valores de

m

y el valor de

k

a fijar para obtener el objetivo concreto en cada momento.

Aplicaciones

Referencias

Related Articles

Wikiwand AI