Los filtros de Bloom me recuerdan a Cruz y Raya

Pues sí, siempre que oigo hablar de los filtros de Bloom me viene a la cabeza el dúo Cruz y Raya, y la escena en la que decían "Si no es por no ir, si hay que ir se va, pero ir pa ná es tontería".

Los filtros de Bloom

Y es que los filtros de Bloom nos permiten saber de forma muy eficiente "si hay que ir o no" a hacer algo y, en consecuencia, nos pueden evitar tener que ir en balde.

Los filtros de Bloom sirven para preguntar si un elemento está en un conjunto, y la respuesta puede ser:

  • "no, el elemento no está en el conjunto", de forma rotunda, siempre fiable, o bien
  • "puede ser que el elemento esté en el conjunto", con un grado de certidumbre aproximado.

Esta imprecisión en el valor afirmativo es, precisamente, la clave de su eficiencia. Si uno quisiese obtener una respuesta exacta entonces almacenaría los elementos en un conjunto normal y ya está.

Pero a veces el conjunto normal es tan grande, con millones o cientos de millones de entradas (todos los usuarios de una red social, o todas las transacciones realizadas el último mes, o todos los usuarios que hayan realizado un pedido en las últimas 24 horas) que no nos cabe en la memoria, y hay que guardarla en el disco, o en la red.

Y, claro, preguntar al disco, o a la red, suele ser lento y caro.

Los filtros de Bloom nos permiten conocer la respuesta "imprecisa" de forma muchísimo más eficiente, ocupando muchísima menos memoria. Y si la respuesta del filtro es que el elemento no está en el conjunto entonces podemos evitar tener que ir a buscarlo al disco, o a la red, ahorrándonos el paseo. Como decían los de Cruz y Raya, "si no es por no ir, pero ir 'pa ná' es tontería".

Los filtros son tan eficientes que siempre tardan lo mismo en responder, independientemente de si en el conjunto hay un único elemento o diez mil millones de elementos. Y el coste de inserción de nuevos elementos es, también, constante.

Obviamente la precisión de la respuesta afirmativa depende del tiempo de respuesta y del número de elementos a guardar. Es decir, si queremos un filtro de Bloom que sea muy preciso (que nos de pocos "falsos positivos" en sus respuestas) entonces necesitaremos más memoria que un filtro de Bloom menos preciso, y la respuesta será también ligeramente más lenta.

Esta calculadora sirve para saber cuánto puede ocupar un filtro Bloom en memoria dependiendo del número de elementos que tenga el conjunto y de la precisión que queramos en la respuesta (el número de falsos positivos). Algunos números rápidos:

Nº elementosFalsos positivosTamaño en memoria
cien millonesuno de cada diez mil 228 Mb.
cien millonesuno de cada mil 171 Mb.
cien millonesuno de cada cien 114 Mb.

Por cierto, podemos experimentar interactivamente con los filtros Bloom en esta página de Jason Davies, que nos permite insertar cadenas en un filtro de Bloom que podemos ver, y preguntar después al filtro si las palabras que hemos insertado están o no en el conjunto. Muy didáctico.

Aplicaciones prácticas

Hay muchísimos ejemplos prácticos del uso de filtros de Bloom:

Para ir terminando

En resumen: los filtros Bloom nos permiten evitar realizar operaciones muy costosas con una eficiencia estupenda, y en consecuencia acelerar enormemente procesos que de otro modo serían muy lentos.

Finalmente, y ahora que ya sabemos qué son los filtros Bloom y para qué sirven, quizá nos interese leer sobre la "paradoja de Bloom", para saber cuándo no hay que usarlos.

Si es que, como decían los de Cruz y Raya, no es por no usar los filtros Bloom, pero a veces usarlos "pa ná" también puede ser una tontería.