Acerca de las estructuras de datos Bloom filters.

Buenas, vamos a hablar un poquito acerca de esta interesante estructura de datos que te puede servir como una caché rápida, más rápida que una estructura hash, pues tiene una complejidad logarítmica de O(Log(n)), donde n son los elementos que te cabrán en esta estructura.

A saco, primero muestro una par de implementaciones un tanto naive, primero en Java, luego en python:

import java.util.BitSet;

public class BloomFilter {
private int m;
private int k;
private BitSet bitset;

public BloomFilter(int m, int k) {
    this.m = m;
    this.k = k;
    this.bitset = new BitSet(m);
}

public void add(String word) {
    for (int i = 0; i < k; i++) {
        int hash = hash(word, i);
        bitset.set(hash % m);
    }
}

public boolean contains(String word) {
    for (int i = 0; i < k; i++) {
        int hash = hash(word, i);
        if (!bitset.get(hash % m)) {
            return false;
        }
    }
    return true;
}

private int hash(String word, int i) {
    int hash = 0;
    for (int j = 0; j < word.length(); j++) {
        hash = hash * 31 + word.charAt(j);
    }
    return hash;
}

public static void main(String[] args) {
    BloomFilter bloomFilter = new BloomFilter(10000, 5);
    bloomFilter.add("hola");
    bloomFilter.add("mundo");

    System.out.println(bloomFilter.contains("hola")); // true
    System.out.println(bloomFilter.contains("mundo")); // true
    System.out.println(bloomFilter.contains("adios")); // false
}

}

Este código crea un Bloom Filter con 10000 bits y 5 hash funciones. Luego, agrega las palabras «hola» y «mundo» al filtro. Finalmente, verifica si el filtro contiene las palabras «hola», «mundo» y «adios».

Aquí tienes un ejemplo de cómo usar un Bloom Filter en Python:

import random

class BloomFilter:
def __init__(self, m, k):
    self.m = m
    self.k = k
    self.bitset = set()

def add(self, word):
    for i in range(self.k):
        hash = random.randint(0, self.m)
        self.bitset.add(hash)

def contains(self, word):
    for i in range(self.k):
        hash = random.randint(0, self.m)
        if hash not in self.bitset:
            return False
    return True

def main():
bloom_filter = BloomFilter(10000, 5)
bloom_filter.add(«hola»)
bloom_filter.add(«mundo»)

print(bloom_filter.contains("hola"))  # True
print(bloom_filter.contains("mundo"))  # True
print(bloom_filter.contains("adios"))  # False

if name == «main«:
main()

Este código crea un Bloom Filter con 10000 bits y 5 hash funciones. Luego, agrega las palabras «hola» y «mundo» al filtro. Finalmente, verifica si el filtro contiene las palabras «hola», «mundo» y «adios».

En ambos ejemplos, el Bloom Filter se usa para comprobar si una palabra está presente en un conjunto de datos. El Bloom Filter es una estructura de datos probabilística, lo que significa que puede producir falsos positivos. En este caso, un falso positivo ocurre cuando el Bloom Filter indica que una palabra está presente en el conjunto de datos cuando en realidad no lo está.

La probabilidad de un falso positivo depende de la cantidad de bits en el Bloom Filter y de la cantidad de hash funciones que se usan. En general, cuanto más bits tenga el Bloom Filter y cuanto más hash funciones se usen, menor será la probabilidad de un falso positivo.

Luego al final te explico como tratar de minimizar al máximo esta probabilidad de que aparezca un falso positivo.

Pregunta:

cuales son las ventajas de uso de un Bloom filter con respecto a otras estructuras de datos?

Respuesta:

Las ventajas de usar un Bloom Filter con otras estructuras de datos incluyen:

