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

data-structures bloom-filter (5)

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

Alex lo ha explicado bastante bien. Para aquellos que aún no entendieron bien, espero que este ejemplo les ayude a entender:

Digamos que trabajo para Google, en el equipo de Chrome, y quiero agregar una característica al navegador que notifica al usuario si la URL que ingresó es una URL maliciosa. Así que tengo un conjunto de datos de alrededor de 1 millón de URL maliciosas, el tamaño de este archivo es de alrededor de 25 MB. Como 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 de hash eficiente y ejecuto todo el millón de URL a través de la función hash para obtener las claves hash. Luego hago una tabla hash (una matriz), donde la clave hash me da el índice para colocar esa URL. Entonces, una vez que he procesado y llenado la tabla hash, verifico su tamaño. He almacenado todos 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 un usuario aparece e ingresa una URL en la barra de direcciones, necesito verificar si es malicioso. Por lo tanto, ejecuto la URL a través de la función hash (el navegador mismo 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 ingresada por el usuario. Si es así, entonces es malicioso y, en caso negativo, 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 se trata de una URL maliciosa. Esto tomaría mucho tiempo y, por lo tanto, haría que mi navegador fuera lento.

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 están marcadas como 1, en una gran variedad de ceros. Digamos que queremos una tasa de falsos positivos del 1%, usando una calculadora de filtro de bloom ( http://hur.st/bloomfilter?n=1000000&p=0.01 ), obtenemos el tamaño del filtro de floración requerido como solo 1.13 MB. Se espera este tamaño pequeño ya que, aunque el tamaño de la matriz es enorme, solo almacenamos 1s o 0s 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 tomado por 8 veces. ¡Este filtro de 1.13 MB de floración, debido a su pequeño tamaño, puede almacenarse en el navegador web mismo! Por lo tanto, cuando un usuario accede e ingresa una URL, simplemente aplicamos las funciones hash requeridas (en el navegador mismo) y verificamos todas las posiciones en el filtro bloom (que está almacenado 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 PUEDE 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 realmente está presente. Como la mayoría de las veces, una URL no es maliciosa, el pequeño filtro de floración en el navegador se da cuenta de eso y ahorra tiempo al evitar las llamadas al servidor remoto. Solo en algunos casos, si el filtro de bloom nos dice que la URL PUEDE ser maliciosa, solo en esos casos hacemos una llamada al servidor. Ese ''Might'' 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 por cada URL ingresada.

Podemos ver que la tabla hash con una sola función hash se usa para un propósito diferente en conjunto a un filtro bloom. Espero que esto aclare tus dudas :)

editar :

Implementé un filtro de floración para la tarea de prueba maliciosa de URL 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 dar un ejemplo cuando pueden ser útiles.

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

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

Esto possibly in the set es exactamente por lo que se llama probabilístico. Usar palabras inteligentes significa que los falsos positivos son posibles (puede haber casos en los que falsamente piensa que el elemento es positivo) pero los falsos negativos son imposibles.

Pero no puede ^* :

eliminar un elemento del conjunto
darle una lista de todos los elementos que están actualmente en su conjunto

^* _{Este conjunto de can / can not es para un filtro de bloom básico.} _{Debido a que es una estructura de datos útil que se creó hace mucho tiempo, las personas descubrieron cómo augment con otras funciones useful .}

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

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

Otra cosa interesante es que es espacio constante. Cuando guardas los datos en un conjunto, debes guardarlos. 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 un gran muro de texto).

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

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

No describiré cómo funcionan los filtros de bloom (el artículo de wikipedia hace un muy buen trabajo explicando todo). Aquí voy a contar brevemente lo básico.

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

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

Entonces, ¿cuándo pueden ser útiles los filtros de floración? La respuesta corta está en todas partes donde los falsos positivos son aceptables y en los que desearí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 michaelnielsen.org/ddi/why-bloom-filters-work-the-way-they-do se describe en casi cualquier place donde la gente hable sobre filtros de bloom
es una contraseña débil: en lugar de tener un gran conjunto de todas las contraseñas débiles posibles, simplemente 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 puedes tener solo un filtro (verifica si la combinación de user_id + article_id está allí)
Bitcoin usa un filtro de bloom para la sincronización de la billetera
Los servidores web de Akamai usan filtros Bloom para evitar que se almacenen "maravillas de un solo golpe" en sus cachés de disco. Las maravillas de un solo golpe 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é. Usar un filtro Bloom para detectar la segunda solicitud de un objeto web y almacenar ese objeto solo en su segunda solicitud evita que las maravillas de un solo golpe ingresen a la memoria caché del disco, reduciendo significativamente la carga de trabajo del disco y aumentando las tasas de aciertos de la memoria caché. artículo en wiki)

De la en.wikipedia.org/wiki/Bloom_filter :

Los filtros de Bloom tienen una gran ventaja de espacio con respecto a 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, que pueden requerir desde un número pequeño de bits, enteros pequeños hasta un número arbitrario de bits, como cadenas (los intentos son una excepción, ya que pueden compartir almacenamiento entre elementos con los mismos prefijos). Las estructuras vinculadas incurren en una sobrecarga de espacio lineal adicional para los punteros. Un filtro Bloom con un 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 las matrices, y en parte de su naturaleza probabilística. Si una tasa de 1% de falsos positivos parece demasiado alta, cada vez que agreguemos alrededor de 4,8 bits por elemento lo disminuiremos en 10 veces.

Muy claro para mí.

Un filtro de floración no almacena los elementos, este es el punto crucial. No utiliza un filtro de bloom para comprobar si hay un elemento presente; lo usa para comprobar si no está presente, ya que no garantiza falsos negativos. Esto le permite no realizar trabajos adicionales para elementos que no existen en un conjunto (como disco IO para buscarlos).

Y todo en un espacio significativamente menor que algo así 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 una posibilidad de estar presente.

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

Usted tiene una gran cantidad de datos, en el disco: usted decide qué error enlazado desea (por ejemplo, 1%), que prescribe el valor de m . Entonces se determina la k óptima (de la fórmula dada en el artículo). Rellena el filtro de estos datos vinculados al disco una vez.

Ahora tienes el filtro en la RAM. Cuando necesite procesar algún elemento, consulte su filtro para ver si existe la posibilidad de que exista en su conjunto de datos. Si no lo hace, no se realiza ningún trabajo adicional. No se lee el disco, etc. (lo que tendrías que hacer si fuera un hash o un árbol, etc.).

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

Los filtros Bloom son bastante útiles en bioinformática. Pueden ser más eficientes en cuanto a espacio en comparación con el uso de un hash regular, especialmente cuando el tamaño de las cadenas con las que trabajas puede ser de cientos de millones de letras con un alfabeto muy pequeño, es decir, {A, G, T, C}. Generalmente se usan para evaluar si un cierto k-mer está presente o ausente en un genoma. Hay un ejemplo de uno usado para algo relevante here .

EDITAR:

Las múltiples funciones hash se utilizan para minimizar los falsos positivos. La esperanza es que entre todas las funciones k-hash cada valor tendrá una firma única en el conjunto de bits en comparación con cualquier otro valor posible. Sin embargo, existen falsos positivos, pero se pueden minimizar a un nivel manejable. Usando esta técnica, hash elementos independientemente de su tamaño. Cuando los busca, utiliza cada función hash y comprueba para asegurarse de que sus bit-values 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 supone que codificas los elementos usando 2 bits / letra.

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