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.
Construcción
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 de n elementos de un universo X
Un vector S de m bits todos a 0
Un conjunto de k funciones hash diferentes , cada una de las cuales dado un valor de X devuelve un valor en el dominio {1,..,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
La búsqueda de un elemento devuelve true si al aplicar todas las funciones hash todas las componentes que devuelve tienen un 1 en el vector S
Consideraciones
Lo ideal sería tener funciones hash totalmente independientes y así tener una baja correlación entre el valor 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
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
Los filtros de Bloom se suelen usar para:
Acelerar la búsqueda de elementos. Si el filtro devuelve false entonces es seguro que el elemento no se encuentra en el conjunto
Realizar búsquedas sin especificar claramente lo buscado (protegiendo su privacidad)
Referencias
Tesis de maestría en Redes de Datos. Detección de intrusos en redes de datos con captura distribuida y procesamiento estadístico. Britos José Daniel. UNLP-Argentina. 2010
Mastering Bitcoin. Unlocking Digital Cryptocurrencies. Andreas M. Antonopoulos. O'Reilly 2014
Tesis doctoral. Algoritmos de agrupación para flujos de datos en entornos centralizados y distribuidos. Mar Callau-Zori. Universidad Politécnica de Madrid. 2012
Datos:Q885373
Multimedia:Bloom filter / Q885373
Octubre 10, 2022
filtro, bloom, filtro, bloom, estructura, datos, probabilística, concebida, burton, howard, bloom, 1970, usada, para, verificar, elemento, miembro, conjunto, falsos, positivos, posibles, pero, falsos, negativos, Índice, construcción, consideraciones, aplicacio. Un filtro de Bloom es una estructura de datos probabilistica 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 Indice 1 Construccion 2 Consideraciones 3 Aplicaciones 4 ReferenciasConstruccion Editar 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 esta en el conjunto x y z porque tiene uno o mas de los valores hash a 0 Para este ejemplo m 18 y k 3 Inicialmente tenemos Un conjunto x 1 x n displaystyle x 1 x n de n elementos de un universo X Un vector S de m bits todos a 0 Un conjunto de k funciones hash diferentes h 1 h k displaystyle h 1 h k cada una de las cuales dado un valor de X devuelve un valor en el dominio 1 m una posicion 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 La busqueda de un elemento devuelve true si al aplicar todas las funciones hash todas las componentes que devuelve tienen un 1 en el vector SConsideraciones EditarLo ideal seria tener funciones hash totalmente independientes y asi tener una baja correlacion entre el valor de los campos La eliminacion de un elemento de un filtro de Bloom por la forma en que esta construido es imposible Sin embargo puede ser util tener un segundo filtro de Bloom que contenga los elementos eliminados La probabilidad de un falso positivo se puede estimar por 1 e k n m k displaystyle 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 momentoAplicaciones EditarLos filtros de Bloom se suelen usar para Acelerar la busqueda de elementos Si el filtro devuelve false entonces es seguro que el elemento no se encuentra en el conjunto Realizar busquedas sin especificar claramente lo buscado protegiendo su privacidad Referencias EditarTesis de maestria en Redes de Datos Deteccion de intrusos en redes de datos con captura distribuida y procesamiento estadistico Britos Jose Daniel UNLP Argentina 2010 Mastering Bitcoin Unlocking Digital Cryptocurrencies Andreas M Antonopoulos O Reilly 2014 Tesis doctoral Algoritmos de agrupacion para flujos de datos en entornos centralizados y distribuidos Mar Callau Zori Universidad Politecnica de Madrid 2012 Datos Q885373 Multimedia Bloom filter Q885373 Obtenido de https es wikipedia org w index php title Filtro de Bloom amp oldid 142376574, wikipedia, wiki, leyendo, leer, libro, biblioteca,