Introducción a la Estructura de Datos Probabilística

En función de diferentes propiedades, como la velocidad, el costo y la facilidad de uso (como desarrollador), etc., la siguiente información representa diferentes formas de almacenar cosas en la computadora.

Tape------->HDD------->SSD------->Memory

Significa que la memoria es más rápida que SSD que HDD que Tape y lo mismo ocurre con el costo y la facilidad de uso como desarrollador.

El almacenamiento y sus limitaciones.

Ahora analicemos el escenario con el contexto del desarrollador. Si queremos almacenar algunas cosas en la memoria, podemos usar Set (por supuesto, también se puede usar otra estructura de datos en memoria, como Arrays, List, Map, etc.) y si queremos almacenar algunos datos en SSD, entonces podemos use algo como una base de datos relacional o una búsqueda elástica. De manera similar, para un disco duro (HDD) podemos usar Hadoop (HDFS).
Ahora supongamos que queremos almacenar datos en la memoria utilizando una estructura de datos en memoria determinista, pero el problema es que la cantidad de memoria que tenemos en los servidores en términos de GB o TB para la memoria es menor que SSD y SSD puede tener menos memoria que un disco duro (HDD), y también se debe recordar que la estructura de datos deterministas es buena y popular de usar, pero estas estructuras de datos no son eficientes en términos de consumo de memoria.

HDD<-------SSD<-------Memory   //Storage per node

Ahora la pregunta es ¿cómo podemos hacer más cosas en el lado de la memoria, con menos consumo de memoria?

HDD-------SSD-------Memory
                      ^
                      |
              How can we do more stuff here? 

Por lo tanto, este es el lugar donde la estructura de datos probabilísticos entra en escena, que puede hacer casi el mismo trabajo que una estructura de datos deterministas pero con mucha menos memoria.

Estructura de datos determinista vs probabilística

Siendo un profesional de TI, es posible que nos hayamos encontrado con muchas estructuras de datos deterministas como Array, List, Set, HashTable, HashSet, etc. Estas estructuras de datos en memoria son las estructuras de datos más típicas en las que se realizan diversas operaciones, como insertar, buscar y La eliminación se puede realizar con valores clave específicos. Como resultado de la operación lo que obtenemos es el resultado determinista (preciso). Pero esto no es en el caso de una estructura de datos probabilísticos. Aquí el resultado de la operación podría ser probabilístico (puede que no le dé una respuesta definitiva, siempre da como resultado una aproximación), y por lo tanto se denomina estructura de datos probabilísticos. Veremos y probaremos esto en las próximas secciones. Pero por ahora profundicemos en más detalles de su definición, tipos y usos.

¿Como funciona?
La estructura de datos probabilísticos funciona con un gran conjunto de datos, donde queremos realizar algunas operaciones, como encontrar algunos elementos únicos en un conjunto de datos determinado o encontrar el elemento más frecuente o si existen algunos elementos o no. Para realizar una operación de este tipo, la estructura de datos probabilísticos utiliza cada vez más funciones hash para aleatorizar y representar un conjunto de datos.

The more number of hash function the more accurate result. 

Cosas para recordar
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. Como se indicó anteriormente, 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. Además, en el caso de una aplicación de transmisión en la que se requiere que los datos se procesen de una sola vez y se realicen actualizaciones incrementales, es muy difícil de manejar con la estructura de datos determinista.

Casos de uso

1. Analizar grandes conjuntos de datos
2. análisis estadístico
3. Minería de terabytes de conjuntos de datos, etc.

Estructuras de datos probabilísticos populares

1. filtro de floración
2. Croquis de conteo mínimo
3. HyperLogLog