Bloom Filter en Java usando Guayaba

1. Información general

En este artículo, veremos la construcción del filtro Bloom de la biblioteca de Guava . Un filtro de Bloom es una estructura de datos probabilística eficiente en la memoria que podemos usar para responder a la pregunta de si un elemento dado está o no en un conjunto .

No hay falsos negativos con un filtro Bloom, por lo que cuando devuelve falso , podemos estar 100% seguros de que el elemento no está en el conjunto.

Sin embargo, un filtro Bloom puede devolver falsos positivos , por lo que cuando devuelve verdadero , existe una alta probabilidad de que el elemento esté en el conjunto, pero no podemos estar 100% seguros.

Para un análisis más profundo de cómo funciona un filtro Bloom, puede seguir este tutorial.

2. Dependencia de Maven

Usaremos la implementación de Guava del filtro Bloom, así que agreguemos la dependencia de guava :

 com.google.guava guava 29.0-jre 

La última versión se puede encontrar en Maven Central.

3. ¿Por qué utilizar Bloom Filter?

El filtro Bloom está diseñado para ahorrar espacio y ser rápido . Al usarlo, podemos especificar la probabilidad de respuestas falsas positivas que podemos aceptar y, según esa configuración, el filtro Bloom ocupará la menor cantidad de memoria posible.

Debido a esta eficiencia de espacio, el filtro Bloom encajará fácilmente en la memoria incluso para una gran cantidad de elementos. Algunas bases de datos, incluidas Cassandra y Oracle, usan este filtro como la primera verificación antes de ir al disco o al caché, por ejemplo, cuando entra una solicitud de una ID específica.

Si el filtro devuelve que el ID no está presente, la base de datos puede detener el procesamiento posterior de la solicitud y regresar al cliente. De lo contrario, va al disco y devuelve el elemento si se encuentra en el disco.

4. Creación de un filtro Bloom

Suponga que queremos crear un filtro Bloom para hasta 500 enteros y que podemos tolerar una probabilidad del uno por ciento (0.01) de falsos positivos.

Podemos usar la clase BloomFilter de la biblioteca de Guava para lograr esto. Necesitamos pasar la cantidad de elementos que esperamos que se inserten en el filtro y la probabilidad de falso positivo deseada:

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

Ahora agreguemos algunos números al filtro:

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

Agregamos solo tres elementos y definimos que el número máximo de inserciones será 500, por lo que nuestro filtro Bloom debería producir resultados muy precisos . Probemos usando 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 sugiere el nombre, no podemos estar 100% seguros de que un elemento dado esté realmente en el filtro cuando el método devuelve verdadero .

Cuando mightContain () devuelve verdadero en nuestro ejemplo, podemos tener un 99% de certeza de que el elemento está en el filtro y hay una probabilidad del uno por ciento de que el resultado sea un falso positivo. Cuando el filtro devuelve falso , podemos estar 100% seguros de que el elemento no está presente.

5. Filtro de floración saturada

Cuando diseñamos nuestro filtro Bloom, es importante que proporcionemos un valor razonablemente preciso para el número esperado de elementos . De lo contrario, nuestro filtro devolverá falsos positivos a una tasa mucho mayor de la deseada. Veamos un ejemplo.

Supongamos que creamos un filtro con una probabilidad falsa positiva deseada del uno por ciento y algunos elementos esperados iguales a cinco, pero luego insertamos 100,000 elementos:

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

Debido a que el número esperado de elementos es tan pequeño, el filtro ocupará muy poca memoria.

Sin embargo, a medida que agregamos más elementos de lo esperado, el filtro se satura y tiene una probabilidad mucho mayor de devolver resultados falsos positivos que el uno por ciento deseado:

assertThat(filter.mightContain(1)).isTrue(); assertThat(filter.mightContain(2)).isTrue(); assertThat(filter.mightContain(3)).isTrue(); assertThat(filter.mightContain(1_000_000)).isTrue();

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

6. Conclusión

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

Puede encontrar la implementación de todos estos ejemplos y fragmentos de código en el proyecto GitHub.

Este es un proyecto de Maven, por lo que debería ser fácil de importar y ejecutar tal como está.