Filtro Bloom

El número de funciones hash, k , debe ser un entero positivo. Dejando de lado esta restricción, para un m y n dados , el valor de k que minimiza la probabilidad de falso positivo es

${\displaystyle k={\frac {m}{n}}\ln 2.}$

El número de bits requerido, m , dado n (el número de elementos insertados) y una probabilidad de falso positivo deseada ε (y suponiendo que se utiliza el valor óptimo de k ) se puede calcular sustituyendo el valor óptimo de k en la expresión de probabilidad anterior:

${\displaystyle \varepsilon =\left(1-e^{-({\frac {m}{n}}\ln 2){\frac {n}{m}}}\right)^{{\frac {m}{n}}\ln 2}=\left({\frac {1}{2}}\right)^{{\frac {m}{n}}\ln 2}}$

que se puede simplificar a:

${\displaystyle \ln(\varepsilon )=-{\frac {m}{n}}\ln(2)^{2}.}$

Esto da como resultado:

${\displaystyle m=-{\frac {n\ln(\varepsilon )}{\ln(2)^{2}}}}$

Por lo tanto, el número óptimo de bits por elemento es

${\displaystyle {\frac {m}{n}}=-{\frac {\ln(\varepsilon )}{\ln(2)^{2}}}\approx -2.08\ln(\varepsilon )}$

con el número correspondiente de funciones hash k (ignorando la integralidad):

${\displaystyle k=-{\frac {\ln(\varepsilon )}{\ln(2)}}.}$

Esto significa que para una probabilidad de falso positivo dada ε , la longitud de un filtro Bloom m es proporcional al número de elementos que se filtran n y el número requerido de funciones hash solo depende de la probabilidad de falso positivo objetivo ε . ^{[ 9 ]}

La fórmula${\displaystyle m=-{\frac {n\ln \varepsilon }{(\ln 2)^{2}}}}$es aproximado por tres razones. Primero, y lo que menos preocupa, se aproxima a ${\displaystyle 1-{\frac {1}{m}}}$como${\displaystyle e^{-{\frac {1}{m}}}}$, que es una buena aproximación asintótica (es decir, que se cumple cuando m →∞). En segundo lugar, y lo que es más preocupante, supone que durante la prueba de pertenencia el evento de que un bit probado se establezca en 1 es independiente del evento de que cualquier otro bit probado se establezca en 1. En tercer lugar, y lo que es más preocupante, supone que${\displaystyle k={\frac {m}{n}}\ln 2}$es fortuitamente integral.

Goel y Gupta, ^{[ 10 ]} sin embargo, dan una cota superior rigurosa que no hace aproximaciones y no requiere suposiciones. Demuestran que la probabilidad de falso positivo para un filtro Bloom finito con m bits (${\displaystyle m>1}$), n elementos y k funciones hash es como máximo

${\displaystyle \varepsilon \leq \left(1-e^{-{\frac {k(n+0.5)}{m-1}}}\right)^{k}.}$

Este límite puede interpretarse como que la fórmula aproximada${\displaystyle \left(1-e^{-{\frac {kn}{m}}}\right)^{k}}$se puede aplicar con una penalización de como máximo medio elemento adicional y como máximo un bit menos.

Los filtros de Bloom son una forma de representar de manera compacta un conjunto de elementos. Es común intentar calcular el tamaño de la intersección o unión entre dos conjuntos. Los filtros de Bloom se pueden usar para aproximar el tamaño de la intersección y unión de dos conjuntos. Para dos filtros de Bloom de longitud m , sus recuentos, respectivamente, se pueden estimar como

${\displaystyle n(A^{*})=-{\frac {m}{k}}\ln \left[1-{\frac {|A|}{m}}\right]}$

y

${\displaystyle n(B^{*})=-{\frac {m}{k}}\ln \left[1-{\frac {|B|}{m}}\right].}$

El tamaño de su unión se puede estimar como

${\displaystyle n(A^{*}\cup B^{*})=-{\frac {m}{k}}\ln \left[1-{\frac {|A\cup B|}{m}}\right],}$

dónde${\displaystyle n(A\cup B)}$es el número de bits establecidos a uno en cualquiera de los dos filtros de Bloom. Finalmente, la intersección se puede estimar como

${\displaystyle n(A^{*}\cap B^{*})=n(A^{*})+n(B^{*})-n(A^{*}\cup B^{*}),}$

using the three formulas together.^[11]

