Entender los filtros Bloom con ejemplos

 (llimllib.github.io)
2 puntos por GN⁺ 2025-07-01 | 1 comentarios | Compartir por WhatsApp
  • Un filtro Bloom es una estructura de datos que permite filtrar rápidamente si algo pertenece a un conjunto grande usando poca memoria, y solo distingue entre “definitivamente no está” y “podría estar”
  • La clave está en un vector de bits y varias funciones hash; al insertar, se ponen en 1 los bits en las posiciones apuntadas por los resultados hash
  • Al consultar, si alguna de esas posiciones sigue en 0, el elemento puede descartarse, pero aunque todas estén en 1, todavía existe la posibilidad de un falso positivo
  • Las funciones hash deben ser independientes, distribuirse de forma cercana a uniforme y además ser rápidas; hay un caso en que cambiar de md5 a murmur dio una mejora de velocidad de aproximadamente 800%
  • La precisión y el costo del filtro dependen del equilibrio entre la cantidad esperada de elementos n, el número de bits m y la cantidad de hashes k; tanto la inserción como la consulta son de orden O(k)

Cómo funciona un filtro Bloom

  • Un filtro Bloom es una estructura de datos probabilística para determinar de forma rápida y eficiente en memoria si un elemento pertenece a un conjunto
  • El resultado se limita a dos posibilidades
    • el elemento definitivamente no está en el conjunto
    • el elemento podría estar en el conjunto
  • Su estructura interna es un vector de bits; al agregar un elemento, la entrada se pasa por varias funciones hash
  • Luego se ponen en 1 los bits en los índices señalados por cada valor hash y así termina la inserción
  • En el ejemplo se usan Fnv y Murmur como funciones hash simples

Verificación de pertenencia y falsos positivos

  • La consulta usa las mismas funciones hash que se usaron al insertar
  • Si al menos uno de los bits apuntados por los valores hash está en 0, ese elemento definitivamente no está en el conjunto
  • Si todos los bits relacionados están en 1, el elemento podría estar
    • esos mismos bits podrían haber sido activados antes por otro elemento o por la combinación de varios elementos
  • Debido a estas colisiones, en los filtros Bloom existe la posibilidad de falsos positivos (false positives)

Criterios para elegir funciones hash

  • Las funciones hash de un filtro Bloom deben ser independientes, distribuirse de forma cercana a uniforme y ser lo más rápidas posible
  • Los hashes criptográficos como sha1 se usan ampliamente, pero no siempre son una buena elección para un filtro Bloom
  • Algunos ejemplos de hashes rápidos y simples son:
  • Hay un caso en el que cambiar una implementación de filtro Bloom de md5 a murmur produjo una mejora de velocidad de aproximadamente 800%

Hashes usados en implementaciones reales

  • Distintas implementaciones usan diferentes funciones hash en sus filtros Bloom

Cómo definir el tamaño del filtro y la cantidad de funciones hash

  • Un filtro Bloom permite ajustar la tasa de falsos positivos
    • un filtro más grande reduce los falsos positivos
    • un filtro más pequeño aumenta los falsos positivos
  • La tasa de falsos positivos se calcula aproximadamente como (1-e^-kn/m)^k
    • n: cantidad esperada de elementos a insertar
    • m: cantidad de bits del filtro
    • k: cantidad de funciones hash
  • Cuantas más funciones hash haya, más lentas serán la consulta y la inserción, y además el filtro se llenará más rápido
  • En cambio, si hay muy pocas funciones hash, los falsos positivos pueden volverse excesivos
  • Para valores dados de m y n, el valor óptimo de k puede elegirse como (m/n)ln(2)
  • El tamaño del filtro puede ajustarse con este proceso
    • estimar aproximadamente el valor esperado de n
    • elegir un valor de m
    • calcular el valor óptimo de k
    • calcular la tasa de error con los valores elegidos de n, m y k
    • si la tasa de error no es aceptable, cambiar m y volver a calcular

Rendimiento y condiciones de uso adecuadas

  • En un filtro Bloom con m bits y k funciones hash, tanto la inserción como la verificación de pertenencia son de orden O(k)
  • Al agregar o consultar un elemento, basta con pasarlo por k funciones hash y luego activar o revisar los bits correspondientes
  • La eficiencia de espacio depende de la tasa de error que se pueda tolerar
  • Si el rango de elementos que pueden insertarse es muy limitado, un vector de bits determinista puede ser mejor opción
  • Si no es posible estimar ni siquiera de forma aproximada cuántos elementos se insertarán, una tabla hash o un scalable Bloom filter puede ser más adecuada

Material de referencia y ejemplos de uso

Lecturas relacionadas

