Categorías: Tecnología

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.

Oscar Montalvo

Ciudadano del mundo, periodista y deportista frustrado. Le gusta la literatura universal así como las películas de corte histórico, de ciencia ficción y, por supuesto, de terror. No deja de sorprenderse con los avances tecnológicos del día a día, al mismo tiempo de admirar diferentes talentos, aunque no termina por descubrir completamente los suyos.

Compartir
Publicado por
Oscar Montalvo

Entradas recientes

4 consejos para dejar tu celular como nuevo

Hicimos un guía con las herramientas fundamentales y gratuitas para limpiar, acelerar, ahorrar batería y…

6 años hace

Usuarios de PSafe Total deben actualizar su aplicación

Versiones 2.9 y anteriores de la aplicación “PSafe Total” ya no serán actualizadas

6 años hace

Cómo borrar el WhatsApp de un celular robado o perdido

Garantiza tu privacidad, aunque te hayan robado el teléfono

6 años hace

5 cuidados que debes tener para que no hackeen tu celular

Trucos simples pero fundamentales para bloquear los ataques de bandidos a tu teléfono

6 años hace

Descubre cuáles aplicaciones tienen acceso a tus datos personales de Facebook

Aprende también cómo removerlas y a elegir los datos que pueden ser accedidos

6 años hace

Como no caer en las trampas de los enlaces falsos

Conoce la herramienta que identifica y bloquea enlaces maliciosos en tiempo real

6 años hace