Filtro de Bloom: estructura de datos probabilística, hashes y falsos positivos

Filtro de Bloom: guía práctica sobre estructura probabilística, funciones hash, falsos positivos, ventajas, limitaciones y aplicaciones para ahorrar memoria y acelerar búsquedas.

Un filtro de Bloom es una estructura de datos que permite a los ordenadores comprobar si un elemento determinado aparece en un conjunto de forma muy eficiente en espacio y tiempo. Para ello, los filtros de Bloom utilizan funciones hash y un arreglo de bits. Por cada elemento que se añade se calculan varios valores hash y se activan (se ponen a 1) las posiciones correspondientes en el arreglo de bits. Al consultar si un elemento pertenece al conjunto, se calculan las mismas posiciones: si alguna de ellas es 0, se sabe con certeza que el elemento no está; si todas son 1, se responde "posiblemente está", porque puede tratarse de un falso positivo. Un filtro Bloom es una estructura de datos probabilística: puede producir falsos positivos pero, en las condiciones habituales (sin eliminar elementos), no produce falsos negativos.

Cómo funciona (operaciones básicas)

Conceptualmente un filtro Bloom consiste en:

• Un arreglo de m bits inicializados a 0.
• k funciones hash independientes (o derivadas entre sí) que mapean cada elemento a k posiciones entre 0 y m-1.

Operaciones:

• Añadir(elemento): calcular h1(x), h2(x), ..., hk(x) y poner a 1 los bits en esas posiciones.
• Consultar(elemento): calcular las mismas hi(x). Si alguno de los bits en esas posiciones es 0, devolver "definitivamente no en el conjunto". Si todos son 1, devolver "posiblemente en el conjunto" (puede ser falso positivo).

Nota: con la versión básica no se soporta eliminar elementos porque poner un bit a 0 podría borrar información necesaria para otros elementos. Existen extensiones (vea más abajo) que permiten eliminar mediante contadores.

Probabilidad de falso positivo y fórmulas

Si se insertan n elementos en un filtro con m bits y k funciones hash, la probabilidad aproximada de un falso positivo es

p ≈ (1 − e^{−k n / m})^k

Para un tamaño m dado, el número óptimo de hashes que minimiza p es

k ≈ (m / n) · ln 2

Y, para obtener una probabilidad de falso positivo p deseada, el número de bits por elemento recomendado es

m / n ≈ −(ln p) / (ln 2)²

Ejemplos prácticos: para p = 1% (~0.01) se necesita alrededor de 9.6 bits por elemento; para p = 0.1% se necesitan ≈ 14.4 bits por elemento. Esto concuerda con la regla empírica mencionada: en general, se necesitan menos de 10 bits por elemento para una probabilidad de falso positivo del 1%.

Elección de funciones hash y eficiencia

Las funciones hash deben distribuir uniformemente y ser eficientes. En la práctica a menudo no se usan k funciones completamente independientes, sino técnicas como el "double hashing" (Kirsch y Mitzenmacher): generar dos hashes h1, h2 y combinar para obtener las k posiciones como h1 + i·h2 (mod m). Esto reduce costes sin degradar significativamente la probabilidad de falso positivo.

El coste de consulta y de inserción es O(k) operaciones de hashing y accesos a memoria. Elegir k demasiado grande aumenta coste por operación; elegir k demasiado pequeño aumenta la probabilidad de falsos positivos. La elección óptima depende de m/n y del objetivo p.

Historia y motivación

Edward Bloom propuso el filtro de Bloom en 1970 motivado por un problema práctico: acelerar la separación con guiones en texto. Bloom observó que almacenar patrones exactos requeriría mucha memoria y que la mayoría de los accesos podían evitarse usando una estructura probabilística que filtrara la mayoría de las búsquedas costosas. Su técnica permitía reducir mucho el número de accesos a disco empleando un área de hash mucho menor que la necesaria para un hash “perfecto”.

Variantes y formas de eliminar o adaptar filtros Bloom

• Counting Bloom filter: en lugar de bits mantiene pequeños contadores por posición; permite eliminaciones incrementando/decrementando contadores, a costa de mayor memoria.
• Scalable Bloom filter: crece dinámicamente añadiendo nuevos subfiltros cuando la probabilidad de falso positivo aumenta al agregar elementos.
• Partitioned Bloom filter: el arreglo se divide en k particiones y cada hash indexa una partición distinta; mejora la concurrencia y puede tener ventajas prácticas.
• Cuckoo filter: alternativa que almacena "huellas" (fingerprints) y permite eliminaciones con tasas de falso positivo comparables o inferiores y, en algunas cargas, menos espacio.

Usos comunes

Los filtros de Bloom se usan ampliamente cuando se necesita una prueba rápida de pertenencia con bajo consumo de memoria, por ejemplo:

• Caches y sistemas de almacenamiento en disco (p. ej. evitar accesos innecesarios a disco).
• Bases de datos distribuidas y sistemas de claves (Bigtable, HBase, Cassandra, Redis).
• Redes y protocolos (por ejemplo filtros para rutas, detección de spam o intercambio de conjuntos de direcciones).
• Sistemas de criptomoneda y listas de revocación (CRL) donde se aceptan falsos positivos raros.

Ventajas y limitaciones

Ventajas:

• Uso de memoria muy eficiente para probar pertenencia.
• Operaciones muy rápidas (accesos a memoria y hashing).
• Fácil de implementar y adaptar.

Limitaciones:

• Pueden producir falsos positivos (la tasa depende de m, n y k).
• La versión básica no admite eliminaciones sin causar falsos negativos.
• Si se insertan muchos más elementos de los previstos, la tasa de falsos positivos crece y puede perder utilidad.

Consejos prácticos

• Dimensionar m y k según el número esperado de elementos n y la probabilidad de falso positivo aceptable p, usando las fórmulas anteriores.
• Si necesita eliminaciones, use counting Bloom o un filtro alternativo como cuckoo filter.
• Para implementar múltiples hashes eficientemente, use double hashing en vez de k funciones independientes.
• Supervisar la carga: si n crece más de lo esperado, considere reconstruir o escalar el filtro (scalable Bloom).

En resumen, el filtro de Bloom es una herramienta probabilística potente y compacta para pruebas rápidas de pertenencia, con aplicaciones prácticas muy variadas. Su diseño requiere equilibrar espacio, número de hashes y la tasa de falsos positivos según los requisitos del sistema.

Preguntas y respuestas

P: ¿Qué es un filtro Bloom?

P: ¿Qué tipo de estructura de datos es un filtro de Bloom?

P: ¿Quién propuso el filtro de Bloom?

P: ¿Cuál fue el ejemplo de Edward para utilizar su técnica?

P: ¿Cuántos bits por elemento se necesitan para una probabilidad de falso positivo del 1%?

P: ¿Es posible eliminar elementos de un filtro de floración una vez que se han añadido?

P: ¿Añadir más elementos aumenta o disminuye la probabilidad de obtener un resultado falso positivo?

Búsqueda por letra