Filtro Bloom en Java con guayaba

Buen dia a todos.

Lanzamos un nuevo curso: "Algoritmos para desarrolladores" , diseñado para aquellos que mejoran su conocimiento de diversas estructuras y algoritmos para el procesamiento de datos, la resolución de problemas algebraicos y problemas de programación dinámica para varios idiomas. Así que hoy compartimos una pequeña nota sobre el funcionamiento del filtro Bloom en Java.

Introduccion

En este artículo, veremos la estructura del filtro Bloom de la biblioteca Guava. El filtro Bloom es una estructura de datos probabilística con un uso eficiente de la memoria que podemos usar para responder la pregunta "¿Está este elemento en el conjunto?".

No hay falsos negativos en el filtro Bloom, por lo que si devuelve falso, puede estar 100% seguro de que este elemento no está en el conjunto.

Sin embargo, el filtro Bloom puede devolver falsos positivos , por lo que cuando se devuelve verdadero, la probabilidad de que el elemento esté realmente en el conjunto es alta, pero la probabilidad no es del 100%.

Para obtener más información sobre el funcionamiento del filtro Bloom, consulte esta guía.



Adicción a Maven

Usaremos la implementación de guayaba del filtro Bloom, así que agregue una dependencia de guayaba
La última versión se puede encontrar en Maven Central .

<dependency> <groupId>com.google.guava</groupId> <artifactId>guava</artifactId> <version>22.0</version> </dependency> 

¿Por qué usar un filtro de floración?

El filtro Bloom está diseñado para ser económico y rápido . Al usarlo, podemos aclarar la probabilidad de respuestas falsas positivas que estamos listos para aceptar y, de acuerdo con la configuración, el filtro Bloom ocupará la menor cantidad de memoria posible.

Debido a su economía, el filtro Bloom se adapta fácilmente a la memoria incluso con una gran cantidad de elementos. Algunas bases de datos, incluidas Cassandra y Oracle, usan este filtro para las comprobaciones iniciales antes de acceder al disco o al caché, por ejemplo, cuando se recibe una solicitud de ID específica.

Si el filtro dice que no hay ID, la base de datos puede dejar de procesar la solicitud y regresar al cliente. De lo contrario, la consulta va al disco y devuelve el elemento encontrado.

Crear un filtro de floración

Supongamos que queremos crear un filtro Bloom para no más de 500 enteros, y estamos triplicados por una probabilidad del uno por ciento (0.01) de falsos positivos.

Para hacer esto, podemos usar la clase BloomFilter de la biblioteca Guava. Es necesario transferir el número de elementos informados al filtro y la probabilidad deseada de falsos positivos:

 BloomFilter<Integer> filter = BloomFilter.create( Funnels.integerFunnel(), 500, 0.01); 

Ahora agregue algunos números al filtro:

 filter.put(1); filter.put(2); filter.put(3); 

Agregamos solo tres elementos y determinamos el número máximo de inserciones: 500, por lo que nuestro filtro Bloom debería dar resultados bastante precisos. mightContain() con el método mightContain() :

 assertThat(filter.mightContain(1)).isTrue(); assertThat(filter.mightContain(2)).isTrue(); assertThat(filter.mightContain(3)).isTrue(); assertThat(filter.mightContain(100)).isFalse(); 

Como su nombre lo indica, no podemos estar 100% seguros de que este elemento realmente esté en el filtro si el método devuelve verdadero.

En nuestro caso, cuando mightContain() devuelve verdadero, 99% de que el elemento está en el filtro y 1%, que el resultado es falso positivo. Si el filtro devuelve falso, puede estar 100% seguro de que falta el elemento.

Filtro de floración sobresaturada

Al diseñar un filtro Bloom, es importante proporcionar un valor suficientemente preciso para el número esperado de elementos. De lo contrario, nuestro filtro devolverá falsos positivos con mucha más frecuencia de la que nos gustaría. Considera un ejemplo.

Supongamos que creamos un filtro con la probabilidad deseada de falso positivo igual al uno por ciento y el número esperado de elementos igual a cinco, pero luego insertamos 100,000 elementos:

 BloomFilter<Integer> filter = BloomFilter.create( Funnels.integerFunnel(), 5, 0.01); IntStream.range(0, 100_000).forEach(filter::put); 

Esperando tan pocos elementos, el filtro ocupará muy poca memoria.
Sin embargo, después de agregar una cantidad mucho mayor de elementos, el filtro se sobresatura y tiene una mayor probabilidad de producir un resultado falso positivo que el uno por ciento deseado.

Tenga en cuenta que el método mightContatin() devuelve verdadero incluso para un valor que no insertamos previamente en el filtro.

Conclusión

En este tutorial rápido, observamos la naturaleza probabilística de la estructura de datos del filtro Bloom, utilizando la implementación de Guava.

La implementación de todos estos ejemplos y fragmentos de código se puede encontrar en el proyecto GitHub .

Este es un proyecto Maven, por lo que importar y lanzar no debería ser difícil.

El fin

Estamos a la espera de comentarios y preguntas que, como siempre, se pueden dejar aquí e ir a la jornada de puertas abiertas al profesor del curso Mikhail Gorshkov .