Las redes de distribución de contenido (CDN) implementan cachés web en todo el mundo para almacenar y servir contenido web a los usuarios con mayor rendimiento y fiabilidad. Una aplicación clave de los filtros Bloom es su uso para determinar de forma eficiente qué objetos web almacenar en estas cachés. Casi tres cuartas partes de las URL a las que se accede desde una caché web típica son de acceso único, es decir, que los usuarios acceden solo una vez y nunca más. Almacenar este tipo de URL en una caché web supone un claro desperdicio de recursos de disco, ya que nunca se volverán a utilizar. Para evitar el almacenamiento en caché de URL de acceso único, se utiliza un filtro Bloom para realizar un seguimiento de todas las URL a las que acceden los usuarios. Un objeto web se almacena en caché solo cuando se ha accedido a él al menos una vez, es decir, se almacena en caché en su segunda solicitud. El uso de un filtro Bloom de esta manera reduce significativamente la carga de trabajo de escritura en disco, ya que la mayoría de las URL de acceso único no se escriben en la caché. Además, filtrar estas URL también ahorra espacio en la caché, lo que aumenta la tasa de aciertos. ^{[ 13 ]}

Kiss et al. describieron una nueva construcción para el filtro de Bloom que evita los falsos positivos, además de la típica inexistencia de falsos negativos. ^{[ 36 ]} La construcción se aplica a un universo finito del cual se toman los elementos del conjunto. Se basa en el esquema de prueba de grupo combinatorio no adaptativo existente de Eppstein, Goodrich y Hirschberg. A diferencia del filtro de Bloom típico, los elementos se convierten en una matriz de bits mediante funciones deterministas, rápidas y fáciles de calcular. El tamaño máximo del conjunto para el cual se evitan por completo los falsos positivos es una función del tamaño del universo y está controlado por la cantidad de memoria asignada.

Alternativamente, se puede construir un filtro Bloom inicial de la forma estándar y luego, con un dominio finito y enumerable, se pueden encontrar exhaustivamente todos los falsos positivos y, a partir de esa lista, se construye un segundo filtro Bloom; los falsos positivos en el segundo filtro se manejan de manera similar construyendo un tercero, y así sucesivamente. Como el universo es finito y el conjunto de falsos positivos se reduce estrictamente con cada paso, este procedimiento da como resultado una cascada finita de filtros Bloom que (en este dominio cerrado y finito) producirá solo verdaderos positivos y verdaderos negativos. Para verificar la pertenencia a la cascada de filtros, se consulta el filtro inicial y, si el resultado es positivo, se consulta el segundo filtro, y así sucesivamente. Esta construcción se utiliza en CRLite , un mecanismo propuesto de distribución del estado de revocación de certificados para la PKI web , y se aprovecha la Transparencia de Certificados para cerrar el conjunto de certificados existentes. ^{[ 37 ]}

Los filtros de conteo permiten implementar una operación de eliminación en un filtro Bloom sin necesidad de recrearlo. En un filtro de conteo, las posiciones de la matriz (cubetas) se extienden de un solo bit a un contador multibit. De hecho, los filtros Bloom convencionales pueden considerarse filtros de conteo con un tamaño de cubeta de un bit. Los filtros de conteo fueron introducidos por Fan et al. (2000) .

La operación de inserción se extiende para incrementar el valor de los depósitos, y la operación de búsqueda verifica que cada uno de los depósitos requeridos sea distinto de cero. La operación de eliminación consiste entonces en decrementar el valor de cada uno de los depósitos correspondientes.

El desbordamiento aritmético de los cubetas es un problema, y ​​estas deben ser lo suficientemente grandes para que este caso sea poco frecuente. Si se produce, las operaciones de incremento y decremento deben dejar el conjunto de cubetas con el valor máximo posible para conservar las propiedades de un filtro Bloom.

El tamaño de los contadores suele ser de 3 o 4 bits. Por lo tanto, los filtros Bloom de conteo utilizan de 3 a 4 veces más espacio que los filtros Bloom estáticos. En contraste, las estructuras de datos de Pagh, Pagh y Rao (2005) y Fan et al. (2014) también permiten eliminaciones, pero utilizan menos espacio que un filtro Bloom estático.

Otro problema de los filtros de conteo es su limitada escalabilidad . Dado que la tabla del filtro Bloom de conteo no se puede ampliar, es necesario conocer de antemano el número máximo de claves que se pueden almacenar simultáneamente en el filtro. Una vez superada la capacidad de la tabla, la tasa de falsos positivos aumentará rápidamente a medida que se inserten más claves.

