Bloom filter

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^{*}),}$

utilizando las tres fórmulas juntas. ^{[ 11 ]}

Content delivery networks deploy web caches around the world to cache and serve web content to users with greater performance and reliability. A key application of Bloom filters is their use in efficiently determining which web objects to store in these web caches. Nearly three-quarters of the URLs accessed from a typical web cache are "one-hit-wonders" that are accessed by users only once and never again. It is clearly wasteful of disk resources to store one-hit-wonders in a web cache, since they will never be accessed again. To prevent caching one-hit-wonders, a Bloom filter is used to keep track of all URLs that are accessed by users. A web object is cached only when it has been accessed at least once before, i.e., the object is cached on its second request. The use of a Bloom filter in this fashion significantly reduces the disk write workload, since most one-hit-wonders are not written to the disk cache. Further, filtering out the one-hit-wonders also saves cache space on disk, increasing the cache hit rates.^[13]

Kiss et al described a new construction for the Bloom filter that avoids false positives in addition to the typical non-existence of false negatives.^[36] The construction applies to a finite universe from which set elements are taken. It relies on existing non-adaptive combinatorial group testing scheme by Eppstein, Goodrich and Hirschberg. Unlike the typical Bloom filter, elements are hashed to a bit array through deterministic, fast and simple-to-calculate functions. The maximal set size for which false positives are completely avoided is a function of the universe size and is controlled by the amount of allocated memory.

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.

Replicating Bloom filters are more efficient when the number of queries is much larger than the number of elements that the Bloom filter contains, the break even point compared to Distributed Bloom filters is approximately after ${\displaystyle |{\text{PE}}|*|{\text{Elements}}|/\log _{f^{\text{+}}}|{\text{PE}}|}$ accesses, with ${\displaystyle f^{\text{+}}}$ as the false positive rate of the bloom filter.

Bloom filters can be used for approximate data synchronization as in Byers et al. (2004). Counting Bloom filters can be used to approximate the number of differences between two sets and this approach is described in Agarwal & Trachtenberg (2006).

Bloom filters can be adapted to the context of streaming data. For instance, Deng & Rafiei (2006) proposed Stable Bloom filters, which consist of a counting Bloom filter where insertion of a new element sets the associated counters to a value c, and then only a fixed amount s of counters are decreased by 1, hence the memory mostly contains information about recent elements (intuitively, one could assume that the lifetime of an element inside a SBF of N counters is around ${\displaystyle c{\tfrac {s}{N}}}$). Another solution is the Aging Bloom filter, that consists of two Bloom filter each occupying half the total available memory: when one filter is full, the second filter is erased and newer elements are then added to this newly empty filter.^[44]

However, it has been shown^[45] that no matter the filter, after n insertions, the sum of the false positive ${\displaystyle FP}$ and false negative ${\displaystyle FN}$ probabilities is bounded below by $${\displaystyle FP+FN\geq 1-{\frac {1-\left(1-{\frac {1}{L}}\right)^{m}}{1-\left(1-{\frac {1}{L}}\right)^{n}}}}$$ where L is the amount of all possible elements (the alphabet size), m the memory size (in bits), assuming ${\displaystyle n>m}$. This result shows that for L big enough and n going to infinity, then the lower bound converges to ${\displaystyle FP+FN=1}$, which is the characteristic relation of a random filter. Hence, after enough insertions, and if the alphabet is too big to be stored in memory (which is assumed in the context of probabilistic filters), it is impossible for a filter to perform better than randomness. This result can be leveraged by only expecting a filter to operate on a sliding window rather than the whole stream. In this case, the exponent n in the formula above is replaced by w, which gives a formula that might deviate from 1, if w is not too small.

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.