¿Cuál es la ventaja de usar filtros de floración?

Estoy leyendo sobre los filtros de floración y parecen tontos. Cualquier cosa que pueda lograr con un filtro de floración, podría lograrlo en menos espacio, de manera más eficiente, usando una sola función hash en lugar de múltiples, o eso es lo que parece. ¿Por qué usarías un filtro de floración y cómo es útil?

De Wikipedia :

Los filtros Bloom tienen una gran ventaja de espacio 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). Las estructuras enlazadas incurren en una sobrecarga de espacio lineal adicional para los punteros. Un filtro Bloom con 1% de error y un valor óptimo de k, por otro lado, 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 matrices, y en parte por su naturaleza probabilística. Si una tasa de falsos positivos del 1% parece demasiado alta, cada vez que agregamos aproximadamente 4.8 bits por elemento, la disminuimos diez veces.

Bastante claro para mí.

Un filtro de floración no almacena los elementos en sí, este es el punto crucial. No usa un filtro de floración para probar si un elemento está presente, lo usa para probar si ciertamente no está presente, ya que no garantiza falsos negativos. Esto le permite no hacer trabajo adicional para elementos que no existen en un conjunto (como E / S de disco para buscarlos).

Y todo en mucho menos espacio que algo como una tabla hash (que probablemente estará parcialmente en el disco para grandes conjuntos de datos). Aunque puede usar un filtro de floración junto con una estructura como una tabla hash, una vez que esté seguro de que el elemento tiene la posibilidad de estar presente.

Entonces, un patrón de uso de ejemplo podría ser:

Tiene una gran cantidad de datos en el disco: usted decide qué límite de error desea (por ejemplo, 1%), que prescribe el valor de m . Entonces se determina el k óptimo (a partir de la fórmula dada en el artículo). Completa su filtro a partir de estos datos enlazados al disco una vez.

Ahora tienes el filtro en RAM. Cuando necesita procesar algún elemento, consulta su filtro para ver si tiene alguna posibilidad de existir en su conjunto de datos. Si no es así, no se realiza ningún trabajo adicional. No hay lecturas de disco, etc. (lo que tendría que hacer si fuera un hash o un árbol, etc.).

De lo contrario, si el filtro dice "Sí, está ahí", hay un 1% de probabilidad de que esté mal, por lo que debe hacer el trabajo necesario para averiguarlo. El 99% del tiempo, realmente estará allí, por lo que el trabajo no fue en vano.

Alex lo ha explicado bastante bien. Para aquellos que aún no lo entendieron bien, con suerte este ejemplo los ayudará a comprender:

Digamos que trabajo para Google, en el equipo de Chrome, y quiero agregar una función al navegador que notifica al usuario si la URL que ingresó es una URL maliciosa. Así que tengo un conjunto de datos de aproximadamente 1 millón de URL maliciosas, el tamaño de este archivo es de alrededor de 25 MB. Dado que el tamaño es bastante grande (grande en comparación con el tamaño del navegador en sí), almaceno estos datos en un servidor remoto.

Caso 1: uso una función hash con una tabla hash. Decido una función hash eficiente y ejecuto todos los 1 millón de URL a través de la función hash para obtener claves hash. Luego hago una tabla hash (una matriz), donde la clave hash me daría el índice para colocar esa URL. Así que ahora, una vez que he realizado el hash y llenado la tabla hash, verifico su tamaño. He almacenado los 1 millón de URL en la tabla hash junto con sus claves. Entonces, el tamaño es de al menos 25 MB. Esta tabla hash, debido a su tamaño, se almacenará en un servidor remoto. Cuando aparece un usuario e ingresa una URL en la barra de direcciones, necesito verificar si es maliciosa. Por lo tanto, ejecuto la URL a través de la función hash (el propio navegador puede hacer esto) y obtengo una clave hash para esa URL. Ahora tengo que hacer una solicitud a mi servidor remoto con esa clave hash, para verificar si la URL particular en mi tabla hash con esa clave en particular, es la misma que la que ingresó el usuario. Si es así, entonces es malicioso y si no, entonces no es malicioso. Por lo tanto, cada vez que el usuario ingresa una URL, se debe realizar una solicitud al servidor remoto para verificar si es una URL maliciosa. Esto llevaría mucho tiempo y, por lo tanto, ralentizaría mi navegador.