Bonomi et al. (2006) introdujeron una estructura de datos basada en el hash d-izquierdo que es funcionalmente equivalente, pero utiliza aproximadamente la mitad del espacio que los filtros de Bloom convencionales. El problema de escalabilidad no se presenta en esta estructura de datos. Una vez superada la capacidad de diseño, las claves se pueden reinsertar en una nueva tabla hash del doble de tamaño.

La variante que optimiza el uso del espacio, propuesta por Putze, Sanders y Singler (2007), también podría utilizarse para implementar filtros de conteo, permitiendo inserciones y eliminaciones.

Rottenstreich, Kanizo y Keslassy (2012) introdujeron un nuevo método general basado en incrementos de variables que mejora significativamente la probabilidad de falsos positivos al contar filtros de Bloom y sus variantes, sin dejar de admitir eliminaciones. A diferencia del conteo de filtros de Bloom, en cada inserción de elemento, los contadores hash se incrementan mediante un incremento de variable hash en lugar de un incremento unitario. Para consultar un elemento, se consideran los valores exactos de los contadores y no solo su positividad. Si la suma representada por un valor de contador no puede componerse con el incremento de variable correspondiente para el elemento consultado, se puede devolver una respuesta negativa a la consulta.

Kim et al. (2019) muestran que el falso positivo del filtro Counting Bloom disminuye de k=1 a un punto definido${\displaystyle k_{opt}}$y aumenta desde${\displaystyle k_{opt}}$hasta el infinito positivo, y encuentra${\displaystyle k_{opt}}$en función del umbral de recuento. ^{[ 38 ]}

Los filtros de Bloom pueden organizarse en estructuras de datos distribuidas para realizar cálculos totalmente descentralizados de funciones agregadas . La agregación descentralizada permite que las mediciones colectivas estén disponibles localmente en cada nodo de una red distribuida sin necesidad de una entidad computacional centralizada para este fin. ^{[ 39 ]}

Los filtros Bloom paralelos pueden implementarse para aprovechar los múltiples elementos de procesamiento (PE) presentes en las máquinas paralelas sin recursos compartidos . Uno de los principales obstáculos para un filtro Bloom paralelo es la organización y comunicación de los datos no ordenados que, en general, se distribuyen uniformemente entre todos los PE al inicio o en las inserciones por lotes. Para ordenar los datos se pueden utilizar dos enfoques, ya sea que el filtro Bloom sobre todos los datos se almacene en cada PE, llamado filtro Bloom replicante, o que el filtro Bloom sobre todos los datos se divida en partes iguales, almacenando cada PE una parte de él. ^{[ 40 ]} Para ambos enfoques se utiliza un filtro Bloom de "disparo único" que solo calcula un hash, lo que resulta en un bit invertido por elemento, para reducir el volumen de comunicación.

Los filtros Bloom distribuidos se inician aplicando primero un hash a todos los elementos en su PE local y luego ordenándolos localmente por sus hashes. Esto se puede hacer en tiempo lineal utilizando, por ejemplo, el algoritmo de ordenación por cubetas y también permite la detección local de duplicados. La ordenación se utiliza para agrupar los hashes con su PE asignado como separador para crear un filtro Bloom para cada grupo. Después de codificar estos filtros Bloom utilizando, por ejemplo, la codificación Golomb, cada filtro Bloom se envía como un paquete al PE responsable de los valores hash que se insertaron en él. Un PE p es responsable de todos los hashes entre los valores${\displaystyle p*(s/|{\text{PE}}|)}$y${\displaystyle (p+1)*(s/|{\text{PE}}|)}$donde s es el tamaño total del filtro de Bloom sobre todos los datos. Debido a que cada elemento se aplica una sola función hash y, por lo tanto, solo se activa un bit, para verificar si un elemento se insertó en el filtro de Bloom, solo es necesario operar sobre el PE responsable del valor hash del elemento. Las operaciones de inserción únicas también se pueden realizar de manera eficiente porque solo se debe cambiar el filtro de Bloom de un PE, en comparación con los filtros de Bloom replicados, donde cada PE tendría que actualizar su filtro de Bloom. Al distribuir el filtro de Bloom global entre todos los PE en lugar de almacenarlo por separado en cada PE, el tamaño de los filtros de Bloom puede ser mucho mayor, lo que resulta en una mayor capacidad y una menor tasa de falsos positivos. Los filtros de Bloom distribuidos se pueden utilizar para mejorar los algoritmos de detección de duplicados ^{[ 41 ]} al filtrar los elementos más "únicos". Estos se pueden calcular comunicando solo los hashes de los elementos, no los elementos mismos, que son mucho más grandes en volumen, y eliminándolos del conjunto, lo que reduce la carga de trabajo para el algoritmo de detección de duplicados utilizado posteriormente.