• Eficiencia: Los Bloom Filters son estructuras de datos muy eficientes, tanto en términos de espacio como de tiempo. Ocupan solo una pequeña cantidad de espacio, lo que los hace ideales para aplicaciones con limitaciones de espacio. Además, las operaciones de consulta y adición son muy rápidas.
• Flexibilidad: Los Bloom Filters se pueden usar en una amplia variedad de aplicaciones. Son útiles para aplicaciones que requieren comprobar si un elemento está presente en un conjunto de datos, como filtros de spam, motores de búsqueda y sistemas de recomendación.
• Facilidad de implementación: Los Bloom Filters son relativamente fáciles de implementar. Hay muchas bibliotecas disponibles para diferentes lenguajes de programación.

En comparación con otras estructuras de datos, los Bloom Filters ofrecen las siguientes ventajas:

• Los conjuntos disjuntos: Los conjuntos disjuntos son estructuras de datos que almacenan un conjunto de elementos únicos. Los Bloom Filters son más eficientes que los conjuntos disjuntos en términos de espacio, ya que no necesitan almacenar información sobre la cardinalidad del conjunto.
• Los árboles de búsqueda: Los árboles de búsqueda son estructuras de datos que permiten buscar elementos de manera eficiente. Los Bloom Filters son más eficientes que los árboles de búsqueda en términos de tiempo, ya que no necesitan realizar una búsqueda completa del árbol.

Sin embargo, los Bloom Filters también tienen algunas desventajas, que incluyen:

• Falsos positivos: Los Bloom Filters pueden producir falsos positivos. Un falso positivo ocurre cuando el Bloom Filter indica que un elemento está presente en el conjunto cuando en realidad no lo está. La probabilidad de un falso positivo depende de la cantidad de bits en el Bloom Filter y de la cantidad de hash funciones que se usan.
• Especificidad: Los Bloom Filters no proporcionan información sobre la posición del elemento en el conjunto. Por lo tanto, si el Bloom Filter indica que un elemento está presente en el conjunto, no se puede determinar su posición exacta.

En general, los Bloom Filters son una buena opción para aplicaciones que requieren comprobar si un elemento está presente en un conjunto de datos. Son eficientes, flexibles y fáciles de implementar. Sin embargo, es importante tener en cuenta las desventajas de los Bloom Filters, como la posibilidad de falsos positivos y la falta de especificidad.

Pregunta:

como se pueden minimizar al máximo dichas desventajas?

Respuesta:

La probabilidad de falsos positivos en un Bloom Filter se puede minimizar aumentando la cantidad de bits en el Bloom Filter y la cantidad de hash funciones que se usan. En general, cuanto más bits tenga el Bloom Filter y cuanto más hash funciones se usen, menor será la probabilidad de un falso positivo.

Por ejemplo, si un Bloom Filter tiene 10000 bits y 5 hash funciones, la probabilidad de un falso positivo es aproximadamente del 1%. Si el Bloom Filter tiene 1000000 bits y 10 hash funciones, la probabilidad de un falso positivo es aproximadamente del 0,01%.

Sin embargo, aumentar la cantidad de bits y hash funciones también aumenta el tamaño del Bloom Filter. Por lo tanto, es importante encontrar un equilibrio entre la probabilidad de falsos positivos y el tamaño del Bloom Filter.

La falta de especificidad de los Bloom Filters se puede minimizar usando una estructura de datos adicional para almacenar información sobre la posición del elemento en el conjunto. Por ejemplo, se podría usar un árbol binario para almacenar la información de posición.

En este caso, el Bloom Filter se usaría para determinar si un elemento está presente en el conjunto. Si el Bloom Filter indica que el elemento está presente, se usaría el árbol binario para determinar su posición exacta.

Esta solución es más eficiente que usar un Bloom Filter sin información de posición. Sin embargo, también requiere más espacio, ya que es necesario almacenar la información de posición en el árbol binario.

En general, la mejor manera de minimizar las desventajas de los Bloom Filters depende de las necesidades específicas de la aplicación.

Pregunta:

no me queda claro cuantos elementos pueden almacenar este tipo de estructuras, para empezar, es una estructura dinámica? cual es la complejidad logarítimica?

