Filtro Bloom

Estructura de datos para la pertenencia aproximada a un conjunto

Un filtro Bloom es una estructura de datos probabilística que ahorra espacio , concebida por Burton Howard Bloom en 1970, que se utiliza para comprobar si un elemento es miembro de un conjunto . Es posible que se produzcan coincidencias de falsos positivos , pero no de falsos negativos ; en otras palabras, una consulta devuelve "posiblemente en el conjunto" o "definitivamente no en el conjunto". Se pueden añadir elementos al conjunto, pero no eliminarlos (aunque esto se puede solucionar con la variante de filtro Bloom de conteo); cuantos más elementos se añadan, mayor será la probabilidad de que se produzcan falsos positivos.

Bloom propuso la técnica para aplicaciones en las que la cantidad de datos de origen requeriría una cantidad de memoria imprácticamente grande si se aplicaran técnicas de hash sin errores "convencionales". Dio el ejemplo de un algoritmo de separación de palabras para un diccionario de 500.000 palabras, de las cuales el 90% sigue reglas de separación de palabras simples, pero el 10% restante requiere costosos accesos al disco para recuperar patrones de separación de palabras específicos. Con suficiente memoria central , se podría utilizar un hash sin errores para eliminar todos los accesos innecesarios al disco; por otro lado, con una memoria central limitada, la técnica de Bloom utiliza un área de hash más pequeña pero aún así elimina la mayoría de los accesos innecesarios. Por ejemplo, un área de hash de solo el 18% del tamaño necesario para un hash sin errores ideal aún elimina el 87% de los accesos al disco. ^[1]

De manera más general, se requieren menos de 10 bits por elemento para una probabilidad de falso positivo del 1%, independientemente del tamaño o la cantidad de elementos del conjunto. ^[2]

Descripción del algoritmo

Un ejemplo de un filtro Bloom que representa el conjunto { x , y , z } . Las flechas de colores muestran las posiciones en la matriz de bits a las que se asigna cada elemento del conjunto. El elemento w no está en el conjunto { x , y , z } , porque se aplica un algoritmo hash a una posición de la matriz de bits que contiene 0. Para esta figura, m  = 18 y k = 3 .

Un filtro Bloom vacío es una matriz de bits de m bits, todos configurados a 0. Está equipado con k funciones hash diferentes , que asignan elementos del conjunto a una de las m posiciones posibles de la matriz. Para que sean óptimas, las funciones hash deben estar distribuidas uniformemente y ser independientes . Normalmente, k es una constante pequeña que depende de la tasa de errores falsos deseada ε , mientras que m es proporcional a k y al número de elementos que se van a agregar.

Para agregar un elemento, introdúzcalo en cada una de las k funciones hash para obtener k posiciones de la matriz. Establezca los bits en todas estas posiciones en 1.

Para comprobar si un elemento está en el conjunto, introdúzcalo en cada una de las k funciones hash para obtener k posiciones de la matriz. Si alguno de los bits en estas posiciones es 0, el elemento definitivamente no está en el conjunto; si lo estuviera, entonces todos los bits se habrían establecido en 1 cuando se insertó. Si todos son 1, entonces el elemento está en el conjunto o los bits se han establecido por casualidad en 1 durante la inserción de otros elementos, lo que da como resultado un falso positivo . En un filtro Bloom simple, no hay forma de distinguir entre los dos casos, pero técnicas más avanzadas pueden abordar este problema.

El requisito de diseñar k funciones hash independientes diferentes puede ser prohibitivo para valores k grandes . Para una buena función hash con una salida amplia, debería haber poca o ninguna correlación entre los diferentes campos de bits de dicho hash, por lo que este tipo de hash se puede utilizar para generar múltiples funciones hash "diferentes" al dividir su salida en múltiples campos de bits. Alternativamente, se pueden pasar k valores iniciales diferentes (como 0, 1, ..., k  − 1) a una función hash que toma un valor inicial; o agregar (o anexar) estos valores a la clave. Para valores m y/o k mayores , la independencia entre las funciones hash se puede relajar con un aumento insignificante en la tasa de falsos positivos. ^[3] (Específicamente, Dillinger y Manolios (2004b) muestran la efectividad de derivar los índices k utilizando hash doble mejorado y hash triple , variantes de hash doble que son efectivamente generadores de números aleatorios simples sembrados con los dos o tres valores hash).

Eliminar un elemento de este filtro Bloom simple es imposible porque no hay forma de saber cuál de los k bits a los que se asigna debe borrarse. Aunque establecer cualquiera de esos k bits en cero es suficiente para eliminar el elemento, también eliminaría cualquier otro elemento que se asigne a ese bit. Dado que el algoritmo simple no proporciona ninguna forma de determinar si se han agregado otros elementos que afecten a los bits del elemento que se eliminará, borrar cualquiera de los bits introduciría la posibilidad de falsos negativos.

La eliminación única de un elemento de un filtro Bloom se puede simular con un segundo filtro Bloom que contenga elementos que se han eliminado. Sin embargo, los falsos positivos en el segundo filtro se convierten en falsos negativos en el filtro compuesto, lo que puede resultar indeseable. Con este enfoque, no es posible volver a agregar un elemento eliminado previamente, ya que habría que quitarlo del filtro "eliminado".

Suele suceder que todas las claves están disponibles, pero enumerarlas resulta costoso (por ejemplo, porque requieren muchas lecturas del disco). Cuando la tasa de falsos positivos es demasiado alta, se puede regenerar el filtro; este debería ser un evento relativamente poco frecuente.

Ventajas de espacio y tiempo

El filtro Bloom se utiliza para acelerar las respuestas en un sistema de almacenamiento de clave-valor. Los valores se almacenan en un disco que tiene tiempos de acceso lentos. Las decisiones del filtro Bloom son mucho más rápidas. Sin embargo, se realizan algunos accesos innecesarios al disco cuando el filtro informa un resultado positivo (para eliminar los falsos positivos). La velocidad general de respuesta es mejor con el filtro Bloom que sin él. Sin embargo, el uso de un filtro Bloom para este propósito aumenta el uso de memoria ^{[ cita requerida ]} .

Si bien corren el riesgo de falsos positivos, los filtros Bloom tienen una ventaja sustancial de espacio sobre otras estructuras de datos para representar conjuntos, como árboles de búsqueda binarios autoequilibrados , tries , tablas hash o matrices simples o listas enlazadas de las entradas. La mayoría de estos requieren almacenar al menos los elementos de datos en sí, lo que puede requerir desde una pequeña cantidad de bits, para números enteros pequeños, hasta una cantidad arbitraria de bits, como para cadenas ( los tries son una excepción ya que pueden compartir almacenamiento entre elementos con prefijos iguales). Sin embargo, los filtros Bloom no almacenan los elementos de datos en absoluto, y se debe proporcionar una solución separada para el almacenamiento real. Las estructuras enlazadas incurren en una sobrecarga de espacio lineal adicional para los punteros. Un filtro Bloom con un error del 1% y un valor óptimo de k , en contraste, requiere solo alrededor de 9,6 bits por elemento, independientemente del tamaño de los elementos. Esta ventaja proviene en parte de su compacidad, heredada de las matrices, y en parte de su naturaleza probabilística. La tasa de falsos positivos del 1% se puede reducir en un factor de diez añadiendo sólo unos 4,8 bits por elemento.

Sin embargo, si el número de valores potenciales es pequeño y muchos de ellos pueden estar en el conjunto, el filtro Bloom es superado fácilmente por la matriz de bits determinista , que requiere solo un bit para cada elemento potencial. Las tablas hash obtienen una ventaja de espacio y tiempo si comienzan a ignorar las colisiones y almacenan solo si cada contenedor contiene una entrada; en este caso, se han convertido efectivamente en filtros Bloom con k = 1. [ ^4]

Los filtros Bloom también tienen la propiedad inusual de que el tiempo necesario para agregar elementos o para verificar si un elemento está en el conjunto es una constante fija, O( k ) , completamente independiente de la cantidad de elementos que ya están en el conjunto. Ninguna otra estructura de datos de conjuntos de espacio constante tiene esta propiedad, pero el tiempo de acceso promedio de las tablas hash dispersas puede hacer que, en la práctica, sean más rápidas que algunos filtros Bloom. Sin embargo, en una implementación de hardware, el filtro Bloom se destaca porque sus k búsquedas son independientes y se pueden paralelizar.

Para entender su eficiencia espacial, es instructivo comparar el filtro Bloom general con su caso especial cuando k = 1. Si k = 1 , entonces para mantener la tasa de falsos positivos suficientemente baja, se debe establecer una pequeña fracción de bits, lo que significa que la matriz debe ser muy grande y contener largas series de ceros. El contenido de información de la matriz en relación con su tamaño es bajo. El filtro Bloom generalizado ( k mayor que 1) permite establecer muchos más bits mientras se mantiene una baja tasa de falsos positivos; si los parámetros ( k y m ) se eligen bien, aproximadamente la mitad de los bits se establecerán, ^[5] y estos serán aparentemente aleatorios, minimizando la redundancia y maximizando el contenido de información.

