¿Cuáles son las mejores aplicaciones de los filtros Bloom?

Oracle usa filtros Bloom para realizar la poda de particiones Bloom para ciertas consultas. Por ejemplo, al unir una tabla de dimensiones de fecha con una tabla de hechos grande dividida por fecha, se puede construir un filtro Bloom sobre la dimensión de fecha y usarlo para podar particiones de la tabla de hechos [1].

[1] http://structureddata.org/2010/1 …

Quora implementó un filtro de floración fragmentado en el backend de alimentación para filtrar historias que la gente ha visto antes. Es mucho más rápido y más eficiente en memoria que las soluciones anteriores (Redis, Tokyo Cabinet y DB) y ahorra cientos de ms en ciertos tipos de solicitudes.

Como otros mencionaron en el hilo, el filtro Bloom es una forma de saber rápidamente si un elemento no pertenece al conjunto. La utilicé por última vez cuando rastreaba mil millones de páginas para construir un motor de búsqueda fuera de línea. En ese momento teníamos cuatro máquinas con 4 GB de RAM, de las cuales solo 2.1 GB eran accesibles para la máquina virtual Java. Estábamos haciendo un rastreo abierto (descubriendo páginas sobre la marcha) y teníamos que asegurarnos de no rastrear las mismas páginas una y otra vez. Si hubiéramos usado un hashset con la clave de 8 bytes como hash de URL, hubiéramos necesitado más de 2 Gigs solo para este conjunto. Así que terminamos usando el filtro Bloom para esto.

Otra aplicación que puedo ver para algo como esto es una aplicación de escritura única, sin actualización, por ejemplo, un servicio de acortador de URL. Aquí, una vez que se ha asignado una URL pequeña a una URL que no se va a actualizar. Entonces, en lugar de necesitar hacer una llamada a la base de datos y usar mucha memoria en Memcache, estos datos también pueden almacenarse en un filtro de floración.

Los filtros Bloom pueden usarse para muchas cosas. En Insieve los usamos para

1. Mantenga un registro de las páginas que un usuario ha visitado sin poder enumerar los enlaces que ha visitado. Esto nos ayuda a abordar las preocupaciones de privacidad que las personas pueden tener acerca de tener nuestro complemento en su sistema. El filtro de floración solo nos permite probar si se ha visitado una url, pero no enumerar las url que han visitado.

2. Utilizamos una versión modificada de bloom-filter para detectar y eliminar eficientemente las placas de caldera que aparecen en el texto que rastreamos. Mantenemos una serie de filtros de recuento de flores. Seguimos agregando a un filtro de floración dado y pasamos al siguiente cuando su capacidad está llena para el nivel de tasa de error dado … y cuando todos están llenos, reiniciamos el filtro de floración más antiguo y lo usamos para completar nuevas ejecuciones de texto. En cualquier etapa, si el recuento de un hash dado excede un umbral preestablecido, se gradúa a un filtro de floración de membresía utilizado para la consulta de placa de caldera. Esto nos da un filtro de envejecimiento de forma que podemos usar para detectar placas de caldera. El hecho de que este es un filtro de floración antiguo es importante ya que las otras ejecuciones de texto válidas deben eliminarse gradualmente o conducirán al almacenamiento de muchas ejecuciones de texto bueno sin ninguna razón.

3. También utilizamos filtros de floración para reducir el número de búsquedas en la base de datos. Entonces, solo buscamos el db cuando el filtro de floración dice verdadero.

Facebook usa filtros de floración para la búsqueda de escritura anticipada, para buscar amigos y amigos de amigos en una consulta escrita por el usuario. El filtro de floración es de solo 16 bits por conexión de amigo (una ventaja en el gráfico social de Facebook) y lo han llamado “la floración más pequeña del mundo” 😛!

La charla describe Typeahead Search Tech Talk (15/06/2010) cómo funciona.

LinkedIn también usa filtros de floración para la consulta de escritura anticipada de una manera muy similar a la de Facebook: Cleo: la tecnología de código abierto detrás de la búsqueda de mecanografía de LinkedIn | Ingeniería de LinkedIn

Cualquier aplicación donde un falso positivo está bien, pero un falso negativo no lo está.

El uso más común para los filtros de floración probablemente sea probar para ver si existe un elemento en el disco antes de realizar cualquier E / S. A veces se arriesga a buscar algo que no está allí, pero nunca se saltará la prueba de un segmento porque el filtro de floración dijo que no estaba allí y que estaba. Esto debería reducir su E / S para búsquedas dramáticamente en grandes conjuntos de datos.

