{"id":10696,"date":"2015-06-19T19:00:20","date_gmt":"2015-06-19T22:00:20","guid":{"rendered":"https:\/\/www.psafe.com\/es\/blog\/?p=10696"},"modified":"2015-06-22T11:59:09","modified_gmt":"2015-06-22T14:59:09","slug":"que-es-bloom-filter","status":"publish","type":"post","link":"https:\/\/www.psafe.com\/es\/blog\/que-es-bloom-filter\/","title":{"rendered":"Estructura de datos: \u00bfSabes que es Bloom Filter?"},"content":{"rendered":"

En una anterior oportunidad hablamos sobre el sistema de c\u00f3digo abierto Cassandra<\/a>, el cual es usado para administrar grandes vol\u00famenes de datos en tiempo real, lo que permite una respuesta inmediata ante fallas. Pues bien, ese sistema, que es extremadamente r\u00e1pido en escrituras y lecturas, debe en buena parte sus caracter\u00edsticas a una estructura de datos denominada Bloom Filter<\/strong>.<\/p>\n

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\u00e1 dise\u00f1ada para decirnos, con rapidez, si un elemento est\u00e1 presente dentro de un conjunto.<\/p>\n

Se trata de un algoritmo probabil\u00edstico que puede arrojar falsos positivos, pero nunca falsos negativos. Conocer esa probabilidad de ocurrencia de dichos errores y dise\u00f1ar 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.<\/p>\n

\u00bfC\u00f3mo funciona?<\/strong><\/h3>\n

Act\u00faa con dos elementos. Uno llamado array<\/strong> de m<\/strong> bits, inicializado a cero, y un conjunto de k<\/strong> funciones hash que, dado un dato, generar\u00e1 n\u00fameros entre 0 y m-1<\/strong>.<\/p>\n

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

Lo principal es comprobar que algunas posiciones en el array generada por algunas de las funcioness hash nos devuelva 0.<\/p>\n

Es como un juego de qui\u00e9n es qui\u00e9n, pero con muchos sospechosos. El jugador \u00abA\u00bb agrega sospechosos, mientras que el jugador \u00abB\u00bb cuestiona al jugador \u00abA\u00bb sobre\u00a0los atributos de los sospechosos que coloc\u00f3. Llevando esto al \u00e1rea t\u00e9cnica, esos sospechosos ser\u00edan los datos y sus atributos las funciones hash. La lista total de atributos que guarde el jugador \u00abA\u00bb ser\u00eda el array de bits.<\/p>\n

Vemos este ejemplo:<\/p>\n

Mark Zuckerberg<\/strong>
\nAtributos: \u201cRico\u201d, \u201cJoven\u201d y \u201cAmericano\u201d<\/p>\n

Tom Hanks<\/strong>
\nAtributos: \u201cRico\u201d, \u201cActor\u201d y \u201cAmericano\u201d<\/p>\n

Supongamos que el jugador \u00abA\u00bb coloca como sospechoso a Mark Zuckerberg, lo que significa que ahora ese jugador tiene como caracter\u00edsticas \u201cRico\u201d, \u201cjoven\u201d y \u201cAmericano\u201d. Es as\u00ed que cuando el jugador \u00abB\u00bb pregunte por Tom Hanks, pese a que tiene las cualidades \u201cRico\u201d y \u201cAmericano\u201d tambi\u00e9n, no posee la de \u201cjoven\u201d, por\u00a0 lo que puede estar seguro de que Tom Hanks no es uno de los sospechosos.<\/p>\n

Es as\u00ed como funciona Bloom Filter solo que con muchos m\u00e1s datos. Todo un ej\u00e9rcito de informaci\u00f3n al servicio de los especialistas.<\/p>\n

\"datos\"<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"

Una herramienta que sirve para conocer si un dato se encuentra o no dentro de un conjunto. Bloom Filter funciona con grandes vol\u00famenes de informaci\u00f3n. <\/p>\n","protected":false},"author":4,"featured_media":10697,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[6],"tags":[],"class_list":["post-10696","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-tecnologia"],"_links":{"self":[{"href":"https:\/\/www.psafe.com\/es\/blog\/wp-json\/wp\/v2\/posts\/10696","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.psafe.com\/es\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.psafe.com\/es\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.psafe.com\/es\/blog\/wp-json\/wp\/v2\/users\/4"}],"replies":[{"embeddable":true,"href":"https:\/\/www.psafe.com\/es\/blog\/wp-json\/wp\/v2\/comments?post=10696"}],"version-history":[{"count":0,"href":"https:\/\/www.psafe.com\/es\/blog\/wp-json\/wp\/v2\/posts\/10696\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.psafe.com\/es\/blog\/wp-json\/wp\/v2\/media\/10697"}],"wp:attachment":[{"href":"https:\/\/www.psafe.com\/es\/blog\/wp-json\/wp\/v2\/media?parent=10696"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.psafe.com\/es\/blog\/wp-json\/wp\/v2\/categories?post=10696"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.psafe.com\/es\/blog\/wp-json\/wp\/v2\/tags?post=10696"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}