Probabilidad de falsos positivos

La probabilidad de falsos positivos en función del número de elementos del filtro y del tamaño del filtro . Se ha supuesto un número óptimo de funciones hash . ${\displaystyle p}$ ${\displaystyle n}$ ${\displaystyle m}$ ${\displaystyle k=(m/n)\ln 2}$

Supongamos que una función hash selecciona cada posición de la matriz con la misma probabilidad. Si m es el número de bits de la matriz, la probabilidad de que una determinada función hash no establezca en 1 un determinado bit durante la inserción de un elemento es

${\displaystyle 1-{\frac {1}{m}}.}$

Si k es el número de funciones hash y cada una no tiene correlación significativa entre sí, entonces la probabilidad de que el bit no esté establecido en 1 por ninguna de las funciones hash es

${\displaystyle \left(1-{\frac {1}{m}}\right)^{k}.}$

Podemos utilizar la identidad conocida para e ⁻¹

${\displaystyle \lim _{m\to \infty }\left(1-{\frac {1}{m}}\right)^{m}={\frac {1}{e}}}$

para concluir que, para m grande ,

${\displaystyle \left(1-{\frac {1}{m}}\right)^{k}=\left(\left(1-{\frac {1}{m}}\right)^{m}\right)^{k/m}\approx e^{-k/m}.}$

Si hemos insertado n elementos, la probabilidad de que un determinado bit siga siendo 0 es

${\displaystyle \left(1-{\frac {1}{m}}\right)^{kn}\approx e^{-kn/m};}$

La probabilidad de que sea 1 es por lo tanto

${\displaystyle 1-\left(1-{\frac {1}{m}}\right)^{kn}\approx 1-e^{-kn/m}.}$

Ahora, se prueba la pertenencia de un elemento que no está en el conjunto. Cada una de las k posiciones de la matriz calculadas por las funciones hash es 1 con una probabilidad como la indicada anteriormente. La probabilidad de que todas sean 1, lo que haría que el algoritmo afirmara erróneamente que el elemento está en el conjunto, se suele expresar como

${\displaystyle \varepsilon =\left(1-\left[1-{\frac {1}{m}}\right]^{kn}\right)^{k}\approx \left(1-e^{-kn/m}\right)^{k}.}$

Esto no es estrictamente correcto, ya que supone independencia de las probabilidades de que se establezca cada bit. Sin embargo, suponiendo que es una aproximación cercana, tenemos que la probabilidad de falsos positivos disminuye a medida que aumenta m (la cantidad de bits en la matriz) y aumenta a medida que aumenta n (la cantidad de elementos insertados).

La probabilidad real de un falso positivo, sin asumir independencia, es

${\displaystyle {\frac {1}{m^{k(n+1)}}}\sum _{i=1}^{m}i^{k}i!{m \choose i}\left\{{kn \atop i}\right\}}$

donde las llaves denotan números de Stirling del segundo tipo . ^[6]

Mitzenmacher y Upfal ofrecen un análisis alternativo que llega a la misma aproximación sin el supuesto de independencia. ^[7] Después de que se hayan añadido todos los n elementos al filtro Bloom, sea q la fracción de los m bits que están fijados a 0. (Es decir, el número de bits que todavía están fijados a 0 es qm ). Entonces, al probar la pertenencia de un elemento que no está en el conjunto, para la posición de la matriz dada por cualquiera de las k funciones hash, la probabilidad de que el bit se encuentre fijado a 1 es . Por lo tanto, la probabilidad de que todas las k funciones hash encuentren su bit fijado a 1 es . Además, el valor esperado de q es la probabilidad de que una posición de matriz dada no sea tocada por cada una de las k funciones hash para cada uno de los n elementos, que es (como arriba) ${\displaystyle 1-q}$ ${\displaystyle (1-q)^{k}}$

${\displaystyle E[q]=\left(1-{\frac {1}{m}}\right)^{kn}}$.

Es posible demostrar, sin el supuesto de independencia, que q está muy fuertemente concentrado alrededor de su valor esperado. En particular, a partir de la desigualdad de Azuma-Hoeffding , demuestran que ^[8]

${\displaystyle \Pr(\left|q-E[q]\right|\geq {\frac {\lambda }{m}})\leq 2\exp(-2\lambda ^{2}/kn)}$

Por esto, podemos decir que la probabilidad exacta de falsos positivos es

${\displaystyle \sum _{t}\Pr(q=t)(1-t)^{k}\approx (1-E[q])^{k}=\left(1-\left[1-{\frac {1}{m}}\right]^{kn}\right)^{k}\approx \left(1-e^{-kn/m}\right)^{k}}$

Como antes.

Número óptimo de funciones hash

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 falsos positivos es

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

La cantidad requerida de bits, m , dada n (la cantidad de elementos insertados) y una probabilidad de falso positivo deseada ε (y asumiendo 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}}$

Lo cual se puede simplificar así:

${\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 es aproximada por tres razones. En primer lugar, y la menos preocupante, se aproxima como , que es una buena aproximación asintótica (es decir, que se cumple cuando m →∞). En segundo lugar, y la 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 la más preocupante, supone que es fortuitamente integral. ${\displaystyle m=-{\frac {n\ln \varepsilon }{(\ln 2)^{2}}}}$ ${\displaystyle 1-{\frac {1}{m}}}$ ${\displaystyle e^{-{\frac {1}{m}}}}$ ${\displaystyle k={\frac {m}{n}}\ln 2}$

Sin embargo, Goel y Gupta ^[10] dan un límite superior riguroso que no hace aproximaciones ni requiere suposiciones. Muestran que la probabilidad de falsos positivos para un filtro Bloom finito con m bits ( ), n elementos y k funciones hash es como máximo ${\displaystyle m>1}$

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

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

Aproximación del número de elementos en un filtro Bloom

La cantidad de elementos en un filtro Bloom se puede aproximar con la siguiente fórmula:

${\displaystyle n^{*}=-{\frac {m}{k}}\ln \left[1-{\frac {X}{m}}\right],}$

donde es una estimación del número de elementos en el filtro, m es la longitud (tamaño) del filtro, k es el número de funciones hash y X es el número de bits establecidos en uno. ^[11] ${\displaystyle n^{*}}$

La unión y la intersección de conjuntos

Los filtros Bloom son una forma de representar de forma compacta un conjunto de elementos. Es habitual intentar calcular el tamaño de la intersección o unión entre dos conjuntos. Los filtros Bloom se pueden utilizar para aproximar el tamaño de la intersección y la unión de dos conjuntos. Para dos filtros 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],}$

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

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

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

Propiedades

• A diferencia de una tabla hash estándar que utiliza direccionamiento abierto para la resolución de colisiones , un filtro Bloom de un tamaño fijo puede representar un conjunto con una cantidad arbitrariamente grande de elementos; agregar un elemento nunca falla debido a que la estructura de datos se "llena". Sin embargo, la tasa de falsos positivos aumenta de manera constante a medida que se agregan elementos hasta que todos los bits del filtro se establecen en 1, momento en el que todas las consultas arrojan un resultado positivo. Con el hash de direccionamiento abierto, nunca se producen falsos positivos, pero el rendimiento se deteriora de manera constante hasta que se acerca a la búsqueda lineal.
• La unión e intersección de filtros Bloom con el mismo tamaño y conjunto de funciones hash se pueden implementar con operaciones OR y AND bit a bit , respectivamente. La operación de unión en filtros Bloom no tiene pérdidas en el sentido de que el filtro Bloom resultante es el mismo que el filtro Bloom creado desde cero utilizando la unión de los dos conjuntos. La operación de intersección satisface una propiedad más débil: la probabilidad de falso positivo en el filtro Bloom resultante es como máximo la probabilidad de falso positivo en uno de los filtros Bloom constituyentes, pero puede ser mayor que la probabilidad de falso positivo en el filtro Bloom creado desde cero utilizando la intersección de los dos conjuntos.
• Algunos tipos de código superpuesto pueden verse como un filtro Bloom implementado con tarjetas físicas con muescas en los bordes . Un ejemplo es Zatocoding , inventado por Calvin Mooers en 1947, en el que el conjunto de categorías asociadas con una pieza de información se representa mediante muescas en una tarjeta, con un patrón aleatorio de cuatro muescas para cada categoría.

Ejemplos

