Contando filtros Bloom: introducción e implementación

En este artículo se discutirá la implementación del Counting Bloom Filter. Los siguientes son los temas que se van a tratar.

• ¿Por qué necesitamos estructuras de datos probabilísticos?
• ¿Cuáles son algunas áreas donde se puede aplicar?
• ¿Cuál es el tipo de problema de membresía?
• ¿En qué se diferencia el filtro de floración de conteo del filtro de floración tradicional?
• Introducción a Counting Bloom Filter e Implementación.

¿ Por qué necesitamos estructuras de datos probabilísticos ?

En esta era de Big Data, todas las empresas procesaban una gran cantidad de datos cada día. Por ejemplo, IBM ha declarado que las personas crean 2,5 quintillones de bytes de datos todos los días, este número crece constantemente, por lo que las empresas necesitan alguna técnica para comprender rápidamente los datos para encontrar valor y actuar en consecuencia. Sin embargo, las tecnologías tradicionales que incluyen estructuras de datos y algoritmos, se vuelven ineficaces cuando se trata de Big Data. La mejor solución para este tipo de problema es utilizar Estructuras de Datos Probabilísticas . 

Una estructura de datos determinista también puede realizar todas las operaciones que hace una estructura de datos probabilística, pero solo con conjuntos de datos bajos. Si el conjunto de datos es demasiado grande y no cabe en la memoria, entonces la estructura determinista de datos falla y simplemente no es factible.

PDS (Estructuras de datos probabilísticos) siempre proporciona respuestas aproximadas pero con formas confiables de estimar posibles errores. Afortunadamente, las posibles pérdidas y errores se compensan por completo con requisitos de memoria extremadamente bajos, tiempo de consulta constante y escalado, los factores que se vuelven esenciales en las aplicaciones de Big Data.

¿Cuáles son algunas áreas en las que aplicamos?

Como se mencionó anteriormente, la ventaja de PDS aparece en problemas de Big Data como

• ¿Problema de membresía donde necesitamos encontrar si el elemento particular está presente en los datos o no?
• En problemas como encontrar el número de elementos únicos presentes en los datos.
• Contar la frecuencia de un elemento en particular en los datos completos.

¿Cuál es el tipo de problema de membresía?

Un problema de membresía para un conjunto de datos es una tarea para decidir si algún elemento pertenece al conjunto de datos o no. A diferencia de las estructuras de datos deterministas que encuentran el lugar donde ocurrió la coincidencia exacta. En muchos de los escenarios, no necesitamos saber qué elemento del conjunto se ha emparejado, solo que se ha hecho una coincidencia y, por lo tanto, es posible almacenar solo las firmas de los elementos en lugar del valor total.

¿ En qué se diferencia el filtro Bloom de conteo del filtro Bloom tradicional ?

La principal desventaja del filtro Bloom clásico es que la operación de eliminación no es posible, es decir, solo se puede insertar el elemento y se puede verificar si el elemento está presente en los datos o no. Incluso si alguien intenta cambiar los bits en la array de bits correspondientes a las posiciones k, puede generar falsos negativos. Afortunadamente, la falta de soporte de eliminación no es un problema para muchas aplicaciones del mundo real,

Contando el filtro Bloom y su implementación

La extensión más popular del filtro Bloom clásico que admite la eliminación es el filtro Counting Bloom, propuesto por Li Fan, Pei Cao, Jussara Almeida y Andrei Z. Broder en 2000. El filtro Counting Bloom introduce una array de m contadores {C _j } ^m _j=1 correspondiente a cada bit de la array del filtro. 

El filtro Counting Bloom permite aproximar el número de veces que se ha visto cada elemento en el filtro incrementando el contador correspondiente cada vez que se añade el elemento. La estructura de datos CountingBloomFilter asociada contiene una array de bits y la array de contadores de longitud m, todos inicializados en ceros. Cuando se inserta un nuevo elemento en CountingBloomFilter, primero calcule sus posiciones de bit correspondientes, luego, para cada posición, incrementamos el contador asociado. Estas son algunas ideas básicas para codificar en cualquier idioma preferido.

Pseudocódigo: 

Entrada: El elemento x pertenece a D
Entrada: Filtro de conteo Bloom con m contadores {C _j } _j=1 ^m y k funciones hash {h _i } _i=1 ^k  
Algo:

para i=1 a k hacer

    j=h _yo (x)

   Cj = _Cj +1 _{_}