Respuesta:

Los Bloom Filters pueden almacenar una cantidad ilimitada de elementos. La cantidad de elementos que se pueden almacenar en un Bloom Filter depende de la cantidad de bits que tenga el Bloom Filter y de la cantidad de hash funciones que se usen.

En general, cuanto más bits tenga el Bloom Filter y cuanto más hash funciones se usen, más elementos se pueden almacenar.

Sin embargo, es importante tener en cuenta que la probabilidad de falsos positivos aumenta a medida que aumenta la cantidad de elementos que se almacenan en un Bloom Filter.

Por ejemplo, si un Bloom Filter tiene 10000 bits y 5 hash funciones, puede almacenar aproximadamente 100000 elementos sin que la probabilidad de falsos positivos sea mayor del 1%. Si el Bloom Filter tiene 1000000 bits y 10 hash funciones, puede almacenar aproximadamente 10000000 elementos sin que la probabilidad de falsos positivos sea mayor del 1%.

En cuanto a la complejidad logarítimica, las operaciones de consulta y adición en un Bloom Filter tienen una complejidad de O(log(n)), donde n es la cantidad de bits en el Bloom Filter.

Esto significa que el tiempo necesario para realizar una consulta o adición en un Bloom Filter es proporcional al logaritmo de la cantidad de bits en el Bloom Filter.

En general, los Bloom Filters son estructuras de datos dinámicas, ya que se pueden agregar y eliminar elementos sin necesidad de reestructurar el Bloom Filter.

Sin embargo, es importante tener en cuenta que la probabilidad de falsos positivos aumenta a medida que se agregan y eliminan elementos de un Bloom Filter.

En principio diría que estas estructuras, aunque sean dinámicas por naturaleza, si queremos todas sus ventajas, complejidad logarítmica en sus operaciones y nada de sus desventajas, aparición de falsos positivos, tenemos que procurar ceñirnos al número de elementos que hemos calculado para que no aparezcan.

Pregunta:

cuales son las ventajas con respecto a una tabla hash?

Respuesta:

Las ventajas de los Bloom Filters con respecto a las tablas hash incluyen:

• Eficiencia: Los Bloom Filters son más eficientes en términos de espacio que las tablas hash. Esto se debe a que los Bloom Filters no necesitan almacenar información sobre la cardinalidad del conjunto.
• Rapidez: Las operaciones de consulta y adición en los Bloom Filters son más rápidas que las operaciones de consulta y adición en las tablas hash. Esto se debe a que los Bloom Filters no necesitan realizar una búsqueda completa de la tabla.
• Flexibilidad: Los Bloom Filters se pueden usar en una amplia variedad de aplicaciones, mientras que las tablas hash se usan principalmente para almacenar y recuperar datos.

Las desventajas de los Bloom Filters con respecto a las tablas hash incluyen:

• Falsos positivos: Los Bloom Filters pueden producir falsos positivos. Un falso positivo ocurre cuando el Bloom Filter indica que un elemento está presente en el conjunto cuando en realidad no lo está.
• Especificidad: Los Bloom Filters no proporcionan información sobre la posición del elemento en el conjunto.

En general, los Bloom Filters son una buena opción para aplicaciones que requieren comprobar si un elemento está presente en un conjunto de datos. Son eficientes, rápidos y flexibles. Sin embargo, es importante tener en cuenta las desventajas de los Bloom Filters, como la posibilidad de falsos positivos y la falta de especificidad.

A continuación se presentan algunos ejemplos específicos de las ventajas de los Bloom Filters sobre las tablas hash:

• Filtros de spam: Los Bloom Filters se pueden usar para identificar correos electrónicos no deseados. Los correos electrónicos no deseados se pueden agregar al Bloom Filter y luego se puede usar el Bloom Filter para comprobar si un correo electrónico entrante es no deseado.
• Motores de búsqueda: Los Bloom Filters se pueden usar para almacenar índices de búsqueda. Los términos de búsqueda se pueden agregar al Bloom Filter y luego se puede usar el Bloom Filter para comprobar si un documento contiene un término de búsqueda específico.
• Sistemas de recomendación: Los Bloom Filters se pueden usar para almacenar preferencias de usuarios. Las preferencias de los usuarios se pueden agregar al Bloom Filter y luego se puede usar el Bloom Filter para recomendar productos o servicios a los usuarios.

En estas aplicaciones, las ventajas de los Bloom Filters en términos de eficiencia y rapidez superan las desventajas de los falsos positivos y la falta de especificidad.

Pregunta:

en el caso del JDK, porque no está presente como estructura de datos oficial?

El JDK no incluye los Bloom Filters como una estructura de datos oficial por varias razones, que incluyen:

• Los Bloom Filters son una estructura de datos probabilística, lo que significa que pueden producir falsos positivos. Los falsos positivos son un problema importante para algunas aplicaciones, como las bases de datos, donde la precisión es fundamental.
• Los Bloom Filters no proporcionan información sobre la posición del elemento en el conjunto. Esto puede ser un inconveniente para algunas aplicaciones, como las que requieren acceder a los elementos del conjunto en un orden específico.
• Los Bloom Filters no son adecuados para todas las aplicaciones. Los Bloom Filters son una buena opción para aplicaciones que requieren comprobar si un elemento está presente en un conjunto de datos, pero no son la mejor opción para todas las aplicaciones.

En general, el JDK se centra en proporcionar estructuras de datos que sean precisas, eficientes y adecuadas para una amplia gama de aplicaciones. Los Bloom Filters no cumplen con todos estos criterios, por lo que no se incluyen como una estructura de datos oficial del JDK.

Sin embargo, existen bibliotecas de terceros que proporcionan implementaciones de Bloom Filters para Java. Estas bibliotecas pueden ser una buena opción para aplicaciones que requieren las ventajas de los Bloom Filters, pero están dispuestas a aceptar los riesgos de los falsos positivos y la falta de especificidad.

A continuación se presentan algunas bibliotecas de terceros que proporcionan implementaciones de Bloom Filters para Java:

• Guava: La biblioteca Guava de Google incluye una implementación de Bloom Filter en su paquete com.google.common.hash.
• Apache Commons: La biblioteca Apache Commons Lang incluye una implementación de Bloom Filter en su paquete org.apache.commons.collections4.bloomfilter.
• Apache Spark: El marco de trabajo Apache Spark incluye una implementación de Bloom Filter en su paquete org.apache.spark.util.bloomfilter.

Estas bibliotecas proporcionan diferentes características y opciones de configuración, por lo que es importante elegir la biblioteca que mejor se adapte a las necesidades específicas de la aplicación.

Ejemplos de uso de dichas librerías:

Guava

import com.google.common.hash.BloomFilter;

public class GuavaBloomFilterExample {

    public static void main(String[] args) {
        // Crea un Bloom Filter con 10000 bits y 5 hash funciones
        BloomFilter<Integer> bloomFilter = BloomFilter.create(10000, 0.01);

        // Agrega algunos elementos al Bloom Filter
        bloomFilter.put(1);
        bloomFilter.put(2);
        bloomFilter.put(3);

        // Comprueba si un elemento está presente en el Bloom Filter
        System.out.println(bloomFilter.mightContain(1)); // true
        System.out.println(bloomFilter.mightContain(4)); // false
    }
}

Este ejemplo crea un Bloom Filter con 10000 bits y 5 hash funciones. Luego, agrega tres elementos al Bloom Filter: 1, 2 y 3. Finalmente, comprueba si los elementos 1 y 4 están presentes en el Bloom Filter. La salida del ejemplo es la siguiente:

true
false

Apache Commons

import org.apache.commons.collections4.bloomfilter.BloomFilter;

public class ApacheCommonsBloomFilterExample {