• Las moscas de la fruta utilizan una versión modificada de los filtros Bloom para detectar la novedad de los olores, con características adicionales que incluyen la similitud del olor nuevo con el de ejemplos experimentados previamente y el tiempo transcurrido desde la experiencia previa del mismo olor. ^[12]
• Los servidores de Akamai Technologies , un proveedor de distribución de contenido , utilizan filtros Bloom para evitar que los "one-hit-wonders" se almacenen en sus cachés de disco. Los one-hit-wonders son objetos web solicitados por los usuarios solo una vez, algo que Akamai descubrió que se aplicaba a casi tres cuartas partes de su infraestructura de almacenamiento en caché. El uso de un filtro Bloom para detectar la segunda solicitud de un objeto web y almacenar en caché ese objeto solo en su segunda solicitud evita que los one-hit-wonders entren en la caché de disco, lo que reduce significativamente la carga de trabajo del disco y aumenta las tasas de aciertos de la caché de disco. ^[13]
• Google Bigtable , Apache HBase , Apache Cassandra , ScyllaDB y PostgreSQL ^[14] utilizan filtros Bloom para reducir las búsquedas en disco de filas o columnas inexistentes. Evitar las costosas búsquedas en disco aumenta considerablemente el rendimiento de una operación de consulta de base de datos. ^[15]
• El navegador web Google Chrome utilizaba anteriormente un filtro Bloom para identificar URL maliciosas. Todas las URL se verificaban primero con un filtro Bloom local y solo si el filtro Bloom arrojaba un resultado positivo se realizaba una verificación completa de la URL (y se advertía al usuario si también arrojaba un resultado positivo). ^{[16] [17]}
• Microsoft Bing (motor de búsqueda) utiliza filtros Bloom jerárquicos de varios niveles para su índice de búsqueda, BitFunnel . Los filtros Bloom tenían un coste menor que el índice Bing anterior, que se basaba en archivos invertidos . ^[18]
• El caché proxy web de Squid utiliza filtros Bloom para los resúmenes de caché. ^[19]
• Bitcoin utilizó filtros Bloom para acelerar la sincronización de billeteras hasta que se descubrieron vulnerabilidades de privacidad con la implementación de filtros Bloom. ^[20]
• El sistema de almacenamiento de archivos Venti utiliza filtros Bloom para detectar datos almacenados previamente. ^[21]
• El verificador de modelos SPIN utiliza filtros Bloom para rastrear el espacio de estados alcanzable para problemas de verificación grandes. ^[22]
• El marco de análisis en cascada utiliza filtros Bloom para acelerar las uniones asimétricas, donde uno de los conjuntos de datos unidos es significativamente más grande que el otro (a menudo llamado unión Bloom en la literatura de bases de datos). ^[23]
• El agente de transferencia de correo (MTA) de Exim utiliza filtros Bloom en su función de límite de velocidad. ^{[ cita requerida ]}
• Medium utiliza filtros Bloom para evitar recomendar artículos que un usuario ya haya leído. ^{[24] [ ¿fuente generada por el usuario? ]}
• Ethereum utiliza filtros Bloom para encontrar rápidamente registros en la cadena de bloques Ethereum.
• Grafana Tempo utiliza filtros Bloom para mejorar el rendimiento de las consultas almacenando filtros Bloom para cada bloque de backend. Se accede a ellos en cada consulta para determinar los bloques que contienen datos que cumplen con los criterios de búsqueda proporcionados ^{[25] .}

Alternativas

Los filtros Bloom clásicos utilizan bits de espacio por cada clave insertada, donde es la tasa de falsos positivos del filtro Bloom. Sin embargo, el espacio que es estrictamente necesario para cualquier estructura de datos que desempeñe el mismo papel que un filtro Bloom es solo por clave. ^[26] Por lo tanto, los filtros Bloom utilizan un 44% más de espacio que una estructura de datos óptima equivalente. ${\displaystyle 1.44\log _{2}(1/\varepsilon )}$ ${\displaystyle \varepsilon }$ ${\displaystyle \log _{2}(1/\varepsilon )}$

Pagh et al. proporcionan una estructura de datos que utiliza bits mientras admite operaciones de tiempo esperado amortizado constante. ^[27] Su estructura de datos es principalmente teórica, pero está estrechamente relacionada con el filtro de cociente ampliamente utilizado , que se puede parametrizar para usar bits de espacio, para un parámetro arbitrario , mientras admite operaciones de tiempo constante. ^[28] Las ventajas del filtro de cociente, en comparación con el filtro Bloom, incluyen su localidad de referencia y la capacidad de admitir eliminaciones. ${\textstyle (1+o(1))n\log _{2}(1/\epsilon )+O(n)}$ ${\displaystyle (1+\delta )n\log \epsilon ^{-1}+3n}$ ${\displaystyle \delta >0}$ ${\displaystyle O(\delta ^{-2})}$

Otra alternativa al filtro Bloom clásico es el filtro cuco , basado en variantes de hash cuco que ahorran espacio . En este caso, se construye una tabla hash que no contiene claves ni valores, sino huellas digitales cortas (hashes pequeños) de las claves. Si al buscar la clave se encuentra una huella digital coincidente, entonces es probable que la clave esté en el conjunto. Los filtros cuco admiten eliminaciones y tienen una mejor localidad de referencia que los filtros Bloom. ^[29] Además, en algunos regímenes de parámetros, los filtros cuco se pueden parametrizar para ofrecer garantías de espacio casi óptimas. ^[29]

Muchas alternativas a los filtros Bloom, incluidos los filtros de cociente y los filtros de cuco , se basan en la idea de convertir las claves en huellas dactilares aleatorias de 128 bits y luego almacenar esas huellas dactilares en una tabla hash compacta. Esta técnica, que fue introducida por primera vez por Carter et al. en 1978, ^[26] se basa en el hecho de que las tablas hash compactas se pueden implementar para utilizar aproximadamente bits menos de espacio que sus contrapartes no compactas. Usando tablas hash sucintas , el uso del espacio se puede reducir a tan solo bits ^[30] mientras se admiten operaciones de tiempo constante en una amplia variedad de regímenes de parámetros. ${\displaystyle (\log n+\log \epsilon ^{-1})}$ ${\displaystyle n\log n}$ ${\displaystyle n\log _{2}(e/\epsilon )+o(n)}$

Putze, Sanders y Singler (2007) han estudiado algunas variantes de los filtros Bloom que son más rápidas o utilizan menos espacio que los filtros Bloom clásicos. La idea básica de la variante rápida es ubicar los k valores hash asociados con cada clave en uno o dos bloques que tengan el mismo tamaño que los bloques de caché de memoria del procesador (generalmente 64 bytes). Esto presumiblemente mejorará el rendimiento al reducir la cantidad de posibles errores de caché de memoria . Sin embargo, las variantes propuestas tienen el inconveniente de utilizar aproximadamente un 32% más de espacio que los filtros Bloom clásicos.

La variante que ahorra espacio se basa en el uso de una única función hash que genera para cada clave un valor en el rango donde es la tasa de falsos positivos solicitada. A continuación, la secuencia de valores se ordena y se comprime utilizando la codificación Golomb (o alguna otra técnica de compresión) para ocupar un espacio cercano a los bits. Para consultar el filtro Bloom para una clave determinada, bastará con comprobar si su valor correspondiente está almacenado en el filtro Bloom. Descomprimir todo el filtro Bloom para cada consulta haría que esta variante fuera totalmente inutilizable. Para superar este problema, la secuencia de valores se divide en pequeños bloques de igual tamaño que se comprimen por separado. En el momento de la consulta, solo será necesario descomprimir medio bloque en promedio. Debido a la sobrecarga de descompresión, esta variante puede ser más lenta que los filtros Bloom clásicos, pero esto puede compensarse con el hecho de que es necesario calcular una única función hash. ${\displaystyle \left[0,n/\varepsilon \right]}$ ${\displaystyle \varepsilon }$ ${\displaystyle n\log _{2}(1/\varepsilon )}$

Graf y Lemire (2020) describen un enfoque llamado filtro xor, en el que almacenan huellas dactilares en un tipo particular de tabla hash perfecta , lo que produce un filtro que es más eficiente en el uso de la memoria ( bits por clave) y más rápido que los filtros Bloom o Cuckoo. (El ahorro de tiempo proviene del hecho de que una búsqueda requiere exactamente tres accesos a la memoria, que pueden ejecutarse todos en paralelo). Sin embargo, la creación de filtros es más compleja que los filtros Bloom y Cuckoo, y no es posible modificar el conjunto después de la creación. ${\displaystyle 1.23\log _{2}(1/\varepsilon )}$

Extensiones y aplicaciones