Durante la comunicación de los hashes, los PE buscan bits que estén activados en más de uno de los paquetes recibidos, ya que esto significaría que dos elementos tienen el mismo hash y, por lo tanto, podrían ser duplicados. Si esto ocurre, se envía un mensaje que contiene el índice del bit, que también es el hash del elemento que podría ser un duplicado, a los PE que enviaron un paquete con el bit activado. Si un remitente envía varios índices al mismo PE, puede ser ventajoso codificar también los índices. Todos los elementos que no recibieron su hash de vuelta ahora tienen la garantía de no ser duplicados y no se evaluarán más; para los elementos restantes se puede utilizar un algoritmo de Reparticionamiento ^{[ 42 ]} . Primero, todos los elementos que recibieron su valor hash de vuelta se envían al PE responsable de su hash. Ahora se garantiza que cualquier elemento y su duplicado estén en el mismo PE. En el segundo paso, cada PE utiliza un algoritmo secuencial para la detección de duplicados en los elementos recibidos, que son solo una fracción de la cantidad de elementos iniciales. Al permitir una tasa de falsos positivos para los duplicados, se puede reducir aún más el volumen de comunicación, ya que los procesadores no tienen que enviar elementos con hashes duplicados; en su lugar, cualquier elemento con un hash duplicado se puede marcar como duplicado. Como resultado, la tasa de falsos positivos para la detección de duplicados es la misma que la del filtro Bloom utilizado.

El proceso de filtrado de los elementos más singulares puede repetirse varias veces modificando la función hash en cada paso. Si se utiliza un único paso de filtrado, se obtiene una baja tasa de falsos positivos; sin embargo, si se repite una vez, el primer paso puede generar una tasa de falsos positivos mayor, mientras que el segundo, aunque también mayor, procesa menos elementos, ya que muchos se han eliminado en el paso anterior. Si bien el uso de más de dos repeticiones puede reducir aún más el volumen de comunicación si el número de duplicados en un conjunto es pequeño, la ventaja de estas complicaciones adicionales es mínima.

Los filtros de Bloom replicantes organizan sus datos utilizando un algoritmo de hipercubo bien conocido para el intercambio de información, por ejemplo ^{[ 43 ].} Primero, cada PE calcula el filtro de Bloom sobre todos los elementos locales y lo almacena. Al repetir un bucle donde en cada paso i los PE envían su filtro de Bloom local sobre la dimensión i y fusionan el filtro de Bloom que reciben sobre la dimensión con su filtro de Bloom local, es posible duplicar los elementos que contiene cada filtro de Bloom en cada iteración. Después de enviar y recibir filtros de Bloom sobre todos${\displaystyle \log |{\text{PE}}|}$Las dimensiones de cada PE contienen el filtro Bloom global sobre todos los elementos.

Los filtros Bloom replicados son más eficientes cuando el número de consultas es mucho mayor que el número de elementos que contiene el filtro Bloom; el punto de equilibrio en comparación con los filtros Bloom distribuidos es aproximadamente después de${\displaystyle |{\text{PE}}|*|{\text{Elements}}|/\log _{f^{\text{+}}}|{\text{PE}}|}$accesos, con${\displaystyle f^{\text{+}}}$como la tasa de falsos positivos del filtro Bloom.

Los filtros de Bloom pueden utilizarse para la sincronización aproximada de datos, como en Byers et al. (2004) . Los filtros de Bloom de conteo pueden utilizarse para aproximar el número de diferencias entre dos conjuntos, y este enfoque se describe en Agarwal y Trachtenberg (2006) .