    public static void main(String[] args) {
        // Crea un Bloom Filter con 10000 bits y 5 hash funciones
        BloomFilter<Integer> bloomFilter = new BloomFilter<>(10000, 0.01);

        // Agrega algunos elementos al Bloom Filter
        bloomFilter.add(1);
        bloomFilter.add(2);
        bloomFilter.add(3);

        // Comprueba si un elemento está presente en el Bloom Filter
        System.out.println(bloomFilter.contains(1)); // true
        System.out.println(bloomFilter.contains(4)); // false
    }
}

Este ejemplo es similar al ejemplo de Guava. Crea un Bloom Filter con 10000 bits y 5 hash funciones. Luego, agrega tres elementos al Bloom Filter: 1, 2 y 3. Finalmente, comprueba si los elementos 1 y 4 están presentes en el Bloom Filter. La salida del ejemplo es la misma que la del ejemplo de Guava.

Apache Spark

import org.apache.spark.util.bloomfilter.BloomFilter

object ApacheSparkBloomFilterExample {

  def main(args: Array[String]): Unit = {
    // Crea un Bloom Filter con 10000 bits y 5 hash funciones
    val bloomFilter = new BloomFilter(10000, 0.01)

    // Agrega algunos elementos al Bloom Filter
    bloomFilter.add(1)
    bloomFilter.add(2)
    bloomFilter.add(3)

    // Comprueba si un elemento está presente en el Bloom Filter
    println(bloomFilter.contains(1)) // true
    println(bloomFilter.contains(4)) // false
  }
}

Este ejemplo es similar a los ejemplos de Guava y Apache Commons. Crea un Bloom Filter con 10000 bits y 5 hash funciones. Luego, agrega tres elementos al Bloom Filter: 1, 2 y 3. Finalmente, comprueba si los elementos 1 y 4 están presentes en el Bloom Filter. La salida del ejemplo es la misma que la de los ejemplos de Guava y Apache Commons.

Esta librería es muy interesante que esté presente con Spark, porque dicha estructura adquiere la capacidad de ser distribuida, si por ejemplo hacemos broadcast de ella para que esté disponible entre todos los nodos workers y el driver del cluster Spark.

pregunta:

Bien puedes indicar en el constructor el número de funciones hash, en este caso a través de un entero positivo, 5, o bien se puede usar en el constructor un número flotante positivo, 0.01 que indica la probabilidad de que aparezcan los falsos positivos. Por ejemplo, con esta instrucción, BloomFilter bloomFilter = new BloomFilter<>(10000, 5); estoy inicializando una estructura BloomFilter para almacenar hasta 10000 elementos con una probabilidad del 0.01 que aparezcan falsos positivos en caso de que por ejemplo añada más de 10000 elementos?

Con la instrucción BloomFilter bloomFilter = new BloomFilter<>(10000, 5);, estás inicializando una estructura BloomFilter para almacenar hasta 10000 elementos con una probabilidad del 0.01 que aparezcan falsos positivos en caso de que por ejemplo añada más de 10000 elementos.

En general, la cantidad de bits que tiene un Bloom Filter determina la capacidad del Bloom Filter, es decir, la cantidad de elementos que se pueden almacenar sin que la probabilidad de falsos positivos sea demasiado alta.

La cantidad de funciones hash determina la probabilidad de falsos positivos. En general, cuanto más funciones hash se usen, menor será la probabilidad de falsos positivos.

En el caso de la instrucción que has proporcionado, la cantidad de bits es 10000, que determina la capacidad del Bloom Filter. La cantidad de funciones hash es 5, que determina la probabilidad de falsos positivos.

Por lo tanto, con esta instrucción, estás inicializando un Bloom Filter con capacidad para almacenar hasta 10000 elementos y una probabilidad de falsos positivos del 0.01.

Si intentas añadir más de 10000 elementos al Bloom Filter, se producirán falsos positivos. La probabilidad de falsos positivos aumentará cuanto más elementos se añadan al Bloom Filter.