Existen más de 60 variantes de filtros Bloom, muchas encuestas sobre el campo y una continua rotación de aplicaciones (ver, por ejemplo, Luo, et al ^[31] ). Algunas de las variantes difieren lo suficiente de la propuesta original como para ser brechas o bifurcaciones de la estructura de datos original y su filosofía. ^[31] Aún queda por hacer un tratamiento que unifique los filtros Bloom con otros trabajos sobre proyecciones aleatorias , detección compresiva y hash sensible a la localidad (aunque ver Dasgupta, et al ^[32] para un intento inspirado en la neurociencia).

Filtrado de caché

El uso de un filtro Bloom para evitar que los archivos de un solo uso se almacenen en un caché web redujo la tasa de escrituras en disco a casi la mitad, lo que redujo la carga en los discos y potencialmente aumentó el rendimiento del disco. ^[13]

Las redes de distribución de contenido implementan cachés web en todo el mundo para almacenar en caché y ofrecer contenido web a los usuarios con mayor rendimiento y confiabilidad. Una aplicación clave de los filtros Bloom es su uso para determinar de manera eficiente qué objetos web almacenar en estos cachés web. Casi tres cuartas partes de las URL a las que se accede desde un caché web típico son "one-hit-wonders" a las que los usuarios acceden solo una vez y nunca más. Es claramente un desperdicio de recursos de disco almacenar one-hit-wonders en un caché web, ya que nunca se volverá a acceder a ellos. Para evitar el almacenamiento en caché de one-hit-wonders, 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 antes, es decir, el objeto 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 los one-hit-wonders no se escriben en el caché de disco. Además, filtrar los one-hit-wonders también ahorra espacio de caché en el disco, lo que aumenta las tasas de aciertos de caché. ^[13]

Cómo evitar los falsos positivos en un universo finito

Kiss et al ^[33] describieron una nueva construcción para el filtro Bloom que evita los falsos positivos además de la típica inexistencia de falsos negativos. La construcción se aplica a un universo finito del que se toman los elementos del conjunto. Se basa en el esquema de prueba de grupos combinatorios no adaptativos existente de Eppstein, Goodrich y Hirschberg. A diferencia del filtro 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 que 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.

Como alternativa, se puede construir un filtro Bloom inicial de la forma estándar y luego, con un dominio finito y enumerable de forma manejable, se pueden encontrar exhaustivamente todos los falsos positivos y luego construir un segundo filtro Bloom a partir de esa lista; 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 finito y cerrado) producirán solo verdaderos positivos y verdaderos negativos. Para verificar la membresía en 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 de distribución de estado de revocación de certificados propuesto para la PKI web, y se explota la Transparencia de certificados para cerrar el conjunto de certificados existentes. ^[34]

Contando filtros Bloom

Los filtros de conteo proporcionan una forma de implementar una operación de eliminación en un filtro Bloom sin tener que volver a crear el filtro. En un filtro de conteo, las posiciones de la matriz (cubetas) se extienden de ser un solo bit a ser un contador de varios bits. De hecho, los filtros Bloom regulares 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 contenedores, y la operación de búsqueda verifica que cada uno de los contenedores requeridos sea distinto de cero. La operación de eliminación consiste entonces en disminuir el valor de cada uno de los contenedores respectivos.

El desbordamiento aritmético de los contenedores es un problema y los contenedores deben ser lo suficientemente grandes para que este caso sea poco frecuente. Si ocurre, las operaciones de incremento y decremento deben dejar el contenedor configurado en 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. Por el contrario, 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 con los filtros de conteo es la escalabilidad limitada. Debido a que la tabla de filtros Bloom de conteo no se puede expandir, se debe conocer de antemano la cantidad máxima de claves que se almacenarán simultáneamente en el filtro. Una vez que se excede la capacidad diseñada 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-left que es funcionalmente equivalente pero que utiliza aproximadamente la mitad de espacio que los filtros Bloom de conteo. El problema de escalabilidad no se produce en esta estructura de datos. Una vez que se excede la capacidad diseñada, las claves se pueden volver a insertar en una nueva tabla hash de tamaño doble.

La variante de uso eficiente del espacio de Putze, Sanders y Singler (2007) también podría usarse para implementar filtros de conteo al admitir 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 de contar filtros Bloom y sus variantes, al mismo tiempo que admite eliminaciones. A diferencia de contar filtros Bloom, en cada inserción de elementos, 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 una suma representada por un valor de contador no puede estar compuesta por el incremento de variable correspondiente para el elemento consultado, se puede devolver una respuesta negativa a la consulta.

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

Agregación descentralizada

Los filtros Bloom se pueden organizar en estructuras de datos distribuidas para realizar cálculos totalmente descentralizados de funciones agregadas . La agregación descentralizada hace que las mediciones colectivas estén disponibles localmente en cada nodo de una red distribuida sin involucrar a una entidad computacional centralizada para este propósito. ^[36]

Filtros Bloom distribuidos

Filtro Bloom distribuido de un solo disparo para detección de duplicados con tasa de falsos positivos: 6 elementos se distribuyen en 3 PE, cada uno con una matriz de bits de longitud 4. Durante el primer paso de comunicación, el PE 1 recibe el hash '2' dos veces y lo envía de vuelta al PE 2 o 3, según quién lo haya enviado después. El PE que recibe el hash '2' busca entonces el elemento con ese hash y lo marca como posible duplicado.

Los filtros Bloom paralelos se pueden implementar para aprovechar los múltiples elementos de procesamiento (PE) presentes en las máquinas paralelas sin uso compartido . 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 de manera uniforme entre todos los PE en el inicio o en las inserciones por lotes. Para ordenar los datos se pueden utilizar dos enfoques, ya sea dando como resultado un filtro Bloom sobre todos los datos almacenados en cada PE, llamado filtro Bloom replicante, o el filtro Bloom sobre todos los datos divididos en partes iguales, cada PE almacena una parte de ellos. ^[37] Para ambos enfoques se utiliza un filtro Bloom de "disparo único" que solo calcula un hash, lo que da como resultado un bit invertido por elemento, para reducir el volumen de comunicación.

Los filtros Bloom distribuidos se inician primero aplicando un hash a todos los elementos en su PE local y luego ordenándolos por sus hashes localmente. Esto se puede hacer en tiempo lineal usando, por ejemplo, la ordenación por cubos y también permite la detección de duplicados locales. La ordenación se usa 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 usando, por ejemplo, la codificación Golomb, cada filtro Bloom se envía como 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 y , donde s es el tamaño total del filtro Bloom sobre todos los datos. Debido a que cada elemento solo se aplica un hash una vez y, por lo tanto, solo se establece un solo bit, para verificar si un elemento se insertó en el filtro Bloom, solo se necesita operar en el PE responsable del valor hash del elemento. Las operaciones de inserción única también se pueden realizar de manera eficiente porque solo se debe cambiar el filtro Bloom de un PE, en comparación con la replicación de filtros Bloom donde cada PE tendría que actualizar su filtro Bloom. Al distribuir el filtro Bloom global entre todos los PE en lugar de almacenarlo por separado en cada PE, el tamaño de los filtros Bloom puede ser mucho mayor, lo que da como resultado una mayor capacidad y una menor tasa de falsos positivos. Los filtros Bloom distribuidos se pueden utilizar para mejorar los algoritmos de detección de duplicados ^[38] filtrando los elementos más "únicos". Estos se pueden calcular comunicando solo los hashes de los elementos, no los elementos en sí 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. ${\displaystyle p*(s/|{\text{PE}}|)}$ ${\displaystyle (p+1)*(s/|{\text{PE}}|)}$

Durante la comunicación de los hashes, los PE buscan bits que estén configurados en más de uno de los paquetes de recepción, ya que esto significaría que dos elementos tenían 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 configurado. Si un remitente envía múltiples índices al mismo PE, puede ser ventajoso codificar también los índices. Ahora se garantiza que todos los elementos cuyo hash no se envió de vuelta no serán duplicados y no se evaluarán más; para los elementos restantes se puede utilizar un algoritmo de repartición ^[39] . Primero, todos los elementos cuyo valor hash se envió de vuelta se envían al PE del que es responsable 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 receptores, que son solo una fracción de la cantidad de elementos iniciales. Al permitir una tasa de falsos positivos para los duplicados, el volumen de comunicación se puede reducir aún más, ya que los PE no tienen que enviar elementos con hashes duplicados y, en cambio, cualquier elemento con un hash duplicado puede marcarse simplemente como duplicado. Como resultado, la tasa de falsos positivos para la detección de duplicados es la misma que la tasa de falsos positivos del filtro Bloom utilizado.