Caso 2: uso un filtro de floración. La lista completa de 1 millón de URL se ejecuta a través del filtro de floración utilizando múltiples funciones hash y las posiciones respectivas se marcan como 1, en una gran variedad de 0. Digamos que queremos una tasa de falsos positivos del 1%, utilizando una calculadora de filtro de floración ( http://hur.st/bloomfilter?n=1000000&p=0.01), obtenemos el tamaño del filtro de floración requerido de solo 1,13 MB. Se espera este tamaño pequeño ya que, aunque el tamaño de la matriz es enorme, solo estamos almacenando 1 o 0 y no las URL como en el caso de la tabla hash. Esta matriz se puede tratar como una matriz de bits. Es decir, dado que solo tenemos dos valores 1 y 0, podemos establecer bits individuales en lugar de bytes. Esto reduciría el espacio ocupado en 8 veces. ¡Este filtro de floración de 1,13 MB, debido a su pequeño tamaño, se puede almacenar en el propio navegador web! Por lo tanto, cuando un usuario ingresa e ingresa una URL, simplemente aplicamos las funciones hash requeridas (en el propio navegador) y verificamos todas las posiciones en el filtro de floración (que se almacena en el navegador). Un valor de 0 en cualquiera de las posiciones nos dice que esta URL DEFINITIVAMENTE NO está en la lista de URL maliciosas y el usuario puede proceder libremente. Por lo tanto, no hicimos una llamada al servidor y, por lo tanto, ahorramos tiempo. Un valor de 1 nos dice que la URL PODRÍA estar en la lista de URL maliciosas. En estos casos, hacemos una llamada al servidor remoto y allí podemos usar alguna otra función hash con alguna tabla hash como en el primer caso para recuperar y verificar si la URL está realmente presente. Dado que la mayoría de las veces, no es probable que una URL sea maliciosa, el pequeño filtro de floración en el navegador se da cuenta de eso y, por lo tanto, ahorra tiempo al evitar las llamadas al servidor remoto. Solo en algunos casos, si el filtro bloom nos dice que la URL PODRÍA ser maliciosa, solo en esos casos hacemos una llamada al servidor. Ese 'PODER' es 99% correcto. En estos casos, hacemos una llamada al servidor remoto y allí podemos usar alguna otra función hash con alguna tabla hash como en el primer caso para recuperar y verificar si la URL está realmente presente. Dado que la mayoría de las veces, no es probable que una URL sea maliciosa, el pequeño filtro de floración en el navegador se da cuenta de eso y, por lo tanto, ahorra tiempo al evitar las llamadas al servidor remoto. Solo en algunos casos, si el filtro bloom nos dice que la URL PODRÍA ser maliciosa, solo en esos casos hacemos una llamada al servidor. Ese 'PODER' es 99% correcto. En estos casos, hacemos una llamada al servidor remoto y allí podemos usar alguna otra función hash con alguna tabla hash como en el primer caso para recuperar y verificar si la URL está realmente presente. Dado que la mayoría de las veces, no es probable que una URL sea maliciosa, el pequeño filtro de floración en el navegador se da cuenta de eso y, por lo tanto, ahorra tiempo al evitar las llamadas al servidor remoto. Solo en algunos casos, si el filtro bloom nos dice que la URL PODRÍA ser maliciosa, solo en esos casos hacemos una llamada al servidor. Ese 'PODER' es 99% correcto. el pequeño filtro de floración en el navegador se da cuenta de eso y, por lo tanto, ahorra tiempo al evitar llamadas al servidor remoto. Solo en algunos casos, si el filtro bloom nos dice que la URL PODRÍA ser maliciosa, solo en esos casos hacemos una llamada al servidor. Ese 'PODER' es 99% correcto. el pequeño filtro de floración en el navegador se da cuenta de eso y, por lo tanto, ahorra tiempo al evitar llamadas al servidor remoto. Solo en algunos casos, si el filtro bloom nos dice que la URL PODRÍA ser maliciosa, solo en esos casos hacemos una llamada al servidor. Ese 'PODER' es 99% correcto.

Entonces, al usar un pequeño filtro de floración en el navegador, hemos ahorrado mucho tiempo, ya que no necesitamos hacer llamadas al servidor para cada URL ingresada.

Podemos ver que la tabla hash con una sola función hash se usa para un propósito completamente diferente al de un filtro de floración. Ojalá esto aclare tus dudas :)

editar :

Implementé un filtro de floración para la tarea de pruebas de URL maliciosas en Python. El código se puede encontrar aquí: https://github.com/tarunsharma1/Bloom-Filter El código es muy simple de entender y se proporciona una descripción detallada en el archivo Léame.

Comenzaré con la explicación de qué es un filtro de floración, qué puede y qué no puede hacer, por qué lo necesitamos, mostraré una descripción intuitiva de cómo funciona y luego daré algún ejemplo de cuándo pueden ser útiles.

Entonces, un filtro de floración estándar es una estructura de datos probabilística que puede ^* :

• agregar elemento a un conjunto
• comprobar si un elemento está en el conjunto diciendo definitely not in the setopossibly in the set

Es possibly in the setexactamente por eso que se llama probabilístico. El uso de palabras inteligentes significa que los falsos positivos son posibles (puede haber casos en los que se crea falsamente que el elemento es positivo) pero los falsos negativos son imposibles.

Pero no puede ^* :

• eliminar un artículo del conjunto
• darle una lista de todos los elementos que se encuentran actualmente en su conjunto