A continuación, para probar si un elemento está presente o no, verificamos los contadores correspondientes a k posiciones si el valor de todos los contadores es mayor que 0 implica que el elemento probablemente esté presente.

Entrada: El elemento x pertenece a D
Entrada: Contador Filtro Bloom con m contadores y k funciones hash.
algo:

para i=1 a k hacer

   j=h _yo (x)

  si CountingBloomFilter[j]<1 entonces 

      falso retorno

volver verdadero

Ahora, finalmente, la parte importante de la eliminación. La eliminación es bastante similar a la inserción pero a la inversa. Para eliminar un elemento x , calculamos todos los k valores hash h _i = {h _i (x )} ^k _i=1 y disminuimos los contadores correspondientes. 

A continuación se muestra la implementación del algoritmo anterior.

import math
from fnvhash import fnv1a_32
from bitarray import bitarray
from bitarray.util import ba2int,int2ba
 
class CBloomFilter():
    def __init__(self, n,Counter_size,bucket_size,no_hashfn):
 
        self.n=n
        self.N=Counter_size
        self.m=bucket_size
        self.k=no_hashfn
 
        self.bit_array = []
        for i in range(self.m):
            count=bitarray(self.N)
            count.setall(0)
            self.bit_array.append(count)
 
    def hash(self,item,seed):
        return fnv1a_32(item.encode(),seed) % self.m
 
    def add(self, item):
 
        for i in range(self.k):
            index = self.hash(item,i)
 
            cur_val=ba2int(self.bit_array[index])
            new_array=int2ba(cur_val+1,length=self.N)
             
            self.bit_array[index]=new_array
    def check(self, item):
        for i in range(self.k):
            index = self.hash(item,i)
            cur_val=ba2int(self.bit_array[index])
 
            if(not cur_val>0):
                return False
        return True
       
    def remove(self,item):
        if(self.check(item)):
            for i in range(self.k):
                index = self.hash(item,i)
                 
                cur_val=ba2int(self.bit_array[index])
                new_array=int2ba(cur_val-1,length=self.N)
                self.bit_array[index]=new_array
 
            print('Element Removed')
        else:
            print('Element is probably not exist')

En el código anterior para el hash de los elementos, se usa la función hash FNV (también puede usar la función hash de murmullo), que se usa ampliamente en estructuras de datos probabilísticos. n es el número esperado de elementos que va a ingresar en el filtro. Counter_size es el número de bits para cada contador en el depósito. bucket_size es el número m de cubos que vamos a usar en el filtro y, finalmente, el no_hashfn es k el número de funciones hash que vamos a usar. 

Ahora pruebe la clase con algunos ejemplos, guarde el archivo como counting_bloom_filter.py y ahora cree otro archivo para probar.

from counting_bloom_filter import CBloomFilter
from random import shuffle
 
n = 20  # no of items to add
N = 4  # size of the each counter
m = 150  # total number of the buckets
k = 5  # number of hash functions
 
cbloomf = CBloomFilter(n, N, m, k)
print("Size of bit array:{}".format(cbloomf.m))
print("Size of each bucket:{}".format(cbloomf.N))
print("Number of hash functions:{}".format(cbloomf.k))
 
# words to be added
word_present = ['abound', 'abounds', 'abundance',
                'abundant', 'accessible',
                'bloom', 'blossom', 'bolster', 'bonny',
                'bonus', 'bonuses',
                'coherent', 'cohesive', 'colorful',
                'comely', 'comfort',
                'gems', 'generosity', 'generous',
                'generously', 'genial']
 
# word not added
word_absent = ['bluff', 'cheater', 'hate',
               'war', 'humanity',
               'racism', 'hurt', 'nuke',
               'gloomy', 'facebook',
               'geeksforgeeks', 'twitter']
 
for item in word_present:
    cbloomf.add(item)
 
shuffle(word_present)
shuffle(word_absent)
 
test_words = word_present[:10] + word_absent
shuffle(test_words)
for word in test_words:
    if cbloomf.check(word):
        if word in word_absent:
            print("'{}' is a false positive!".format(word))
        else:
            print("'{}' is probably present!".format(word))
    else:
        print("'{}' is definitely not present!".format(word))

Producción:

Propiedades:

El filtro Counting Bloom hereda todas las propiedades del filtro Bloom clásico, incluida la estimación de errores de falsos positivos y recomendaciones para la elección óptima de m y k refer .