El proceso de filtrado de los elementos más "únicos" también se puede repetir varias veces modificando la función hash en cada paso de filtrado. Si se utiliza un solo paso de filtrado, se debe generar una pequeña tasa de falsos positivos; sin embargo, si el paso de filtrado se repite una vez, el primer paso puede permitir una tasa de falsos positivos más alta, mientras que el segundo tiene una tasa más alta, pero también funciona con menos elementos, ya que muchos ya se han eliminado en el paso de filtrado anterior. Si bien el uso de más de dos repeticiones puede reducir aún más el volumen de comunicación si la cantidad de duplicados en un conjunto es pequeña, la recompensa por las complicaciones adicionales es baja.

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

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 los accesos, siendo la tasa de falsos positivos del filtro Bloom. ${\displaystyle |{\text{PE}}|*|{\text{Elements}}|/\log _{f^{\text{+}}}|{\text{PE}}|}$ ${\displaystyle f^{\text{+}}}$

Sincronización de datos

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

Filtros Bloom para transmisión de datos

Los filtros Bloom pueden adaptarse al contexto de transmisión de datos. Por ejemplo, Deng y Rafiei (2006) propusieron filtros Bloom estables, que consisten en un filtro Bloom de conteo donde la inserción de un nuevo elemento establece los contadores asociados en un valor c , y luego solo una cantidad fija s de contadores se reduce en 1, por lo tanto, 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 ). Otra solución es el filtro Bloom de envejecimiento, que consta de dos filtros Bloom, cada uno de los cuales ocupa la mitad de la memoria total disponible: cuando un filtro está lleno, el segundo filtro se borra y luego se agregan elementos más nuevos a este filtro recién vacío. ^[41] ${\displaystyle c{\tfrac {s}{N}}}$

Sin embargo, se ha demostrado ^[42] que sin importar el filtro, después de n inserciones, la suma de las probabilidades de falsos positivos y falsos negativos está limitada por debajo de donde L es la cantidad de todos los elementos posibles (el tamaño del alfabeto), m el tamaño de la memoria (en bits), asumiendo . Este resultado muestra que para L suficientemente grande y n yendo al infinito, entonces el límite inferior converge a , 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 ser almacenado en la memoria (lo que se asume en el contexto de filtros probabilísticos), es imposible que un filtro funcione mejor que la aleatoriedad. Este resultado se puede aprovechar esperando solo que un filtro funcione en una ventana deslizante en lugar de en todo el flujo. En este caso, el exponente n en la fórmula anterior se reemplaza por w , lo que da una fórmula que podría desviarse de 1, si w no es demasiado pequeño. ${\displaystyle FP}$ ${\displaystyle FN}$ $${\displaystyle FP+FN\geq 1-{\frac {1-\left(1-{\frac {1}{L}}\right)^{m}}{1-\left(1-{\frac {1}{L}}\right)^{n}}}}$$ ${\displaystyle n>m}$ ${\displaystyle FP+FN=1}$

Filtros Bloomier

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

Aproximadores compactos

Boldi y Vigna (2005) propusieron una generalización de los filtros Bloom basada en retículas . Un aproximador compacto asocia a cada clave un elemento de una retícula (los filtros Bloom estándar son el caso de la retícula booleana de dos elementos). En lugar de una matriz de bits, tienen una matriz de elementos de la retícula. Al agregar una nueva asociación entre una clave y un elemento de la retícula, calculan el máximo de los contenidos actuales de las k ubicaciones de la matriz asociadas a la clave con el elemento de la retícula. Al leer el valor asociado a una clave, calculan el mínimo de los valores encontrados en las k ubicaciones asociadas a la clave. El valor resultante se aproxima desde arriba al valor original.

Filtros Bloom con particiones paralelas

Esta implementación utilizó una matriz separada para cada función hash. Este método permite realizar cálculos hash paralelos tanto para inserciones como para consultas. ^[43]

Filtros Bloom escalables

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

Filtros de Bloom espacial

Los filtros Spatial 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 privacidad de 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 varios escenarios de aplicación diferentes. ^[44] 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. ^[45] Esta propiedad permite una priorización de los conjuntos, donde se pueden preservar los conjuntos que contienen elementos más "importantes".

Filtros Bloom en capas

Un filtro Bloom en capas consta de varias capas de filtro Bloom. Los filtros Bloom en capas permiten realizar un seguimiento de cuántas veces se agregó un elemento al filtro Bloom al verificar cuántas capas contienen el elemento. Con un filtro Bloom en capas, una operación de verificación normalmente devolverá el número de capa más profunda en la que se encontró el elemento. ^[46]

Filtros Bloom atenuados

Ejemplo de filtro Bloom atenuado: busque el patrón 11010, comenzando desde el nodo n1.

Un filtro Bloom atenuado de profundidad D puede verse como una matriz de D filtros Bloom normales. En el contexto del descubrimiento de servicios en una red, cada nodo almacena filtros Bloom regulares y atenuados localmente. 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 están a i-hops de distancia del nodo actual. El valor i-ésimo se construye tomando una unión de filtros Bloom locales para nodos que están a i-hops de distancia del nodo. ^[47]

Por ejemplo, considere una red pequeña, como se muestra en el gráfico a continuación. Digamos que estamos buscando un servicio A cuyo identificador se convierte en los bits 0, 1 y 3 (patrón 11010). Sea el nodo n1 el punto de partida. Primero, verificamos si el servicio A es ofrecido por n1 verificando su filtro local. Como los patrones no coinciden, verificamos el filtro Bloom atenuado para determinar qué nodo debería ser el siguiente salto. Vemos que n2 no ofrece el servicio A, pero se encuentra en la ruta hacia los 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 encuentra el destino. ^[48]

Al utilizar filtros Bloom atenuados que constan de múltiples capas, se pueden descubrir servicios a más de un salto de distancia, evitando al mismo tiempo la saturación del filtro Bloom al atenuar (desplazar) los bits establecidos por fuentes más alejadas. ^[47]

Búsqueda de estructura química