^* _{Este conjunto de can / can't es para un filtro de floración básico. Debido a que es una estructura de datos útil que se creó hace mucho tiempo, la gente descubrió cómo aumentarla con otras funciones útiles .}

Pero espere un minuto: ya conocemos una estructura de datos que puede responder a todo esto sin un "posible" vago y también sin todas las limitaciones (no se puede eliminar, no se puede mostrar todo). Y se llama conjunto . Y aquí viene la principal ventaja de un filtro de floración: ahorra espacio y es constante en el espacio .

Esto quiere decir que no importa cuántos elementos almacenemos allí, el espacio será el mismo. Sí, un filtro de floración con 10^6elementos (filtro de floración inútil) ocupará la misma cantidad de espacio que un filtro de floración con 10^20elementos y el mismo espacio que un filtro de floración con 0elementos. Entonces, ¿cuánto espacio tomará? Depende de usted decidir (pero hay un intercambio de: cuantos más elementos tenga, más inseguro estará con su possible in the setrespuesta.

Otra cosa interesante es que es espacio constante. Cuando guarda los datos en un conjunto, realmente tiene que guardar estos datos. Entonces, si almacena this long string in the set, debe usar al menos 27 bytes de espacio. Pero para un error del 1% y un valor óptimo de k ^** , necesitará ~ 9.6 bits (<2 bytes) por cualquier elemento (ya sea un int corto o una pared enorme de texto).

Otra propiedad es que todas las operaciones están tomando un tiempo constante, que no es en absoluto lo mismo que el tiempo constante amortizado en el caso de los conjuntos (recuerde que si el conjunto tiene colisiones, se puede deteriorar en el O(n)tiempo).

^** _{k es un valor de las funciones hash utilizadas en el filtro de floración}

No describiré cómo funcionan los filtros de floración (el artículo de Wikipedia hace un muy buen trabajo explicando todo). Aquí solo contaré brevemente los conceptos básicos.

• inicia una matriz de bits vacía de longitud m
• selecciona kdiferentes funciones hash (cuanto más independientes, mejor)
• si desea agregar un elemento, calcula todos los khashes de este valor y establece los bits correspondientes en 1
• si desea verificar si el elemento existe, también calcula todos los khash y si al menos uno de ellos no está configurado, seguramente no está en el conjunto. De lo contrario, puede estar en el set.

Incluso esta descripción es suficiente para entender por qué no podemos estar seguros (puede obtener todos los bits establecidos a partir de varios otros valores). Aquí hay una visualización muy agradable de cómo funciona .

Entonces, ¿cuándo pueden ser útiles los filtros de floración? La respuesta corta está en todos los lugares donde los falsos positivos son aceptables y donde querría verificar si hay algo en el conjunto , pero incluso si no lo están, puede ser una primera línea de defensa para descartar costosas llamadas a los verificadores.

Aquí hay una lista de descripciones más concretas:

• un ejemplo estándar de sitios web maliciosos y un navegador se describe en casi cualquier lugar donde la gente habla de filtros de floración
• es una contraseña débil: en lugar de tener un gran conjunto de todas las posibles contraseñas débiles, puede verificar si la contraseña seguramente no es débil con un filtro de floración mucho más pequeño
• Si tiene una lista de artículos y una lista de usuarios, puede usar el filtro Bloom para mostrar los artículos de los usuarios que no han leído. Lo interesante es que solo puede tener un filtro (verifica si la combinación de user_id + article_id está ahí)
• bitcoin usa un filtro de floración para la sincronización de billetera
• Los servidores web de Akamai 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 solo una 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 éxito 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 (tomado de ejemplos en el filtro Bloom artículo en wiki)

Los filtros Bloom son bastante útiles en bioinformática. Pueden ser más eficientes en términos de espacio en comparación con el uso de un hash normal, especialmente cuando el tamaño de las cadenas con las que está trabajando puede ser de cientos de millones de letras con un alfabeto muy pequeño, es decir, {A, G, T, C}. Por lo general, se utilizan para evaluar si un determinado k-mer está presente o no en un genoma. Hay un ejemplo de uno usado para algo relevante aquí .

EDITAR:

Las múltiples funciones hash se utilizan para minimizar los falsos positivos. La esperanza es que entre todas las funciones de k-hash, cada valor tenga una firma única en la matriz de bits en comparación con cualquier otro valor posible. Sin embargo, existen falsos positivos, pero se pueden minimizar a un nivel manejable. Utilizando esta técnica, usted hash elementos independientemente de su tamaño. Cuando los busca, usa cada función hash y verifica que sus valores de bits sean todos 1.

Compare esto con el genoma humano, donde un aumento en el tamaño del elemento aumenta significativamente el tamaño de la tabla hash (el tamaño de la tabla es 4 * 4 ^k ). Esto es asumiendo que codifica los elementos usando 2 bits / letra.

Si un filtro de Bloom devuelve que un elemento es miembro del conjunto, existe una cierta probabilidad de un falso positivo. Si solo se usara una única función hash para indicar la pertenencia al conjunto, la probabilidad de un falso positivo sería mayor que el uso de múltiples funciones hash.