Un filtro Bloom es una estructura de datos probabilística eficiente en el espacio , concebida por Burton Howard Bloom en 1970, que se utiliza para probar si un elemento es miembro de un conjunto . Las coincidencias de falsos positivos son posibles, pero los falsos negativos no. En otras palabras, una consulta devuelve "posiblemente en el conjunto" o "definitivamente no en el conjunto". Se pueden agregar elementos al conjunto, pero no eliminarlos (aunque esto se puede solucionar con la variante de filtro de conteo Bloom ); cuantos más elementos se agreguen, mayor será la probabilidad de falsos positivos.
Bloom propuso la técnica para aplicaciones en las que la cantidad de datos de origen requeriría una cantidad de memoria impracticablemente grande si se aplicaran técnicas de hash "convencionales" sin errores . Dio el ejemplo de un algoritmo de separación de sílabas para un diccionario de 500.000 palabras, de las cuales el 90% sigue reglas simples de separación de sílabas, pero el 10% restante requiere costosos accesos al disco para recuperar patrones específicos de separación de sílabas. 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 usa un área hash más pequeña pero aún elimina la mayoría de los accesos innecesarios. Por ejemplo, un área hash de solo el 15% del tamaño que necesita un hash ideal sin errores aún elimina el 85% 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 número de elementos del conjunto. [2]
Descripción del algoritmo
Un filtro Bloom vacío es una matriz de bits de m bits, todos establecidos en 0. También debe haber k funciones hash diferentes definidas, cada una de las cuales mapea o aplica hash a algún elemento establecido en una de las m posiciones de la matriz, generando una distribución aleatoria uniforme. Por lo general, k es una pequeña constante que depende de la tasa de errores falsos deseada ε , mientras que m es proporcional ak y al número de elementos que se agregarán.
Para agregar un elemento, aliméntelo a cada una de las k funciones hash para obtener k posiciones de matriz. Establezca los bits en todas estas posiciones en 1.
Para consultar un elemento (probar si está en el conjunto), aliméntelo a cada una de las k funciones hash para obtener k posiciones de matriz. Si alguno de los bits en estas posiciones es 0, el elemento definitivamente no está en el conjunto; si lo fuera, entonces todos los bits se habrían puesto a 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 diferentes funciones hash independientes puede ser prohibitivo para k grandes . Para una buena función hash con una salida amplia, debe 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" dividiendo su salida en varios bits. campos. Alternativamente, se pueden pasar k valores iniciales diferentes (como 0, 1, ..., k - 1) a una función hash que toma un valor inicial; o agregue (o anexe) estos valores a la clave. Para m y / o k más grandes , 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 usando hash doble mejorado o hash triple , variantes de hash doble que son efectivamente simples generadores de números aleatorios sembrados con los dos o tres valores hash).
Eliminar un elemento de este filtro Bloom simple es imposible porque no hay forma de saber a cuál de los k bits 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 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 ser indeseable. En este enfoque, no es posible volver a agregar un elemento previamente eliminado, ya que habría que eliminarlo del filtro "eliminado".
A menudo ocurre que todas las claves están disponibles pero son costosas de enumerar (por ejemplo, requieren muchas lecturas de disco). Cuando la tasa de falsos positivos es demasiado alta, el filtro se puede regenerar; este debería ser un evento relativamente raro.
Ventajas de espacio y tiempo
Si bien se arriesgan a falsos positivos, los filtros Bloom tienen una ventaja de espacio sustancial sobre otras estructuras de datos para representar conjuntos, como árboles de búsqueda binaria autoequilibrados , intentos , tablas hash o matrices simples o listas vinculadas de las entradas. La mayoría de estos requieren almacenar al menos los elementos de datos en sí mismos, que pueden requerir desde una pequeña cantidad de bits, para enteros pequeños, hasta un número arbitrario de bits, como cadenas (los intentos son una excepción ya que pueden compartir el 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 , por el contrario, 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 de Bloom es fácilmente superado 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 depósito 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 del número 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 tablas hash dispersas puede hacerlas más rápidas en la práctica que algunos filtros Bloom. Sin embargo, en una implementación de hardware, el filtro Bloom brilla porque sus búsquedas k son independientes y pueden paralelizarse.
Para comprender 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 lo 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 tasa baja de falsos positivos; si los parámetros ( k y m ) se eligen bien, alrededor de la mitad de los bits se establecerá, [5] y estos serán aparentemente aleatoria, lo que minimiza la redundancia y la maximización de contenido de información.
Probabilidad de falsos positivos
Suponga que una función hash selecciona cada posición de la matriz con la misma probabilidad. Si m es el número de bits en la matriz, la probabilidad de que un determinado bit no se establezca en 1 por una determinada función hash durante la inserción de un elemento es
Si k es el número de funciones hash y cada una no tiene una correlación significativa entre sí, entonces la probabilidad de que el bit no esté establecido en 1 por ninguna de las funciones hash es
Podemos usar la identidad conocida para e −1
para concluir que, para m grande ,
Si hemos insertado n elementos, la probabilidad de que un cierto bit siga siendo 0 es
la probabilidad de que sea 1 es por tanto
Ahora pruebe la pertenencia a 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 anterior. La probabilidad de que todos ellos sean 1, lo que haría que el algoritmo afirmara erróneamente que el elemento está en el conjunto, a menudo se da como
Esto no es estrictamente correcto ya que asume independencia para las probabilidades de que se establezca cada bit. Sin embargo, asumiendo que es una aproximación cercana, tenemos que la probabilidad de falsos positivos disminuye a medida que aumenta m (el número de bits en la matriz) y aumenta a medida que aumenta n (el número de elementos insertados).
La verdadera probabilidad de un falso positivo, sin asumir independencia, es
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 agregado todos los n elementos al filtro Bloom, sea q la fracción de los m bits que se establecen en 0 (es decir, el número de bits que aún se establecen en 0 es qm ). pertenencia a 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 establecido en 1 es. Entonces, la probabilidad de que todas las k funciones hash encuentren su bit establecido en 1 es. Además, el valor esperado de q es la probabilidad de que cada una de las k funciones hash de cada uno de los n elementos no modifique una posición determinada de la matriz , que es (como arriba)
- .
Es posible probar, sin el supuesto de independencia, que q está muy fuertemente concentrado alrededor de su valor esperado. En particular, a partir de la desigualdad Azuma-Hoeffding , prueban que [8]
Debido a esto, podemos decir que la probabilidad exacta de falsos positivos es
como antes.
Número óptimo de funciones hash
El número de funciones hash, k , debe ser un número entero positivo. Dejando de lado esta restricción, para m y n dados , el valor de k que minimiza la probabilidad de falso positivo es
El número requerido de bits, m , dado n (el número de elementos insertados) y una probabilidad falsa positiva deseada ε (y asumiendo que se usa el valor óptimo de k ) se puede calcular sustituyendo el valor óptimo de k en la expresión de probabilidad anterior :
que se puede simplificar a:
Esto resulta en:
Entonces, el número óptimo de bits por elemento es
con el número correspondiente de funciones hash k (ignorando la integralidad):
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 formula es aproximado por tres razones. Primero, y de menor preocupación, se aproxima como , que es una buena aproximación asintótica (es decir, que se mantiene como m → ∞). En segundo lugar, 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, lo más preocupante es que asume que es fortuitamente integral.
Goel y Gupta, [10] sin embargo, dan un límite superior riguroso que no hace aproximaciones y no requiere suposiciones. Muestran que la probabilidad de falso positivo para un filtro Bloom finito con m bits (), n elementos y k funciones hash es como máximo
Este límite puede interpretarse en el sentido de que la fórmula aproximada se puede aplicar con una penalización de como máximo medio elemento extra y como máximo un bit menos.
Aproximación del número de elementos en un filtro Bloom
Swamidass y Baldi (2007) demostraron que la cantidad de elementos en un filtro Bloom se puede aproximar con la siguiente fórmula:
dónde 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.
La unión e intersección de conjuntos
Los filtros Bloom son una forma de representar de forma 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 Bloom se pueden usar para aproximar el tamaño de la intersección y unión de dos conjuntos. Swamidass y Baldi (2007) demostraron que para dos filtros Bloom de longitud m , sus recuentos, respectivamente, pueden estimarse como
y
El tamaño de su unión se puede estimar como
dónde es el número de bits establecido en uno en cualquiera de los dos filtros Bloom. Finalmente, la intersección se puede estimar como
usando las tres fórmulas juntas.
Propiedades interesantes
- A diferencia de una tabla hash estándar que utiliza direccionamiento abierto para la resolución de colisiones , un filtro Bloom de tamaño fijo puede representar un conjunto con un número 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 constantemente 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 constantemente hasta que se acerca a la búsqueda lineal.
- La unión y la 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 los 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 la codificación Zato , inventada por Calvin Mooers en 1947, en la que el conjunto de categorías asociadas con un dato se representa mediante muescas en una tarjeta, con un patrón aleatorio de cuatro muescas para cada categoría.
Ejemplos de
- 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 nuevo olor con el de los ejemplos previamente experimentados y el tiempo transcurrido desde la experiencia previa del mismo olor. [11]
- Los servidores de Akamai Technologies , un proveedor de distribución de contenido , utilizan filtros Bloom para evitar que las "maravillas de un solo resultado" se almacenen en sus cachés de disco. Las maravillas de un solo resultado son objetos web solicitados por los usuarios una sola vez, algo que Akamai encontró aplicado 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 el almacenamiento en caché de ese objeto solo en su segunda solicitud evita que las maravillas de un solo resultado ingresen al caché del disco, lo que reduce significativamente la carga de trabajo del disco y aumenta las tasas de aciertos del caché del disco. [12]
- Google Bigtable , Apache HBase y Apache Cassandra y PostgreSQL [13] utilizan filtros Bloom para reducir las búsquedas en disco de filas o columnas inexistentes. Evitar costosas búsquedas de disco aumenta considerablemente el rendimiento de una operación de consulta de base de datos. [14]
- El navegador web Google Chrome solía utilizar un filtro Bloom para identificar URL maliciosas. Cualquier URL se verificó primero con un filtro Bloom local, y solo si el filtro Bloom arrojó un resultado positivo se realizó una verificación completa de la URL (y el usuario advirtió, si eso también arrojó un resultado positivo). [15] [16]
- Microsoft Bing (motor de búsqueda) utiliza filtros Bloom jerárquicos de varios niveles para su índice de búsqueda, BitFunnel . Los filtros Bloom proporcionaron un costo más bajo que el índice Bing anterior, que se basaba en archivos invertidos . [17]
- El calamar Web Proxy Cache utiliza filtros Bloom para digiere caché . [18]
- Bitcoin usó filtros Bloom para acelerar la sincronización de la billetera hasta que se descubrieron vulnerabilidades de privacidad con la implementación de filtros Bloom. [19] [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 estado accesible para grandes problemas de verificación. [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 la base de datos). [23]
- El agente de transferencia de correo de Exim (MTA) utiliza filtros Bloom en su función de límite de velocidad. [24]
- Medium usa filtros Bloom para evitar recomendar artículos que un usuario haya leído anteriormente. [25]
- Ethereum usa filtros Bloom para encontrar rápidamente registros en la cadena de bloques Ethereum.
Alternativas
Uso de filtros Bloom clásicos bits de espacio por 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 solopor clave. [26] Por tanto, los filtros Bloom utilizan un 44% más de espacio que una estructura de datos óptima equivalente. En cambio, Pagh et al. proporcionar una estructura de datos de espacio óptimo. Además, su estructura de datos tiene una localidad de referencia constante independiente de la tasa de falsos positivos, a diferencia de los filtros Bloom, donde una tasa de falsos positivos más baja conduce a un mayor número de accesos a la memoria por consulta, . Además, permite eliminar elementos sin penalización de espacio, a diferencia de los filtros Bloom. Las mismas propiedades mejoradas de uso óptimo del espacio, localidad de referencia constante y la capacidad de eliminar elementos también son proporcionadas por el filtro cucú de Fan et al. (2014) , cuya implementación de código abierto está disponible.
Stern y Dill (1996) describen una estructura probabilística basada en tablas hash , compactación hash , que Dillinger y Manolios (2004b) identifican como significativamente más precisa que un filtro Bloom cuando cada uno está configurado de manera óptima. Dillinger y Manolios, sin embargo, señalan que la precisión razonable de cualquier filtro Bloom dado sobre una amplia gama de números de adiciones lo hace atractivo para la enumeración probabilística de espacios estatales de tamaño desconocido. La compactación hash es, por lo tanto, atractiva cuando el número de adiciones se puede predecir con precisión; sin embargo, a pesar de ser muy rápido en software, la compactación hash no es adecuada para hardware debido al tiempo de acceso lineal en el peor de los casos.
Putze, Sanders y Singler (2007) han estudiado algunas variantes de los filtros Bloom que son más rápidos 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 tienen el mismo tamaño que los bloques de memoria caché del procesador (generalmente 64 bytes). Es de suponer que esto mejorará el rendimiento al reducir el número de posibles pérdidas de memoria caché . 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 de uso eficiente del espacio se basa en el uso de una única función hash que genera para cada clave un valor en el rango dónde es la tasa de falsos positivos solicitada. Luego, la secuencia de valores se ordena y comprime utilizando la codificación Golomb (o alguna otra técnica de compresión) para ocupar un espacio cercano abits. 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 por el hecho de que es necesario calcular una única función hash.
Otra alternativa al filtro Bloom clásico es el filtro de cuco , basado en variantes de hash de cuco que ahorran espacio . En este caso, se construye una tabla hash, que no contiene claves ni valores, sino huellas digitales cortas (pequeños hash) de las claves. Si al buscar la clave se encuentra una huella digital coincidente, es probable que la clave esté en el conjunto. Una propiedad útil de los filtros de cuco es que son actualizables; Las entradas pueden agregarse dinámicamente (con una pequeña probabilidad de falla debido a que la tabla hash está llena) y eliminarse.
Graf y Lemire (2019)bits por tecla) y más rápido que los filtros Bloom o cuco. (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.
describe un enfoque llamado filtro xor, donde almacenan huellas digitales en un tipo particular de tabla hash perfecta , produciendo un filtro que es más eficiente en memoria (Extensiones y aplicaciones
Hay más de 60 variantes de filtros Bloom, muchos estudios de campo y una continua rotación de aplicaciones (ver, por ejemplo, Luo, et al [27] ). Algunas de las variantes difieren lo suficiente de la propuesta original como para ser violaciones o bifurcaciones de la estructura de datos original y su filosofía. [27] Queda por hacer un tratamiento que unifica los filtros de Bloom con otros trabajos sobre proyecciones aleatorias , detección de compresión y hashing sensible a la localidad (aunque ver Dasgupta, et al [28] para un intento inspirado en la neurociencia).
Filtrado de caché
Las redes de entrega 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 "maravillas de un solo resultado" a las que los usuarios acceden solo una vez y nunca más. Es evidente que es un desperdicio de recursos de disco almacenar maravillas de un solo resultado en una caché web, ya que nunca se volverá a acceder a ellas. Para evitar el almacenamiento en caché de las maravillas de un solo resultado, 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 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 las maravillas de un solo golpe nunca se escriben en la memoria caché del disco. Además, filtrar las maravillas de un solo resultado también ahorra espacio de caché en el disco, lo que aumenta las tasas de aciertos de caché. [12]
Evitar falsos positivos en un universo finito
Kiss et al [29] describieron una nueva construcción para el filtro Bloom que evita 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 pruebas grupales combinatorias no adaptativas existente de Eppstein, Goodrich e 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.
Contando filtros Bloom
Los filtros de recuento proporcionan una forma de implementar una operación de eliminación en un filtro Bloom sin volver a crear el filtro. En un filtro de conteo, las posiciones de la matriz (cubos) se extienden de ser un solo bit a ser un contador multibit. De hecho, los filtros Bloom normales pueden considerarse filtros de recuento con un tamaño de cubo de un bit. Los filtros de recuento 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 comprueba que cada uno de los depósitos necesarios sea distinto de cero. Luego, la operación de eliminación consiste en disminuir el valor de cada uno de los cubos respectivos.
El desbordamiento aritmético de los cubos es un problema y los cubos deben ser lo suficientemente grandes para que este caso sea raro. Si ocurre, las operaciones de incremento y decremento deben dejar el depósito establecido 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 recuento 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 & 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 recuento es la escalabilidad limitada. Debido a que la tabla de filtros de recuento Bloom no se puede expandir, se debe conocer de antemano el número máximo de claves que se almacenarán simultáneamente en el filtro. Una vez que se excede la capacidad diseñada de la mesa, la tasa de falsos positivos aumentará rápidamente a medida que se inserten más claves.
Bonomi y col. (2006) introdujeron una estructura de datos basada en hash d-left que es funcionalmente equivalente pero utiliza aproximadamente la mitad de espacio que contar los filtros Bloom. El problema de escalabilidad no ocurre en esta estructura de datos. Una vez superada la capacidad diseñada, las claves podrían reinsertarse en una nueva tabla hash de doble tamaño.
La variante de espacio eficiente de Putze, Sanders & Singler (2007) también podría usarse para implementar filtros de conteo al admitir inserciones y eliminaciones.
Rottenstreich, Kanizo & Keslassy (2012) introdujeron un nuevo método general basado en incrementos de variables que mejora significativamente la probabilidad de falsos positivos de contar los filtros Bloom y sus variantes, sin dejar de admitir deleciones. A diferencia de los filtros de recuento 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 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 y col. (2019) muestra que el falso positivo del filtro Counting Bloom disminuye de k = 1 a un punto definido, y aumenta desde al infinito positivo, y encuentra en función del umbral de recuento. [30]
Agregación descentralizada
Los filtros Bloom se pueden organizar en estructuras de datos distribuidos para realizar cálculos completamente 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 una entidad computacional centralizada para este propósito. [31]
Filtros Bloom distribuidos
Los filtros Bloom paralelos se pueden implementar para aprovechar los múltiples elementos de procesamiento (PE) presentes en las máquinas no compartidas en paralelo . Uno de los principales obstáculos para un filtro Bloom paralelo es la organización y comunicación de los datos desordenados que, en general, se distribuyen uniformemente entre todos los PE al inicio o en las inserciones de lotes. Para ordenar los datos se pueden usar dos enfoques, ya sea que resulten en un filtro Bloom sobre todos los datos que se almacenan en cada PE, llamado filtro de floración replicante, o el filtro Bloom sobre todos los datos se dividen en partes iguales, cada PE almacena una parte de ellos. . [32] Para ambos enfoques se utiliza un filtro Bloom "Single Shot" 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 con un hash de todos los elementos en su PE local y luego clasificándolos por sus hash localmente. Esto se puede hacer en tiempo lineal usando, por ejemplo, la clasificación de cubos y también permite la detección local de duplicados. La clasificación se utiliza para agrupar los hash 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 valores hash entre los valores y , donde s es el tamaño total del filtro Bloom sobre todos los datos. Debido a que cada elemento solo tiene un hash una vez y, por lo tanto, solo se establece un bit, para verificar si un elemento se insertó en el filtro Bloom, solo se debe operar el PE responsable del valor hash del elemento. Las operaciones de inserción única también se pueden realizar de manera eficiente porque el filtro Bloom de solo un PE debe cambiarse, en comparación con los filtros Bloom Replicating donde cada PE tendría que actualizar su filtro Bloom. Al distribuir el filtro Bloom global sobre 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 tasa de falsos positivos más baja.
Los filtros Bloom distribuidos se pueden utilizar para mejorar los algoritmos de detección de duplicados [33] al filtrar los elementos más "únicos". Estos se pueden calcular comunicando solo los valores hash de los elementos, no los elementos en sí, que son mucho más grandes en volumen, y eliminándolos del conjunto, lo que reduce la carga de trabajo del algoritmo de detección de duplicados que se utiliza posteriormente.
Durante la comunicación de los hash, los PE buscan bits que están configurados en más de uno de los paquetes receptores, ya que esto significaría que dos elementos tuvieran el mismo hash y, por lo tanto, podrían estar 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 establecido. Si un remitente envía varios índices al mismo PE, puede resultar ventajoso codificar también los índices. Ahora se garantiza que todos los elementos a los que no se les devolvió el hash no serán un duplicado y no se evaluarán más, para los elementos restantes se puede usar un algoritmo de Repartición [34] . Primero, todos los elementos a los que se les devolvió el valor hash se envían al PE del que es responsable su hash. Ahora se garantiza que cualquier elemento y su duplicado estará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 hash duplicados y, en su lugar, cualquier elemento con un hash duplicado puede simplemente marcarse 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 de floración usado.
El proceso de filtrado de los elementos más "únicos" también se puede repetir varias veces cambiando la función hash en cada paso de filtrado. Si solo se usa un solo paso de filtrado, tiene que archivar 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 último tiene una tasa más alta pero también funciona con menos elementos. ya que muchos ya han sido eliminados por 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 el número de duplicados en un conjunto es pequeño, la recompensa por las complicaciones adicionales es baja.
Los filtros de replicación de Bloom organizan sus datos mediante el uso de un algoritmo de hipercubo conocido para cotillear, por ejemplo, [35] Primero, cada PE calcula el filtro de Bloom sobre todos los elementos locales y lo almacena. Al repetir un bucle en el que en cada paso i los PE envían su filtro Bloom local sobre la dimensión iy 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 todos dimensiones cada PE contiene el filtro Bloom global sobre todos los elementos.
Los filtros de replicación de Bloom son más eficientes cuando la cantidad de consultas es mucho mayor que la cantidad de elementos que contiene el filtro de Bloom, el punto de equilibrio en comparación con los filtros de Bloom distribuida es aproximadamente posterior accesos, con como la tasa de falsos positivos del filtro de floración.
Sincronización de datos
Los filtros Bloom se pueden utilizar para la sincronización de datos aproximada como en Byers et al. (2004) . Los filtros de recuento de Bloom se pueden utilizar para aproximar el número de diferencias entre dos conjuntos y este enfoque se describe en Agarwal y Trachtenberg (2006) .
Filtros más florecientes
Chazelle y col. (2004) diseñaron una generalización de filtros Bloom que podría asociar un valor a cada elemento que se hubiera insertado, implementando un arreglo asociativo . Al igual que los filtros Bloom, estas estructuras logran una sobrecarga de espacio pequeña 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á 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 basada en celosía de los filtros Bloom. Un aproximador compacto asocia a cada tecla un elemento de una celosía (los filtros Bloom estándar son el caso de la celosía booleana de dos elementos). En lugar de una matriz de bits, tienen una matriz de elementos de celosía. Al agregar una nueva asociación entre una clave y un elemento de la celosía, calculan el máximo del contenido actual de las k ubicaciones de matriz asociadas a la clave con el elemento de celosía. 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 por encima del valor original.
Filtros Bloom particionados en paralelo
Esta implementación utilizó una matriz separada para cada función hash. Este método permite cálculos hash en paralelo tanto para inserciones como para consultas. [36]
Filtros de floración estable
Deng y Rafiei (2006) propusieron los filtros Stable Bloom como una variante de los filtros Bloom para la transmisión de datos. La idea es que, dado que no hay forma de almacenar el historial completo de una secuencia (que puede ser infinita), Stable Bloom filtra continuamente la información obsoleta para dejar espacio para elementos más recientes. Dado que se desaloja la información obsoleta, el filtro Stable Bloom introduce falsos negativos, que no aparecen en los filtros Bloom tradicionales. Los autores muestran que se garantiza un límite superior estricto de tasas de falsos positivos, y el método es superior a los filtros Bloom estándar en términos de tasas de falsos positivos y eficiencia de tiempo cuando se da un espacio pequeño y una tasa de falsos positivos aceptable.
Filtros Bloom escalables
Almeida et al. (2007) propusieron una variante de filtros Bloom que puede adaptarse dinámicamente al número de elementos almacenados, asegurando 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, para garantizar 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 & 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 varios conjuntos en una única estructura de datos, lo que los hace adecuados para varios escenarios de aplicación diferentes. [37] 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 probabilidades de falso positivo más altas que los conjuntos ingresados al final. [38] Esta propiedad permite una priorización de los conjuntos, donde se pueden conservar 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 profundo en el que se encontró el elemento. [39]
Filtros de floración atenuada
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 del nivel i indica qué servicios se pueden encontrar en los nodos que están alejados del nodo actual. El i-ésimo valor se construye tomando una unión de filtros Bloom locales para los nodos i-hops fuera del nodo. [40]
Tomemos como ejemplo una pequeña red que se muestra en el gráfico a continuación. Digamos que estamos buscando un servicio A cuyo identificador se haya convertido en los bits 0,1 y 3 (patrón 11010). Sea n1 nodo el punto de partida. En primer lugar, comprobamos si n1 ofrece el servicio A comprobando su filtro local. Dado que los patrones no coinciden, verificamos el filtro Bloom atenuado para determinar qué nodo debe ser el siguiente salto. Vemos que n2 no ofrece el servicio A, pero se encuentra en el camino hacia los nodos que lo hacen. Por tanto, nos movemos a n2 y repetimos el mismo procedimiento. Rápidamente descubrimos que n3 ofrece el servicio y, por lo tanto, se ubica el destino. [41]
Mediante el uso de filtros Bloom atenuados que constan de varias capas, los servicios a más de un salto de distancia se pueden descubrir mientras se evita la saturación del filtro Bloom al atenuar (desplazar) los bits establecidos por fuentes más alejadas. [40]
Búsqueda de estructuras químicas
Los filtros Bloom se utilizan a menudo para buscar en grandes bases de datos de estructuras químicas (ver similitud química ). En el caso más simple, los elementos agregados al filtro (llamado huella digital en este campo) son solo 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 subestructura más grandes como grupos carboxilo y propiedades de gráficos como el número de anillos. En las huellas dactilares basadas en hash, se usa una función hash basada en propiedades de átomos y enlaces para convertir un subgráfico en una semilla PRNG , y los primeros valores de salida se usan para establecer bits en el filtro Bloom.
Las huellas dactilares moleculares comenzaron a fines 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 para subestructuras que no se habían visto previamente. A principios de la década de 1990, el término "huella dactilar" se consideraba diferente de "claves estructurales", pero desde entonces el término ha crecido hasta abarcar la mayoría de las características moleculares que pueden usarse para una comparación de similitudes, incluidas claves estructurales, huellas dactilares de recuento escaso y huellas dactilares en 3D . A diferencia de los filtros Bloom, el método hash 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 un número fijo de bits por característica, lo que las convierte en un filtro Bloom. Las huellas dactilares originales de Daylight se pueden utilizar tanto con fines de similitud como de detección. Muchos otros tipos de huellas dactilares, como el popular ECFP2, pueden usarse para similitudes pero no para detección porque incluyen características ambientales locales que introducen falsos negativos cuando se usan como pantalla. Incluso si se construyen con el mismo mecanismo, no son filtros Bloom porque no se pueden usar para filtrar.
Ver también
- Bosquejo de conteo mínimo
- Función hash
- MinHash
- Filtro de cociente
- Lista de omisión
- Filtros Bloom en bioinformática
- Filtro de cuco
Notas
- ^ Bloom (1970) .
- ^ Bonomi y col. (2006) .
- ^ Dillinger y Manolios (2004a) ; Kirsch y Mitzenmacher (2006) .
- ^ Mitzenmacher y Upfal (2005) .
- ^ Blustein y El-Maazawi (2002) , págs. 21-22
- ^ Gopinathan, Kiran; Sergey, Ilya (21 de julio de 2020). "Certificación de certeza e incertidumbre en estructuras de consulta de membresía aproximadas" . Verificación asistida por computadora . Apuntes de conferencias en Ciencias de la Computación. Springer, Cham. 12225 : 279-303. doi : 10.1007 / 978-3-030-53291-8_16 . ISBN 978-3-030-53290-1. PMC 7363400 .
- ^ Mitzenmacher y Upfal (2005) , págs. 109-111, 308.
- ^ Mitzenmacher y Upfal (2005) , p. 308.
- ^ Starobinski, Trachtenberg y Agarwal (2003)
- ^ Goel y Gupta (2010)
- ^ 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. doi : 10.1073 / pnas.1814448115 . ISSN 0027-8424 . PMC 6304992 . PMID 30509984 .
- ↑ a b c Maggs y Sitaraman (2015) .
- ^ "Módulo de contribución de índice de Bloom" . Postgresql.org. 2016-04-01. Archivado desde el original el 9 de septiembre de 2018 . Consultado el 18 de junio de 2016 .
- ^ Chang y col. (2006) ; Fundación de software Apache (2012) .
- ^ Yakunin, Alex (25 de marzo de 2010). "Blog de Alex Yakunin: aplicación de filtro Nice Bloom" . Blog.alexyakunin.com. Archivado desde el original el 27 de octubre de 2010 . Consultado el 31 de mayo de 2014 .
- ^ "Problema 10896048: Transición de la navegación segura del filtro Bloom al conjunto de prefijos. Revisión de código" . Chromiumcodereview.appspot.com . Consultado el 3 de julio de 2014 .
- ^ Goodwin, Bob; Hopcroft, Michael; Luu, Dan; Clemmer, Alex; Curmei, Mihaela; Elnikety, Sameh; Yuxiong, él (2017). "BitFunnel: Revisando las firmas para la búsqueda" (PDF) . SIGIR : 605–614. doi : 10.1145 / 3077136.3080789 . S2CID 20123252 .
- ^ Wessels (2004) .
- ^ "BIP 0037" . 2012-10-24 . Consultado el 29 de mayo de 2018 .
- ^ "Filtro Bloom | Glosario de río" . River Financial . Consultado el 14 de noviembre de 2020 .
- ^ "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 .
- ^ "Spin - Verificación formal" .
- ^ Mullin (1990) .
- ^ "Código fuente de Exim" . github . Consultado el 3 de marzo de 2014 .
- ^ "¿Qué son los filtros Bloom?" . Medio. 2015-07-15 . Consultado el 1 de noviembre de 2015 .
- ^ Pagh, Pagh y Rao (2005) .
- ^ a b 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 ].
- ^ 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. doi : 10.1073 / pnas.1814448115 . PMC 6304992 . PMID 30509984 .
- ^ Kiss, SZ; Hosszu, E .; Tapolcai, J .; Rónyai, L .; Rottenstreich, O. (2018). "Filtro de floración con zona libre de falsos positivos" (PDF) . Actas del IEEE de INFOCOM . Consultado el 4 de diciembre de 2018 .
- ^ Kim, Kibeom; Jeong, Yongjo; Lee, Youngjoo; Lee, Sunggu (11 de julio de 2019). "Análisis de filtros de recuento Bloom utilizados para el umbral de recuento" . Electrónica . 8 (7): 779. doi : 10.3390 / electronics8070779 . ISSN 2079-9292 .
- ^ Pournaras, Warnier y Brazier (2013) .
- ^ Sanders, Peter y Schlag, Sebastian y Müller, Ingo (2013). "Algoritmos eficientes de comunicación para problemas fundamentales de big data". Conferencia Internacional IEEE sobre Big Data 2013 : 15–23. doi : 10.1109 / BigData.2013.6691549 . ISBN 978-1-4799-1293-3. S2CID 15968541 .CS1 maint: varios nombres: lista de autores ( enlace )
- ^ Schlag, Sebastián (2013). "Eliminación distribuida de duplicados". Instituto de Tecnología de Karlsruhe .
- ^ Shatdal, Ambuj y Jeffrey F. Naughton (1994). "Procesamiento de agregados en sistemas de bases de datos en paralelo". Departamento de Ciencias de la Computación de la Universidad de Wisconsin-Madison : 8.CS1 maint: varios nombres: lista de autores ( enlace )
- ^ V. Kumar, A. Grama, A. Gupta y G. Karypis (1994). Introducción a la Computación Paralela. Diseño y Análisis de Algoritmos . Benjamin / Cummings.CS1 maint: varios nombres: lista de autores ( enlace )
- ^ Kirsch, Adam; Mitzenmacher †, Michael. "Menos hash, mismo rendimiento: creación de un mejor filtro de floración" (PDF) . Escuela de Ingeniería y Ciencias Aplicadas de Harvard . Wiley InterScience.
- ^ Calderoni, Palmieri y Maio (2015) .
- ^ Calderoni, Palmieri y Maio (2018) .
- ^ Zhiwang, Jungang y Jian (2010) .
- ^ a b Koucheryavy y col. (2009) .
- ^ Kubiatowicz y col. (2000) .
Referencias
- Agarwal, Sachin; Trachtenberg, Ari (2006), "Aproximación del número de diferencias entre conjuntos remotos" (PDF) , IEEE Information Theory Workshop , Punta del Este, Uruguay: 217, CiteSeerX 10.1.1.69.1033 , doi : 10.1109 / ITW.2006.1633815 , ISBN 978-1-4244-0035-5, S2CID 2048278
- Ahmadi, Mahmood; Wong, Stephan (2007), "Una arquitectura de caché para contar los filtros Bloom", 15ª Conferencia internacional sobre redes (ICON-2007) , p. 218, CiteSeerX 10.1.1.125.2470 , doi : 10.1109 / ICON.2007.4444089 , ISBN 978-1-4244-1229-7, S2CID 2967865
- Almeida, Paulo; Baquero, Carlos; Preguica, Nuno; Hutchison, David (2007), "Scalable Bloom Filters" (PDF) , Information Processing Letters , 101 (6): 255-261, doi : 10.1016 / j.ipl.2006.10.007 , hdl : 1822/6627
- Apache Software Foundation (2012), "11.6. Diseño de esquema" , Guía de referencia de Apache HBase, Revisión 0.94.27
- Bloom, Burton H. (1970), "Compensación de espacio / tiempo en la codificación hash con errores permitidos", Comunicaciones del 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 los filtros Bloom generales", Bloom Filters - A Tutorial, Analysis, and Survey , 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 ligeros de búsqueda de texto", 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), "An Improved Construction for Counting Bloom Filters", Algorithms - ESA 2006, 14th Annual European Symposium (PDF) , Lecture Notes in Computer Science , 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) , Matemáticas de Internet , 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 adaptables", 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 espacial Bloom" (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 Spatial Bloom 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 Bloomier: una segunda mirada", en Halperin, Dan; Mehlhorn, Kurt (eds.), Algoritmos: ESA 2008, 16º Simposio Anual Europeo, Karlsruhe, Alemania, Septiembre 15-17, 2008, Proceedings , Lecture Notes in Computer Science, 5193 , Springer, pp 259-270,. ArXiv : 0807,0928 , doi : 10.1007 / 978-3-540-87744-8_22 , ISBN 978-3-540-87743-1, S2CID 643445
- 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), "Spectral Bloom Filters", Actas de la Conferencia Internacional ACM SIGMOD sobre Gestión de Datos de 2003 (PDF) , págs. 241-252, doi : 10.1145 / 872757.872787 , ISBN 978-1581136340, S2CID 1058187
- Deng, Fan; Rafiei, Davood (2006), "Detección aproximada de duplicados para la transmisión de datos mediante filtros de floración estable", 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 2007-02-02
- 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.), Automata, Languages and Programming: 35th International Colloquium, ICALP 2008, Reykjavik, Iceland, 7-11 de julio de 2008, Actas, Parte I, Track A: Algoritmos, Autómatas, Complejidad y Juegos , Conferencia Notes in Computer Science, 5125 , Springer, págs. 385–396, arXiv : 0803.3693 , doi : 10.1007 / 978-3-540-70575-8_32 , ISBN 978-3-540-70574-1, S2CID 1699996
- Dillinger, Peter C .; Manolios, Panagiotis (2004a), "Verificación rápida y precisa de Bitstate para SPIN", Actas del 11º Taller internacional de Spin sobre software de verificación de modelos , Springer-Verlag, Lecture Notes in Computer Science 2989
- Dillinger, Peter C .; Manolios, Panagiotis (2004b), "Filtros de floración en verificación probabilística", Actas de la Quinta Conferencia Internacional sobre Métodos Formales en Diseño Asistido por Computadora , Springer-Verlag, Lecture Notes in Computer Science 3312
- Donnet, Benoit; Baynat, Bruno; Friedman, Timur (2006), "Filtros Bloom retocados: Permitir que las aplicaciones en red intercambien de manera flexible falsos positivos con falsos negativos", CoNEXT 06 - Segunda 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 uso eficiente del espacio en flujos de datos de ida y vuelta a través de identidades de Newton y filtros Bloom invertibles", Algoritmos y estructuras de datos, Décimo taller internacional, WADS 2007 , Lecture Notes in Computer Science, 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 de cuco: Prácticamente mejor que Bloom", Proc. 10 ° ACM Int. Conf. Experimentos y tecnologías emergentes de redes (CoNEXT '14) , págs. 75–88, doi : 10.1145 / 2674005.2674994 , ISBN 9781450332798. Implementació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 2018. Una versión preliminar apareció en SIGCOMM '98.
- Goel, Ashish; Gupta, Pankaj (2010), "Consultas de subconjuntos pequeños y filtros de floración 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), "Xor Filters", 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 de floración", en Azar, Yossi; Erlebach, Thomas (eds.), Algorithms - ESA 2006, 14th Annual European Symposium (PDF) , Lecture Notes in Computer Science, 4168 , Springer-Verlag, Lecture Notes in Computer Science 4168, pp. 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 .; Barceló-Arroyo, F .; Braun, T .; Siris, V. (2009), "Traffic and QoS Management in Wireless Multimedia Networks", 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: An architecture for global-scale persistent storage" (PDF) , ACM SIGPLAN Notices : 190–201, archivado desde el original (PDF) el 2012-03-11 , consultado 2011-12-01
- Maggs, Bruce M .; Sitaraman, Ramesh K. (julio de 2015), "Nuggets algorítmicos en la entrega de contenido" (PDF) , SIGCOMM Computer Communication Review , 45 (3): 52–66, CiteSeerX 10.1.1.696.9236 , doi : 10.1145 / 2805789.2805800 , S2CID 65760
- 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 informes de rango dinámico en una dimensión", Actas del trigésimo séptimo Simposio Anual de 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), "Optimal semijuntas 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), "Spatial Bloom Filters: Habilitación de la privacidad en aplicaciones que reconocen la ubicación", Proc. Décima Conferencia Internacional sobre Seguridad de la Información y Criptología (Inscrypt 2014) , 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.), Ciencias de la Computación, Teoría y Aplicaciones: Cuarto Simposio Internacional de Ciencias de la Computación en Rusia, CSR 2009, Novosibirsk, Rusia, 18 al 23 de agosto de 2009, Actas , Lecture Notes in Computer Science, 5675 , Springer , págs. 263–273, arXiv : 0804.1845 , doi : 10.1007 / 978-3-642-03351-3_25 , ISBN 978-3-642-03350-6, S2CID 3205108
- Pournaras, E .; Warnier, M .; Brasero, FMT. (2013), "Un servicio de agregación genérico y adaptativo para redes descentralizadas a gran escala", Modelado de sistemas adaptativos complejos , 1:19 : 19, doi : 10.1186 / 2194-3206-1-19. Implementación de prototipos disponible en github .
- Putze, F .; Sanders, P .; Singler, J. (2007), "Cache-, Hash- and Space-Efficient Bloom Filters", en Demetrescu, Camil (ed.), Experimental Algorithms, 6th International Workshop, WEA 2007 (PDF) , Lecture Notes in Computer Science, 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
- Rottenstreich, Ori; Kanizo, Yossi; Keslassy, Isaac (2012), "The Variable-Increment Counting Bloom Filter", 31ª Conferencia internacional anual de 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 de alto ILP", 36º Simposio Internacional Anual de Microarquitectura IEEE / ACM, 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 2007-01-14
- Starobinski, David; Trachtenberg, Ari; Agarwal, Sachin (2003), "Efficient PDA Synchronization" (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), "A New Scheme for Memory-Efficient Probabilistic Verification", Actas de técnicas de descripción formal para sistemas distribuidos y protocolos de comunicación, y especificación, prueba y verificación de protocolos: IFIP TC6 / WG6.1 Joint International Conference , Chapman & Hall, IFIP Conference Proceedings, págs. 333–348, CiteSeerX 10.1.1.47.4101
- Swamidass, S. Joshua; Baldi, Pierre (2007), "Corrección matemática para medidas de similitud de huellas dactilares para mejorar la recuperación química", Journal of Chemical Information and Modeling , 47 (3): 952–964, doi : 10.1021 / ci600526a , PMID 17444629
- Wessels, Duane (enero de 2004), "10.7 Cache Digests", Squid: The Definitive Guide (1ª ed.), O'Reilly Media, p. 172, ISBN 978-0-596-00162-9,
Cache Digests se basan en una técnica publicada por primera vez por Pei Cao, llamada Summary Cache. 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 los filtros de floración para sistemas distribuidos", IEEE Communications Surveys & Tutorials, no. 1. (PDF) , 14 , págs. 131-155
- Zhiwang, Cen; Jungang, Xu; Jian, Sun (2010), "Un filtro Bloom multicapa para la detección de URL duplicadas", Proc. 3er Congreso Internacional de Teoría e Ingeniería Informática Avanzada (ICACTE 2010) , 1 , pp. V1–586 – V1–591, doi : 10.1109 / ICACTE.2010.5578947 , ISBN 978-1-4244-6539-2, S2CID 3108985
enlaces externos
- "Uso de filtros Bloom" Explicación detallada del filtro Bloom usando Perl
- Por qué los filtros Bloom funcionan como lo hacen (Michael Nielsen, 2012)
- Bloom Filters - A Tutorial, Analysis, and Survey (Blustein & 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 de floración más óptimos", Ely Porat (noviembre de 2007) Vídeo de Google TechTalk en YouTube