Los filtros de Bloom se pueden adaptar al contexto de datos en flujo. Por ejemplo, Deng y Rafiei (2006) propusieron filtros de Bloom estables, que consisten en un filtro de Bloom de conteo donde la inserción de un nuevo elemento establece los contadores asociados a un valor c , y luego solo una cantidad fija s de contadores disminuye en 1, por lo que la memoria contiene principalmente información sobre elementos recientes (intuitivamente, se podría suponer que la vida útil de un elemento dentro de un SBF de N contadores es de alrededor de${\displaystyle c{\tfrac {s}{N}}}$Otra solución es el filtro Bloom de envejecimiento, que consta de dos filtros Bloom, cada uno ocupando la mitad de la memoria total disponible: cuando un filtro está lleno, el segundo se borra y se añaden nuevos elementos a este filtro vacío. ^{[ 44 ]}

Sin embargo, se ha demostrado ^{[ 45 ]} que, independientemente del filtro, después de n inserciones, la suma de los falsos positivos${\displaystyle FP}$y falso negativo${\displaystyle FN}$Las probabilidades están acotadas inferiormente por$${\displaystyle FP+FN\geq 1-{\frac {1-\left(1-{\frac {1}{L}}\right)^{m}}{1-\left(1-{\frac {1}{L}}\right)^{n}}}}$$donde L es la cantidad de todos los elementos posibles (el tamaño del alfabeto), m el tamaño de la memoria (en bits), suponiendo${\displaystyle n>m}$. Este resultado muestra que para L suficientemente grande y n tendiendo a infinito, entonces el límite inferior converge a${\displaystyle FP+FN=1}$, que es la relación característica de un filtro aleatorio. Por lo tanto, después de suficientes inserciones, y si el alfabeto es demasiado grande para almacenarse en la memoria (lo cual se asume en el contexto de los filtros probabilísticos), es imposible que un filtro tenga un rendimiento mejor que el azar. Este resultado se puede aprovechar esperando que un filtro opere solo sobre una ventana deslizante en lugar de sobre todo el flujo. En este caso, el exponente n en la fórmula anterior se reemplaza por w , lo que da como resultado una fórmula que podría desviarse de 1, si w no es demasiado pequeño.

Chazelle et al. (2004) diseñaron una generalización de los filtros de Bloom que podía asociar un valor a cada elemento insertado, implementando un array asociativo . Al igual que los filtros de Bloom, estas estructuras logran una sobrecarga de espacio mínima al aceptar una pequeña probabilidad de falsos positivos. En el caso de los "filtros Bloomier", un falso positivo se define como la devolución de un resultado cuando la clave no está presente en el mapa. El mapa nunca devolverá un valor incorrecto para una clave que sí está presente.

Boldi y Vigna (2005) propusieron una generalización de los filtros de Bloom basada en retículos . Un aproximador compacto asocia a cada clave un elemento de un retículo (los filtros de Bloom estándar son el caso del retículo booleano de dos elementos). En lugar de un arreglo de bits, utilizan un arreglo de elementos del retículo. Al agregar una nueva asociación entre una clave y un elemento del retículo, calculan el máximo de los valores actuales de las k posiciones del arreglo asociadas a la clave con el elemento del retículo. Al leer el valor asociado a una clave, calculan el mínimo de los valores encontrados en las k posiciones asociadas a la clave. El valor resultante se aproxima por encima del valor original.

Esta implementación utilizó un arreglo separado para cada función hash. Este método permite cálculos hash paralelos tanto para inserciones como para consultas. ^{[ 46 ]}

Almeida et al. (2007) propusieron una variante de los filtros de Bloom que se adapta dinámicamente al número de elementos almacenados, garantizando una probabilidad mínima de falsos positivos. La técnica se basa en secuencias de filtros de Bloom estándar con capacidad creciente y probabilidades de falsos positivos más estrictas, de modo que se pueda establecer de antemano una probabilidad máxima de falsos positivos, independientemente del número de elementos que se vayan a insertar.

Los filtros espaciales de Bloom (SBF) fueron propuestos originalmente por Palmieri, Calderoni y Maio (2014) como una estructura de datos diseñada para almacenar información de ubicación , especialmente en el contexto de protocolos criptográficos para la privacidad de la ubicación . Sin embargo, la característica principal de los SBF es su capacidad para almacenar múltiples conjuntos en una sola estructura de datos, lo que los hace adecuados para una serie de escenarios de aplicación diferentes. ^{[ 47 ]} Se puede consultar la pertenencia de un elemento a un conjunto específico, y la probabilidad de falso positivo depende del conjunto: los primeros conjuntos que se ingresan en el filtro durante la construcción tienen mayores probabilidades de falso positivo que los conjuntos ingresados ​​al final. ^{[ 48 ]} Esta propiedad permite una priorización de los conjuntos, donde se pueden preservar los conjuntos que contienen elementos más "importantes".

Un filtro Bloom por capas consta de múltiples capas de filtro Bloom. Los filtros Bloom por capas permiten realizar un seguimiento de cuántas veces se agregó un elemento al filtro Bloom, comprobando en cuántas capas se encuentra dicho elemento. Con un filtro Bloom por capas, una operación de comprobación normalmente devolverá el número de la capa más profunda en la que se encontró el elemento. ^{[ 49 ]}

Un filtro Bloom atenuado de profundidad D puede considerarse como una matriz de D filtros Bloom normales. En el contexto del descubrimiento de servicios en una red, cada nodo almacena localmente filtros Bloom regulares y atenuados. El filtro Bloom regular o local indica qué servicios ofrece el propio nodo. El filtro atenuado de nivel i indica qué servicios se pueden encontrar en nodos que se encuentran a i saltos del nodo actual. El valor i se construye tomando la unión de los filtros Bloom locales para los nodos que se encuentran a i saltos del nodo. ^{[ 50 ]}

Por ejemplo, consideremos una red pequeña, como se muestra en el gráfico a continuación. Supongamos que buscamos un servicio A cuyo ID se codifica mediante hashes a los bits 0, 1 y 3 (patrón 11010). Sea el nodo n1 el punto de partida. Primero, verificamos si n1 ofrece el servicio A consultando su filtro local. Dado que los patrones no coinciden, consultamos el filtro Bloom atenuado para determinar qué nodo debería ser el siguiente salto. Observamos que n2 no ofrece el servicio A, pero se encuentra en la ruta hacia nodos que sí lo ofrecen. Por lo tanto, nos movemos a n2 y repetimos el mismo procedimiento. Rápidamente encontramos que n3 ofrece el servicio y, por lo tanto, se localiza el destino. ^{[ 51 ]}

Al utilizar filtros Bloom atenuados que constan de múltiples capas, se pueden descubrir servicios a más de una distancia de salto, evitando la saturación del filtro Bloom mediante la atenuación (desplazamiento) de los bits establecidos por fuentes más lejanas. ^{[ 50 ]}

Los filtros de Bloom se utilizan a menudo para buscar en grandes bases de datos de estructuras químicas (véase similitud química ). En el caso más simple, los elementos añadidos al filtro (denominado huella digital en este campo) son simplemente los números atómicos presentes en la molécula, o un hash basado en el número atómico de cada átomo y el número y tipo de sus enlaces. Este caso es demasiado simple para ser útil. Los filtros más avanzados también codifican recuentos de átomos, características de subestructuras más grandes como grupos carboxilo y propiedades de grafos como el número de anillos. En las huellas digitales basadas en hash, se utiliza una función hash basada en propiedades de átomos y enlaces para convertir un subgrafo en una semilla de PRNG , y los primeros valores de salida se utilizan para establecer bits en el filtro de Bloom.

Las huellas moleculares surgieron a finales de la década de 1940 como una forma de buscar estructuras químicas en tarjetas perforadas. Sin embargo, no fue hasta alrededor de 1990 que Daylight Chemical Information Systems, Inc. introdujo un método basado en hash para generar los bits, en lugar de utilizar una tabla precalculada. A diferencia del enfoque de diccionario, el método hash puede asignar bits a subestructuras que no se habían visto previamente. A principios de la década de 1990, el término "huella molecular" se consideraba distinto de "claves estructurales", pero desde entonces ha evolucionado para abarcar la mayoría de las características moleculares que se pueden utilizar para una comparación de similitud, incluidas las claves estructurales, las huellas moleculares de conteo disperso y las huellas moleculares 3D. A diferencia de los filtros Bloom, el método hash de Daylight permite que el número de bits asignados por característica sea una función del tamaño de la característica, pero la mayoría de las implementaciones de huellas moleculares tipo Daylight utilizan un número fijo de bits por característica, lo que las convierte en un filtro Bloom. Las huellas moleculares originales de Daylight podían utilizarse tanto para la comparación de similitud como para el cribado. Muchos otros tipos de huellas dactilares, como la popular ECFP2, pueden utilizarse para la detección de similitudes, pero no para el cribado, ya que incluyen características ambientales locales que generan falsos negativos al usarse como método de cribado. Aunque se construyan con el mismo mecanismo, no son filtros de Bloom porque no pueden utilizarse para filtrar.