Es importante elegir la cantidad de bits y la cantidad de funciones hash en función de las necesidades específicas de la aplicación. Si se requiere una precisión muy alta, se pueden usar más bits y más funciones hash. Sin embargo, esto puede aumentar el tamaño del Bloom Filter y reducir su eficiencia.

Pregunta:

Imagina que quiero almacenar hasta 10000 elementos y quiero una probabilidad menor del 0.0001% de falsos positivos si me mantento en ese número de elementos, incluso tengo menos, como debería inicializarlo?

Respuesta:

Para almacenar hasta 10000 elementos con una probabilidad menor del 0.0001% de falsos positivos, se necesitan al menos 24000 bits. Esto se puede calcular utilizando la siguiente fórmula:

n = m * ln(2) * (1 - (1 - p)^k)

donde:

• n es la cantidad de bits necesaria
• m es la cantidad de elementos que se van a almacenar
• p es la probabilidad de falsos positivos
• k es la cantidad de funciones hash que se van a usar

En este caso, m = 10000, p = 0.0001 y k = 5. Por lo tanto, la fórmula se reduce a:

n = 10000 * ln(2) * (1 - (1 - 0.0001)^5)

n = 24000

Por lo tanto, se necesita un Bloom Filter con al menos 24000 bits para almacenar hasta 10000 elementos con una probabilidad menor del 0.0001% de falsos positivos.

Para inicializar un Bloom Filter con 24000 bits y 5 funciones hash, se puede usar el siguiente código:

BloomFilter<Integer> bloomFilter = new BloomFilter<>(24000, 5);

Este código inicializará un Bloom Filter con 24000 bits y 5 funciones hash. Este Bloom Filter tendrá capacidad para almacenar hasta 10000 elementos con una probabilidad menor del 0.0001% de falsos positivos.

Es importante tener en cuenta que esta es solo una aproximación. La probabilidad real de falsos positivos puede variar ligeramente, dependiendo de la implementación específica del Bloom Filter, es decir, hay que probar y testear como se van a comportar nuestras estructruras de datos y algoritmos.

Por si no ha quedado muy claro, recuerdan los atributos privados en la implementacion java?

private int m;
private int k;
private BitSet bitset;

Los atributos internos m, k y bitset se utilizan para almacenar la información del Bloom Filter.

• m es la cantidad de bits que tiene el Bloom Filter.
• k es la cantidad de funciones hash que se usan en el Bloom Filter.
• bitset es una estructura de datos que almacena los bits del Bloom Filter.

m se utiliza para calcular la probabilidad de falsos positivos.
La fórmula para calcular la probabilidad de falsos positivos es la siguiente:

p = 1 - (1 - (1 / 2^m)^k)^m

donde:

• p es la probabilidad de falsos positivos
• m es la cantidad de bits del Bloom Filter
• k es la cantidad de funciones hash que se usan

Por lo tanto, un Bloom Filter con m bits y k funciones hash tendrá una probabilidad de falsos positivos de p.

k se utiliza para reducir la probabilidad de falsos positivos.
En general, cuanto más funciones hash se usen, menor será la probabilidad de falsos positivos.
Sin embargo, también aumentará el tamaño del Bloom Filter.

bitset se utiliza para almacenar los bits del Bloom Filter.
Los bits del Bloom Filter se utilizan para indicar si un elemento está presente o no en el conjunto.

Por ejemplo, si un Bloom Filter tiene m bits y k funciones hash, y un elemento se agrega al Bloom Filter, entonces se establecerán k bits del bitset. Si se comprueba si el elemento está presente en el Bloom Filter, y todos los k bits del bitset están establecidos, entonces se puede decir con seguridad que el elemento está presente en el conjunto. Sin embargo, si alguno de los k bits del bitset no está establecido, entonces es posible que el elemento no esté presente en el conjunto.

Sin más, hasta la próxima.