Filtro de Bloom
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
![](http://upload.wikimedia.org/wikipedia/commons/thumb/a/ac/Bloom_filter.svg/360px-Bloom_filter.svg.png)
- 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).
- Un conjunto
- 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
🔥 Top keywords: Wikipedia:PortadaLamine YamalEurocopaNico WilliamsShannen DohertyCarlos AlcarazMarc CucurellaEspecial:BuscarNovak DjokovicRodri HernándezLuis de la Fuente CastilloDani OlmoCopa AméricaÁlvaro MorataSelección de fútbol de EspañaRobin Le NormandEurocopa 2024Cleopatra I de EgiptoDonald TrumpRichard Ríos MontoyaMikel OyarzabalDani CarvajalIñaki WilliamsHarry KaneEstadio Olímpico de BerlínAymeric LaporteGrand Slam (tenis)Jesús NavasClaudio ReyesRafael NadalCopa América 2024Selección de fútbol de InglaterraCampeonato de WimbledonEurocopa 2020Copa Mundial de FútbolCopa América 2001Unai SimónNéstor LorenzoLuke Perry