Otro buen uso son los recuentos únicos y baratos. Si necesita saber la cantidad aproximada de elementos únicos que ha visto (por ejemplo, en una secuencia), puede usar un filtro de floración para probar si ha visto ese elemento antes. Si el filtro de floración dice que no está en el conjunto, incrementa el recuento en uno. Obtendrá falsos positivos (bajo conteo), pero es más barato que tener que mantener todo el conjunto en la memoria. Es bueno poder decir “hemos visto al menos tantos elementos únicos”.

Apache HBase utiliza el filtro de floración para aumentar la velocidad de lectura al filtrar las lecturas innecesarias del disco de los bloques HFile que no contienen una fila o columna en particular.

Dado que HBase almacena internamente una fila lógica por pares clave-valor separados para cada columna, el usuario puede elegir construir filtros de floración por (1) ROW o (2) ROW ＋ COLUMN dependiendo de los patrones de consulta reales.

Transactional Memory (TM) ha aplicado recientemente filtros Bloom para detectar conflictos de acceso a memoria entre subprocesos.

TM es un estilo de programación concurrente en desarrollo que espera aliviar los desafíos de la programación con bloqueos (serialización o punto muerto / carreras). La tarea del programador es escribir un código transaccional (“simple”), y el sistema TM subyacente rastrea los accesos a la memoria y evita las carreras de datos / punto muerto.

El siguiente es un subconjunto de sistemas de hardware TM (HTM) y software TM (STM) que usan filtros Bloom para representar la información de acceso de un hilo:

• 2006 a granel (Ceze et al. HTM)
  http://portal.acm.org/citation.c …
• 2007/8 Notario (Yen y Sanchez et al. HTM)
  http://portal.acm.org/citation.c …
• 2008 RingSTM (Spear et al. STM)
  http://portal.acm.org/citation.c …
• 2009 Explotación local para TM (Quislant et al. HTM)
  http://portal.acm.org/citation.c …
• 2010 Una memoria transaccional de software eficiente que utiliza la invalidación de tiempo de confirmación (Gottschlich et al. STM)
  http://portal.acm.org/citation.c …

Los filtros Bloom han encontrado que la aplicación reciente es redes de sensores de sistemas integrados e Internet de las cosas, especialmente motivos para comprobar si una mota puede comunicarse con otra mota en la misma red Ad-hoc.

Esto está siendo utilizado por militares de todo el mundo para establecer redes de monitoreo remoto, así como agencias espaciales como la NASA e ISRO.

Un ejemplo: comprobar rápidamente si está seguro de que no existe un registro en una base de datos, para evitar una consulta profunda en el registro inexistente que puede causar un funcionamiento lento del disco.

El propio Bloomfilter permanece en la memoria y, por lo general, consume memoria limitada, incluso si coloca todas las claves, en comparación con el caché que solo puede contener una pequeña parte de los registros.

Bitly usa un filtro de floración para evitar redirigir a los usuarios a sitios web maliciosos. Echa un vistazo a dablooms para más detalles.

Hay algunas aplicaciones interesantes de Bloom Filters en Bioinformática.

Los filtros Bloom se utilizan en los árboles Bloom de secuencia para consultar una gran cantidad de conjuntos de secuencias para kmers de longitud arbitraria. El problema es encontrar en qué conjuntos de datos está presente el kmer. Sequence Bloom Tree ofrece una aproximación al problema que puede ser un par de órdenes de magnitud más rápido que otros enfoques. Cuánto más rápido depende de lo que consultes y cómo esté configurado. Una propiedad muy agradable es la eficiencia espacial de la estructura de datos. Se puede comprimir en un formato que se puede consultar directamente, lo que facilita el análisis de vastos conjuntos de datos.

La estructura de datos Sequence Bloom Trees se describe en el siguiente documento y también pone a disposición una implementación.

Búsqueda rápida de miles de experimentos de secuenciación de lectura corta.

http://ieeexplore.ieee.org/xpl/a …

El documento anterior propone el uso de filtros Bloom para encontrar clics duplicados en una secuencia de datos publicitarios, para detectar posibles fraudes por clics. Mantienen los últimos ‘n’ clics en un filtro Bloom y buscan el clic entrante. Dado que un filtro Bloom no tiene falsos negativos, es eficiente para el caso común de que un clic no sea fraude.

Para buscar la palabra clave específica sobre los datos cifrados, se utilizan filtros de floración para verificar su presencia en un archivo. Si existe una palabra clave, podemos devolver el archivo en particular.

Vea la publicación de Alex Smola sobre filtros de Bloom y aplicaciones: http://blog.smola.org/post/42065 …