Los filtros Bloom se utilizan a menudo para buscar en bases de datos de estructuras químicas de gran tamaño (consulte similitud química ). En el caso más simple, los elementos añadidos al filtro (llamados 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 gráficos como el número de anillos. En 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 PRNG , y los primeros valores de salida se utilizan para establecer bits en el filtro Bloom.

Las huellas moleculares comenzaron a usarse a fines de la década de 1940 como una forma de buscar estructuras químicas buscadas 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 del diccionario, el método hash puede asignar bits para subestructuras que no se habían visto anteriormente. A principios de la década de 1990, el término "huella" se consideraba diferente de "claves estructurales", pero desde entonces el término ha crecido para abarcar la mayoría de las características moleculares que se pueden usar para una comparación de similitud, incluidas las claves estructurales, las huellas dactilares de recuento disperso y las huellas dactilares 3D. A diferencia de los filtros Bloom, el método hash de Daylight permite que la cantidad 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 dactilares similares a Daylight usan una cantidad fija de bits por característica, lo que las convierte en un filtro Bloom. Las huellas dactilares Daylight originales se podían usar tanto para fines de similitud como de cribado. Muchos otros tipos de huellas dactilares, como la popular ECFP2, se pueden utilizar para la similitud, pero no para el cribado, ya que incluyen características ambientales locales que introducen falsos negativos cuando se utilizan como cribado. Incluso si se construyen con el mismo mecanismo, no son filtros Bloom porque no se pueden utilizar para filtrar.

Véase también

• Portal de programación informática

• Esquema de conteo mínimo  : estructura de datos probabilística en informática
• Hashing de características  : vectorización de características mediante una función hash
• MinHash  – Técnica de minería de datos
• Filtro de cociente
• Lista de omisiones  : estructura de datos probabilística
• Filtros Bloom en bioinformática
• Filtro de cuco  : estructura de datos para la pertenencia aproximada a un conjunto

Referencias

Citas

1. Florecer (1970).
2. Bonomi y otros (2006).
3. Dillinger y Manolios (2004a); Kirsch y Mitzenmacher (2006).
4. Mitzenmacher y Upfal (2005).
5. Blustein y El-Maazawi (2002), págs. 21-22
6. Gopinathan, Kiran; Sergey, Ilya (21 de julio de 2020). "Certificación de certeza e incertidumbre en estructuras de consulta de membresía aproximada". Verificación asistida por computadora . Apuntes de clase en informática. Vol. 12225. Springer, Cham. págs. 279–303. doi :10.1007/978-3-030-53291-8_16. ISBN 978-3-030-53290-1. Número de pieza  7363400 .
7. Mitzenmacher y Upfal (2005), págs. 109-111, 308.
8. Mitzenmacher y Upfal (2005), pág. 308.
9. Starobinski, Trachtenberg y Agarwal (2003)
10. Goel y Gupta (2010)
11. Swamidass, S. Joshua; Baldi, Pierre (2007). "Corrección matemática para medidas de similitud de huellas dactilares para mejorar la recuperación química". Revista de información y modelado químico . 47 (3): 952–964. doi :10.1021/ci600526a. PMID  17444629.
12. Dasgupta, Sanjoy; Sheehan, Timothy C.; Stevens, Charles F.; Navlakha, Saket (18 de diciembre de 2018). "Una estructura de datos neuronales para la detección de novedades". Actas de la Academia Nacional de Ciencias . 115 (51): 13093–13098. Bibcode :2018PNAS..11513093D. doi : 10.1073/pnas.1814448115 . ISSN  0027-8424. PMC 6304992 . PMID  30509984. 
13. Maggs y Sitaraman (2015).
14. "Módulo de contribuciones del índice Bloom". Postgresql.org. 1 de abril de 2016. Archivado desde el original el 9 de septiembre de 2018. Consultado el 18 de junio de 2016 .
15. Chang y otros (2006); Apache Software Foundation (2012).
16. Yakunin, Alex (25 de marzo de 2010). "Blog de Alex Yakunin: Bonita aplicación del filtro Bloom". Blog.alexyakunin.com. Archivado desde el original el 27 de octubre de 2010. Consultado el 31 de mayo de 2014 .
17. "Problema 10896048: Transición de navegación segura desde el filtro Bloom al conjunto de prefijos. - Revisión de código". Chromiumcodereview.appspot.com . Consultado el 3 de julio de 2014 .
18. Goodwin, Bob; Hopcroft, Michael; Luu, Dan; Clemmer, Alex; Curmei, Mihaela; Elnikety, Sameh; Yuxiong, He (2017). "BitFunnel: Revisiting Signatures for Search" (PDF) . Actas de la 40.ª Conferencia Internacional ACM SIGIR sobre Investigación y Desarrollo en Recuperación de Información . págs. 605–614. doi : 10.1145/3077136.3080789 . ISBN 978-1-4503-5022-8.S2CID20123252  .​
19. Wessels (2004).
20. "Filtro Bloom | Glosario de River". River Financial . Consultado el 14 de noviembre de 2020 .
21. "Plan 9 /sys/man/8/venti". Plan9.bell-labs.com. Archivado desde el original el 28 de agosto de 2014. Consultado el 31 de mayo de 2014 .
22. "Spin - Verificación formal".
23. Mulin (1990).
24. "¿Qué son los filtros Bloom?". Medium. 2015-07-15 . Consultado el 2015-11-01 .
25. "Documentación de Grafana Tempo: almacenamiento en caché". Grafana . Consultado el 16 de noviembre de 2022 .
26. Carter, Larry; Floyd, Robert; Gill, John; Markowsky, George; Wegman, Mark (1978). "Probadores de membresía exactos y aproximados". Actas del décimo simposio anual de la ACM sobre teoría de la computación - STOC '78 . Nueva York, Nueva York, EE. UU.: ACM Press. págs. 59–65. doi :10.1145/800133.804332. S2CID  6465743.
27. Pagh, Pagh y Rao (2005).
28. Bender, Michael A.; Farach-Colton, Martin; Johnson, Rob; Kraner, Russell; Kuszmaul, Bradley C.; Medjedovic, Dzejla; Montes, Pablo; Shetty, Pradeep; Spillane, Richard P.; Zadok, Erez (julio de 2012). "No aplastes". Actas de la Fundación VLDB . 5 (11): 1627–1637. doi :10.14778/2350229.2350275. ISSN  2150-8097. S2CID  47180056.
29. Even, Tomer; Even, Guy; Morrison, Adam (marzo de 2022). «Filtro de prefijo». Actas de la Fundación VLDB . 15 (7): 1311–1323. doi :10.14778/3523210.3523211. ISSN  2150-8097.
30. Bender, Michael A.; Farach-Colton, Martín; Kuszmaul, John; Kuszmaul, William; Liu, Mingmou (9 de junio de 2022). "Sobre el equilibrio óptimo entre tiempo y espacio para las tablas hash". Actas del 54.º Simposio anual ACM SIGACT sobre teoría de la computación . Nueva York, NY, EE. UU.: ACM. págs. 1284–1297. arXiv : 2111.00602 . doi :10.1145/3519935.3519969. hdl : 1721.1/146419 . ISBN. 9781450392648.S2CID240354692  .​
31. Luo, Lailong; Guo, Deke; Ma, Richard TB; Rottenstreich, Ori; Luo, Xueshan (13 de abril de 2018). "Optimización del filtro Bloom: desafíos, soluciones y comparaciones". arXiv : 1804.04777 [cs.DS].
32. Dasgupta, Sanjoy; Sheehan, Timothy C.; Stevens, Charles F.; Navlakhae, Saket (2018). "Una estructura de datos neuronales para la detección de novedades". Actas de la Academia Nacional de Ciencias . 115 (51): 13093–13098. Bibcode :2018PNAS..11513093D. doi : 10.1073/pnas.1814448115 . PMC 6304992 . PMID  30509984. 
33. Beso, SZ; Hosszu, E.; Tapolcai, J.; Rónyai, L.; Rottenstreich, O. (2018). "Filtro de floración con zona libre de falsos positivos" (PDF) . Actas IEEE de INFOCOM . Consultado el 4 de diciembre de 2018 .
34. Larisch, James; Choffnes, David; Levin, Dave; Maggs, Bruce M.; Mislove, Alan; Wilson, Christo (2017). "CRLite: un sistema escalable para enviar todas las revocaciones de TLS a todos los navegadores". Simposio IEEE sobre seguridad y privacidad de 2017 (SP) . págs. 539–556. doi : 10.1109/sp.2017.17 . ISBN . 978-1-5090-5533-3. Número de identificación del sujeto  3926509.
35. Kim, Kibeom; Jeong, Yongjo; Lee, Youngjoo; Lee, Sunggu (11 de julio de 2019). "Análisis de filtros Bloom de conteo utilizados para el umbral de conteo". Electrónica . 8 (7): 779. doi : 10.3390/electronics8070779 . ISSN  2079-9292.
36. Pournaras, Warnier y Brazier (2013).
37. Sanders, Peter; Schlag, Sebastian; Müller, Ingo (2013). "Algoritmos de comunicación eficientes para problemas fundamentales de big data". Conferencia internacional IEEE sobre big data de 2013. págs. 15-23. doi :10.1109/BigData.2013.6691549. ISBN . 978-1-4799-1293-3. Número de identificación del sujeto  15968541.
38. Schlag, Sebastian (2013). "Eliminación de duplicados distribuidos". Instituto Tecnológico de Karlsruhe .
39. Shatdal, Ambuj; Jeffrey F. Naughton (1994). "Procesamiento de agregados en sistemas de bases de datos paralelas". Departamento de Ciencias Informáticas de la Universidad de Wisconsin-Madison : 8.
40. V. Kumar; A. Grama; A. Gupta; G. Karypis (1994). Introducción a la computación paralela. Diseño y análisis de algoritmos . Benjamin/Cummings.
41. Yoon, MyungKeun (2010). "Filtro Bloom de envejecimiento con dos búferes activos para conjuntos dinámicos". IEEE Transactions on Knowledge and Data Engineering . 22 (1): 134–138. doi :10.1109/TKDE.2009.136. S2CID  15922054.
42. Géraud-Stewart, Rémi; Lombard-Platet, Marius; Naccache, David (2020). "Aproximación a la detección óptima de duplicados en una ventana deslizante". Computing and Combinatorics . Apuntes de clase en informática. Vol. 12273. págs. 64–84. arXiv : 2005.04740 . doi :10.1007/978-3-030-58150-3_6. ISBN 978-3-030-58149-7.S2CID218581915  .​
43. Kirsch, Adam; Mitzenmacher†, Michael. "Menos hash, mismo rendimiento: creación de un mejor filtro Bloom" (PDF) . Facultad de Ingeniería y Ciencias Aplicadas de Harvard . Wiley InterScience.
44. Calderoni, Palmieri y Maio (2015).
45. Calderoni, Palmieri y Maio (2018).
46. Zhiwang, Jungang y Jian (2010).
47. Koucheryavy et al. (2009).
48. Kubiatowicz y otros (2000).

Obras citadas

• Agarwal, Sachin; Trachtenberg, Ari (2006). "Aproximación del número de diferencias entre conjuntos remotos". Taller sobre teoría de la información del IEEE de 2006 (PDF) . Punta del Este, Uruguay. p. 217. CiteSeerX  10.1.1.69.1033 . doi :10.1109/ITW.2006.1633815. ISBN. 978-1-4244-0035-5.S2CID2048278  .​{{cite book}}: CS1 maint: location missing publisher (link)
• Ahmadi, Mahmood; Wong, Stephan (2007), "Una arquitectura de caché para contar filtros Bloom", 15.ª Conferencia internacional sobre redes (ICON-2007) , pág. 218, CiteSeerX  10.1.1.125.2470 , doi :10.1109/ICON.2007.4444089, ISBN 978-1-4244-1229-7, Número de identificación del sujeto  2967865
• Almeida, Paulo; Baquero, Carlos; Preguica, Nuño; Hutchison, David (2007), "Filtros de floración escalables" (PDF) , Cartas sobre procesamiento de información , 101 (6): 255–261, doi :10.1016/j.ipl.2006.10.007, hdl : 1822/6627
• Apache Software Foundation (2012), "11.6. Diseño de esquemas", Guía de referencia de Apache HBase, revisión 0.94.27
• Bloom, Burton H. (1970), "Compensaciones espacio/tiempo en la codificación hash con errores permitidos", Communications of the ACM , 13 (7): 422–426, CiteSeerX  10.1.1.641.9096 , doi :10.1145/362686.362692, S2CID  7931252
• Blustein, James; El-Maazawi, Amal (2002), "Caso óptimo para filtros Bloom generales", Filtros Bloom: un tutorial, análisis y encuesta, Facultad de Ciencias de la Computación de la Universidad de Dalhousie, págs. 1–31
• Boldi, Paolo; Vigna, Sebastiano (2005), "Cadenas mutables en Java: diseño, implementación y algoritmos de búsqueda de texto ligeros", Science of Computer Programming , 54 (1): 3–23, doi :10.1016/j.scico.2004.05.003
• Bonomi, Flavio; Mitzenmacher, Michael ; Panigrahy, Rina; Singh, Sushil; Varghese, George (2006), "Una construcción mejorada para contar filtros Bloom", Algorithms – ESA 2006, 14.º Simposio Europeo Anual (PDF) , Lecture Notes in Computer Science , vol. 4168, págs. 684–695, doi :10.1007/11841036_61, ISBN 978-3-540-38875-3
• Broder, Andrei ; Mitzenmacher, Michael (2005), "Aplicaciones de red de filtros Bloom: una encuesta" (PDF) , Internet Mathematics , 1 (4): 485–509, doi : 10.1080/15427951.2004.10129096 , S2CID  1560675
• Byers, John W.; Considine, Jeffrey; Mitzenmacher, Michael ; Rost, Stanislav (2004), "Entrega de contenido informado a través de redes superpuestas adaptativas", IEEE/ACM Transactions on Networking , 12 (5): 767, CiteSeerX  10.1.1.207.1563 , doi :10.1109/TNET.2004.836103, S2CID  47088273
• Calderoni, Luca; Palmieri, Paolo; Maio, Dario (2015), "Privacidad de la ubicación sin confianza mutua: el filtro Bloom espacial" (PDF) , Computer Communications , 68 : 4–16, doi :10.1016/j.comcom.2015.06.011, hdl :10468/4762, ISSN  0140-3664
• Calderoni, Luca; Palmieri, Paolo; Maio, Dario (2018), "Propiedades probabilísticas de los filtros de Bloom espacial y su relevancia para los protocolos criptográficos", IEEE Transactions on Information Forensics and Security , 13 (7): 1710–1721, doi :10.1109/TIFS.2018.2799486, hdl : 10468/5767 , ISSN  1556-6013, S2CID  3693354
• Chang, Fay; Dean, Jeffrey; Ghemawat, Sanjay; Hsieh, Wilson; Wallach, Deborah; Burrows, Mike; Chandra, Tushar; Fikes, Andrew; Gruber, Robert (2006), "Bigtable: un sistema de almacenamiento distribuido para datos estructurados", Séptimo simposio sobre diseño e implementación de sistemas operativos
• Charles, Denis Xavier; Chellapilla, Kumar (2008), "Filtros Bloomer: una segunda mirada", en Halperin, Dan; Mehlhorn, Kurt (eds.), Algorithms: ESA 2008, 16.º Simposio europeo anual, Karlsruhe, Alemania, 15-17 de septiembre de 2008, Actas , Lecture Notes in Computer Science, vol. 5193, Springer, págs. 259-270, arXiv : 0807.0928 , doi :10.1007/978-3-540-87744-8_22, ISBN 978-3-540-87743-1, S2CID643445 ​
• Chazelle, Bernard ; Kilian, Joe; Rubinfeld, Ronitt ; Tal, Ayellet (2004), "El filtro Bloomier: una estructura de datos eficiente para tablas de búsqueda de soporte estático", Actas del decimoquinto simposio anual ACM-SIAM sobre algoritmos discretos (PDF) , págs. 30–39
• Cohen, Saar; Matias, Yossi (2003), "Filtros de floración espectral", Actas de la Conferencia internacional ACM SIGMOD de 2003 sobre gestión de datos (PDF) , págs. 241–252, doi :10.1145/872757.872787, ISBN 978-1581136340, S2CID  1058187, archivado desde el original (PDF) el 2021-03-10 , consultado el 2019-10-24
• Deng, Fan; Rafiei, Davood (2006), "Detección aproximada de duplicados para transmisión de datos mediante filtros Bloom estables", Actas de la conferencia ACM SIGMOD (PDF) , págs. 25–36
• Dharmapurikar, Sarang; Song, Haoyu; Turner, Jonathan; Lockwood, John (2006), "Clasificación rápida de paquetes mediante filtros Bloom", Actas del Simposio ACM/IEEE de 2006 sobre arquitectura para sistemas de redes y comunicaciones (PDF) , págs. 61–70, CiteSeerX  10.1.1.78.9584 , doi :10.1145/1185347.1185356, ISBN 978-1595935809, S2CID  7848110, archivado desde el original (PDF) el 2 de febrero de 2007
• Dietzfelbinger, Martin; Pagh, Rasmus (2008), "Estructuras de datos sucintas para recuperación y membresía aproximada", en Aceto, Luca; Damgård, Ivan; Goldberg, Leslie Ann; Halldórsson, Magnús M.; Ingólfsdóttir, Anna; Walukiewicz, Igor (eds.), Autómatas, lenguajes y programación: 35.º coloquio internacional, ICALP 2008, Reykjavik, Islandia, 7 al 11 de julio de 2008, Actas, Parte I, Tema A: Algoritmos, autómatas, complejidad y juegos , Lecture Notes in Computer Science, vol. 5125, Springer, págs. 385–396, arXiv : 0803.3693 , doi : 10.1007/978-3-540-70575-8_32, ISBN 978-3-540-70574-1, S2CID1699996 ​
• Dillinger, Peter C.; Manolios, Panagiotis (2004a), "Verificación rápida y precisa de estados de bits para SPIN", Actas del 11.º Taller internacional de Spin sobre software de verificación de modelos, Springer-Verlag, Notas de clase en informática 2989
• Dillinger, Peter C.; Manolios, Panagiotis (2004b), "Filtros Bloom en la verificación probabilística", Actas de la 5.ª Conferencia internacional sobre métodos formales en diseño asistido por ordenador, Springer-Verlag, Apuntes de clase en informática 3312
• Donnet, Benoit; Baynat, Bruno; Friedman, Timur (2006), "Filtros Bloom retocados: permitir que las aplicaciones en red equilibren de forma flexible los falsos positivos y los falsos negativos", CoNEXT 06 – 2.ª conferencia sobre tecnologías de redes futuras, archivado desde el original el 17 de mayo de 2009
• Eppstein, David ; Goodrich, Michael T. (2007), "Identificación de rezagados con eficiencia espacial en flujos de datos de ida y vuelta mediante identidades de Newton y filtros Bloom invertibles", Algorithms and Data Structures, 10th International Workshop, WADS 2007 , Lecture Notes in Computer Science, vol. 4619, Springer-Verlag, págs. 637–648, arXiv : 0704.3313 , Bibcode :2007arXiv0704.3313E
• Fan, Bin; Andersen, Dave G.; Kaminsky, Michael; Mitzenmacher, Michael D. (2014), "Filtro Cuckoo: prácticamente mejor que Bloom", Actas de la 10.ª Conferencia Internacional de la ACM sobre Experimentos y Tecnologías de Redes Emergentes , págs. 75–88, doi : 10.1145/2674005.2674994 , ISBN 9781450332798Implementación de código abierto disponible en github.
• Fan, Li; Cao, Pei; Almeida, Jussara ; Broder, Andrei (2000), "Summary Cache: A Scalable Wide-Area Web Cache Sharing Protocol" (PDF) , IEEE/ACM Transactions on Networking , 8 (3): 281–293, CiteSeerX  10.1.1.41.1487 , doi :10.1109/90.851975, S2CID  4779754, archivado desde el original (PDF) el 22 de septiembre de 2017 , consultado el 30 de julio de 2018Una versión preliminar apareció en SIGCOMM '98.
• Goel, Ashish; Gupta, Pankaj (2010), "Consultas de subconjuntos pequeños y filtros Bloom utilizando memorias asociativas ternarias, con aplicaciones" (PDF) , ACM SIGMETRICS Performance Evaluation Review , 38 : 143, CiteSeerX  10.1.1.296.6513 , doi :10.1145/1811099.1811056
• Graf, Thomas Mueller; Lemire, Daniel (2020), "Filtros Xor", ACM Journal of Experimental Algorithmics , 25 : 1–16, arXiv : 1912.08258 , Bibcode :2019arXiv191208258M, doi :10.1145/3376122, S2CID  209405019
• Grandi, Fabio (2018), "Sobre el análisis de los filtros Bloom" (PDF) , Information Processing Letters , 129 : 35–39, doi :10.1016/j.ipl.2017.09.004
• Kirsch, Adam; Mitzenmacher, Michael (2006), "Menos hash, mismo rendimiento: creación de un mejor filtro Bloom", en Azar, Yossi; Erlebach, Thomas (eds.), Algorithms – ESA 2006, 14th Annual European Symposium (PDF) , Apuntes de la asignatura de informática, vol. 4168, Springer-Verlag, Apuntes de la asignatura de informática 4168, págs. 456–467, doi :10.1007/11841036, ISBN 978-3-540-38875-3, archivado desde el original (PDF) el 31 de enero de 2009
• Koucheryavy, Y.; Giambene, G.; Staehle, D.; Barcelo-Arroyo, F.; Braun, T.; Siris, V. (2009), "Gestión del tráfico y la calidad de servicio en redes multimedia inalámbricas", Informe final de COST 290 : 111
• Kubiatowicz, J.; Bindel, D.; Czerwinski, Y.; Geels, S.; Eaton, D.; Gummadi, R.; Rhea, S.; Weatherspoon, H.; et al. (2000), "Oceanstore: una arquitectura para el almacenamiento persistente a escala global" (PDF) , ACM SIGPLAN Notices : 190–201, archivado desde el original (PDF) el 2012-03-11 , consultado el 2011-12-01
• Maggs, Bruce M. ; Sitaraman, Ramesh K. (julio de 2015), "Algorithmic nuggets in content delivery" (PDF) , ACM SIGCOMM Computer Communication Review , 45 (3): 52–66, CiteSeerX  10.1.1.696.9236 , doi :10.1145/2805789.2805800, S2CID  65760, archivado desde el original (PDF) el 2021-08-14
• Mitzenmacher, Michael ; Upfal, Eli (2005), Probabilidad y computación: algoritmos aleatorios y análisis probabilístico, Cambridge University Press, págs. 107–112, ISBN 9780521835404
• Mortensen, Christian Worm; Pagh, Rasmus ; Pătrașcu, Mihai (2005), "Sobre el informe de rango dinámico en una dimensión", Actas del Trigésimo Séptimo Simposio Anual de la ACM sobre Teoría de la Computación , págs. 104-111, arXiv : cs/0502032 , doi :10.1145/1060590.1060606, ISBN 978-1581139600, S2CID  56473
• Mullin, James K. (1990), "Semiuniones óptimas para sistemas de bases de datos distribuidas", IEEE Transactions on Software Engineering , 16 (5): 558–560, doi :10.1109/32.52778
• Pagh, Anna; Pagh, Rasmus ; Rao, S. Srinivasa (2005), "Un reemplazo óptimo del filtro Bloom", Actas del decimosexto simposio anual ACM-SIAM sobre algoritmos discretos (PDF) , págs. 823–829
• Palmieri, Paolo; Calderoni, Luca; Maio, Dario (2014), "Filtros de floración espacial: habilitación de privacidad en aplicaciones con reconocimiento de ubicación", Proc. 10th International Conference on Information Security and Cryptology (Inscrypt 2014) , vol. 8957, Springer-Verlag, Lecture Notes in Computer Science, págs. 16–36, CiteSeerX  10.1.1.471.4759 , doi :10.1007/978-3-319-16745-9_2, ISBN 978-3-319-16744-2
• Porat, Ely (2009), "Un reemplazo óptimo del filtro Bloom basado en la resolución de matrices", en Frid, Anna E.; Morozov, Andrey; Rybalchenko, Andrey; Wagner, Klaus W. (eds.), Computer Science, Theory and Applications: Fourth International Computer Science Symposium in Russia, CSR 2009, Novosibirsk, Rusia, 18-23 de agosto de 2009, Actas , Lecture Notes in Computer Science, vol. 5675, Springer, págs. 263-273, arXiv : 0804.1845 , doi :10.1007/978-3-642-03351-3_25, ISBN 978-3-642-03350-6, S2CID3205108 ​
• Pournaras, E.; Warnier, M.; Brazier, FMT (2013), "Un servicio de agregación genérico y adaptativo para redes descentralizadas a gran escala", Complex Adaptive Systems Modeling , 1 (19): 19, doi : 10.1186/2194-3206-1-19Implementación del prototipo disponible en github.
• Putze, F.; Sanders, P.; Singler, J. (2007), "Filtros Bloom eficientes en caché, hash y espacio", en Demetrescu, Camil (ed.), Experimental Algorithms, 6.º taller internacional, WEA 2007 (PDF) , Lecture Notes in Computer Science, vol. 4525, Springer-Verlag, Lecture Notes in Computer Science 4525, págs. 108–121, doi :10.1007/978-3-540-72845-0, ISBN 978-3-540-72844-3, archivado desde el original (PDF) el 23 de junio de 2007 , consultado el 18 de julio de 2007
• Rottenstreich, Ori; Kanizo, Yossi; Keslassy, ​​Isaac (2012), "El filtro Bloom de conteo de incremento variable", 31.ª Conferencia internacional anual IEEE sobre comunicaciones informáticas, 2012, Infocom 2012 ( PDF) , págs. 1880–1888, CiteSeerX  10.1.1.174.7165 , doi :10.1109/INFCOM.2012.6195563, ISBN 978-1-4673-0773-4
• Sethumadhavan, Simha; Desikan, Rajagopalan; Burger, Doug; Moore, Charles R.; Keckler, Stephen W. (2003), "Desambiguación de memoria de hardware escalable para procesadores con alto ILP", 36.º Simposio internacional anual IEEE/ACM sobre microarquitectura, 2003, MICRO-36 (PDF) , págs. 399–410, CiteSeerX  10.1.1.229.1254 , doi :10.1109/MICRO.2003.1253244, ISBN 978-0-7695-2043-8, S2CID  195881068, archivado desde el original (PDF) el 14 de enero de 2007
• Starobinski, David; Trachtenberg, Ari; Agarwal, Sachin (2003), "Sincronización eficiente de PDA" (PDF) , IEEE Transactions on Mobile Computing , 2 (1): 40, CiteSeerX  10.1.1.71.7833 , doi :10.1109/TMC.2003.1195150
• Stern, Ulrich; Dill, David L. (1996), "Un nuevo esquema para la verificación probabilística con uso eficiente de la memoria", Actas de la conferencia internacional conjunta IFIP TC6/WG6.1 sobre técnicas de descripción formal para sistemas distribuidos y protocolos de comunicación, y Especificación, prueba y verificación de protocolos, Chapman & Hall, Actas de la conferencia IFIP, págs. 333–348, CiteSeerX  10.1.1.47.4101
• Wessels, Duane (enero de 2004), "10.7 Cache Digests", Squid: The Definitive Guide (1.ª ed.), O'Reilly Media, pág. 172, ISBN 978-0-596-00162-9Los resúmenes de caché se basan en una técnica publicada por primera vez por Pei Cao, llamada caché de resumen. La idea fundamental es utilizar un filtro Bloom para representar el contenido de la caché.
• Tarkoma, Sasu; Rothenberg, Christian Esteve; Lagerspetz, Eemil (2012), "Teoría y práctica de filtros bloom para sistemas distribuidos", IEEE Communications Surveys & Tutorials, n.º 1. (PDF) , vol. 14, págs. 131–155
• Zhiwang, Cen; Jungang, Xu; Jian, Sun (2010), "Un filtro Bloom multicapa para la detección de URL duplicadas", Proc. 3rd International Conference on Advanced Computer Theory and Engineering (ICACTE 2010) , vol. 1, págs. V1–586–V1–591, doi :10.1109/ICACTE.2010.5578947, ISBN 978-1-4244-6539-2, Número de identificación del sujeto  3108985

Enlaces externos

• "Uso de filtros Bloom" Explicación detallada de los filtros Bloom mediante Perl
• Por qué los filtros Bloom funcionan como lo hacen (Michael Nielsen, 2012)
• Filtros Bloom: tutorial, análisis y encuesta (Blustein y El-Maazawi, 2002) en la Universidad de Dalhousie
• Tabla de tasas de falsos positivos para diferentes configuraciones de un sitio web de la Universidad de Wisconsin-Madison
• "Filtros Bloom más óptimos", Ely Porat (noviembre de 2007) Vídeo de Google TechTalk en YouTube