Estructura de datos: ¿Sabes que es Bloom Filter?

En una anterior oportunidad hablamos sobre el sistema de código abierto Cassandra, el cual es usado para administrar grandes volúmenes de datos en tiempo real, lo que permite una respuesta inmediata ante fallas. Pues bien, ese sistema, que es extremadamente rápido en escrituras y lecturas, debe en buena parte sus características a una estructura de datos denominada Bloom Filter.

Esta herramienta es una manera muy eficiente de preguntar si un dato existe en un conjunto o no (lo cual utiliza Cassandra para evitar accesos en vano). En otras palabras, está diseñada para decirnos, con rapidez, si un elemento está presente dentro de un conjunto.

Se trata de un algoritmo probabilístico que puede arrojar falsos positivos, pero nunca falsos negativos. Conocer esa probabilidad de ocurrencia de dichos errores y diseñar las consultas siendo conscientes de que dichos errores pueden producirse es vital a la hora de construir las gigantescas bases de datos que hacen posibles numerosas aplicaciones.

¿Cómo funciona?

Actúa con dos elementos. Uno llamado array de m bits, inicializado a cero, y un conjunto de k funciones hash que, dado un dato, generará números entre 0 y m-1.

Cuando un especialista ingresa un dato, este pasara por las funciones hash, las cuales indicarán la posición del array donde se cambiará sus valores a 1. Es un proceso complejo, pero servirá para cuando lleguen nuevas cadenas y queramos comprobar si un elemento existe o no dentro de un conjunto.

Lo principal es comprobar que algunas posiciones en el array generada por algunas de las funcioness hash nos devuelva 0.

Es como un juego de quién es quién, pero con muchos sospechosos. El jugador «A» agrega sospechosos, mientras que el jugador «B» cuestiona al jugador «A» sobre los atributos de los sospechosos que colocó. Llevando esto al área técnica, esos sospechosos serían los datos y sus atributos las funciones hash. La lista total de atributos que guarde el jugador «A» sería el array de bits.

Vemos este ejemplo:

Mark Zuckerberg
Atributos: “Rico”, “Joven” y “Americano”

Tom Hanks
Atributos: “Rico”, “Actor” y “Americano”

Supongamos que el jugador «A» coloca como sospechoso a Mark Zuckerberg, lo que significa que ahora ese jugador tiene como características “Rico”, “joven” y “Americano”. Es así que cuando el jugador «B» pregunte por Tom Hanks, pese a que tiene las cualidades “Rico” y “Americano” también, no posee la de “joven”, por  lo que puede estar seguro de que Tom Hanks no es uno de los sospechosos.

Es así como funciona Bloom Filter solo que con muchos más datos. Todo un ejército de información al servicio de los especialistas.