1 comentarios

 
GN⁺ 2025-07-01
Opiniones en Hacker News

  • Este artículo está dirigido justo a alguien como yo. Había oído el nombre filtro de Bloom y, cada vez que lo mencionaban, pensaba que tenía que investigarlo; al ver este artículo por fin lo hice, y resultó ser la introducción perfecta que quería :)

    • Conocí los filtros de Bloom hace más de 10 años, cuando me asignaron implementarlos para la función de búsqueda de iBooks.
    • Es una estructura realmente interesante. Cuando aparece un problema que necesita un filtro de Bloom, me entusiasma, aunque lamentablemente, según el área, esos casos pueden ser poco frecuentes.

  • En 2009, en la universidad, hice un filtro de Bloom con CUDA, y mi asesor había trabajado antes en Nvidia. Pero después, en mi carrera, nunca volví a hacer programación en GPU.
    Si hubiera tomado otras decisiones en ese momento, quizá habría ganado 100 millones de dólares.

    • A mí me pasó algo parecido. En 2009, por curiosidad, creo que hice una versión muy temprana de un toolkit de bioinformática optimizado para GPU usando CUDA v1 en una GeForce 8.
      Luego me fui a hacer otra cosa y me perdí una fortuna.
    • Considerando que es una idea de ciencias de la computación de 1970, eso parece poco probable. Cualquier idea que valiera la pena probar en GPU de propósito general probablemente ya estaba en la mira de muchos.
      Hace 10 años hice una implementación de hashcash en GPU, pero hoy casi no debe tener valor.
    • Como proyecto de honores de licenciatura, porté a CUDA un algoritmo de machine learning y luego simplemente me encogí de hombros y me fui a programación embebida.
    • Si hubieras comprado Bitcoin, también habrías ganado mucho más.

  • Nota para el autor: la parte interactiva está muy buena. Para mostrar la idea central con más claridad, estaría bueno dar un ejemplo de dos cadenas que tengan una colisión de hash, poner una en el primer campo de entrada y luego verificar la otra en el segundo.
    Así se puede mostrar por qué la respuesta siempre es “podría estar en el conjunto” y no “está”.

    • "bloom" y "demonstrators " colisionan. Hay que prestar atención al espacio al final de la segunda cadena.
      Ambas colisionan con fnv: 7, murmur: 12.

  • Tengo un truco que me gusta. Si a veces tienes que hacer muchas verificaciones de membresía en un conjunto que podría ser pequeño, puedes agregar de forma especulativa un filtro de Bloom de 64 bits con una función hash muy simple.
    Suena tremendamente tonto, pero el costo es tan bajo que vale la pena intentarlo como una apuesta. Si no funciona bien, apenas agrega unos 10 ns a las inserciones y a las verificaciones de membresía; si funciona, puede reducir una cantidad enorme de trabajo.

    • Chromium hace esto en varios lugares. El artículo solo enlaza el ejemplo de Safe Browsing usando murmur, pero Blink, el renderer, por lo general usa rapidhash y emplea estos microfiltros en varios sitios.
      Por ejemplo, se usan en ciertos casos de querySelector(), para prefiltrar búsquedas hash en buckets de CSS y para rechazar rápidamente elementos al buscar ciertos atributos Aria para accesibilidad. Sorprende que filtros diminutos de 32 o 64 bits funcionen, pero en la práctica suelen ser efectivos. También hay algunos filtros de Bloom más grandes. Varios de estos los agregué yo.

  • Le pedí a ChatGPT que hiciera uno en Python, y usó el enfoque de cortar el digest md5 básico para usarlo como si fueran varios hashes. Para usos no críticos me parece bien.

  • Otra visualización de los filtros de Bloom se puede ver al final de esta página:
    https://www.chrislaux.com/hashtable.html

  • Pensé que ya lo había visto antes, pero en realidad era esta otra página: https://bdupras.github.io/filter-tutorial/
    Esta página agrega un poco más de información al comparar filtros de Bloom y filtros cuckoo.

  • Hace poco implementé con un filtro de Bloom una función para evitar spam en mensajes de log. En el logger, hasheaba el mensaje, lo metía en el filtro y, si el elemento ya estaba, no imprimía el mensaje.
    Cada pocos segundos recorría el filtro y limpiaba todos los bits; encajó bien porque no tenía que preocuparme por limpiar atómicamente todos los bits del filtro. Si mientras llegaban mensajes se borraban algunos de esos bits, eso ya era suficiente para que volvieran a aparecer en el log. La implementación anterior contaba la cantidad de mensajes vistos y se saturaba en N, lo que hacía que, si cierto mensaje se repetía, solo se viera por debajo de la velocidad a la que se limpiaba el filtro.
    Fue bastante satisfactorio haber conocido los filtros de Bloom y encontrarles así, de manera natural, un uso real que produjo una gran mejora.

  • Si quieres leer más, también me gustó el artículo de Eli Bendersky sobre filtros de Bloom:
    https://eli.thegreenplace.net/2025/bloom-filters/

  • Intuitivamente, los conceptos necesarios para entender filtros de Bloom, conjuntos y tablas hash se superponen como en un 95%. Un conjunto es una tabla hash para pruebas de membresía que solo se preocupa por claves, no por valores, y un filtro de Bloom es un conjunto que aprovecha el hecho de que el hashing muchos-a-uno “comprime” el espacio de claves mediante colisiones.
    Es como usar deliberadamente una función hash que produce muchas colisiones. Si una clave específica se hasheó alguna vez, necesariamente dará positivo, pero también podría existir otra clave que haya producido el mismo hash. No es un bug, es una característica.

    • Me alegra no ser el único que entiende un filtro de Bloom como una tabla hash que no rastrea los datos reales, sino solo los buckets donde hay datos.
    • Lo clave que falta en esta explicación es que los filtros de Bloom usan varias funciones hash para reducir las colisiones. Por ejemplo, si hay 3 hashes, para decidir que una clave está en el conjunto, los tres hashes tienen que coincidir.
      Esto reduce la probabilidad de colisiones de falsos positivos y mantiene la garantía de que no haya falsos negativos.
    • Si entendiste bien los filtros de Bloom, ya estás casi listo para entender las proyecciones aleatorias y algunas implementaciones de hash sensible a la localidad.