algorithm - tries - ¿Qué son las estructuras de datos probabilísticas?

tries rugby

Question

He leído acerca de las estructuras de datos como los filtros bloom y las listas de salto.

¿Cuáles son las características comunes de las estructuras de datos probabilísticas y para qué se utilizan?

Answer 1

Hay una lista de estructuras de datos probabilísticas en wikipedia para su referencia: https://en.wikipedia.org/wiki/Category:Probabilistic_data_structures

Existen diferentes definiciones sobre qué es la "estructura de datos probabilística". En mi humilde opinión, la estructura de datos probabilística significa que la estructura de datos utiliza algún algoritmo aleatorio o aprovecha algunas características probabilísticas internamente, pero no tiene que comportarse de forma probabilística o no determinista desde la perspectiva del usuario de la estructura de datos.

• Hay muchas "estructuras de datos probabilísticas" con un comportamiento probabilístico como el filtro bloom y el HyperLogLog mencionados en las otras respuestas.

• Al mismo tiempo, hay otras "estructuras de datos probabilísticas" con un comportamiento determinado (desde la perspectiva del usuario), como la lista de omisión . Para la lista de omisiones, los usuarios pueden usarlo de manera similar como un árbol de búsqueda binaria equilibrada, pero se implementa internamente con alguna idea relacionada con la probabilidad. Y de acuerdo con el autor de la lista de omitir William Pugh:

  Las listas de omisiones son una estructura de datos probabilística que parece suplantar a los árboles equilibrados como el método de implementación elegido para muchas aplicaciones. Los algoritmos de lista de salto tienen los mismos límites de tiempo esperados asintóticos que los árboles equilibrados y son más simples, más rápidos y usan menos espacio.

Answer 2

Probablemente hay muchas respuestas diferentes (y buenas), pero en mi opinión humilde, las características comunes de las estructuras de datos probabilísticas es que le proporcionan una respuesta aproximada, no precisa.

¿Cuántos artículos hay aquí? Alrededor de 1523425 con probabilidad del 99%.

Actualización: La búsqueda rápida produjo un enlace a un artículo decente sobre el tema:

https://highlyscalable.wordpress.com/2012/05/01/probabilistic-structures-web-analytics-data-mining/

Answer 3

Si está interesado en estructuras de datos probabilísticos, puede leer mi libro recientemente publicado " Estructuras de datos probabilísticos y algoritmos para aplicaciones de datos grandes " (ISBN: 9783748190486, disponible en Amazon), donde he explicado muchas de estas estructuras de datos eficientes en el espacio. y algoritmos rápidos que son extremadamente útiles en las aplicaciones modernas de Big Data.

En este libro, puede encontrar los algoritmos y las estructuras de datos más avanzados que ayudan a manejar problemas tan comunes en el procesamiento de Big Data como

• Consulta de membresía (filtro Bloom, filtro Bloom contando, filtro de cociente, filtro de cuco).
• Cardinalidad (conteo lineal, conteo probabilístico, LogLog, HyperLogLog, HyperLogLog ++).
• Frecuencia (algoritmo mayoritario, frecuente, croquis de cuenta, croquis de cuenta mínima).
• Rango (muestreo aleatorio, q-digest, t-digest).
• Similitud (LSH, MinHash, SimHash).

Puede obtener una vista previa gratuita y toda la información relacionada con el libro en https://pdsa.gakhov.com

Answer 4

Las estructuras de datos probabilísticas no pueden darle una respuesta definitiva, en lugar de eso, le brindan una aproximación razonable de la respuesta y una manera de aproximar esta estimación. Son extremadamente útiles para aplicaciones de transmisión de datos grandes y datos grandes, ya que permiten disminuir drásticamente la cantidad de memoria necesaria (en comparación con las estructuras de datos que le dan respuestas exactas).

En la mayoría de los casos, estas estructuras de datos utilizan funciones hash para aleatorizar los elementos. Debido a que ignoran las colisiones, mantienen el tamaño constante, pero esta es también una razón por la que no pueden darle valores exactos. Las ventajas que aportan:

• Usan una pequeña cantidad de memoria (puedes controlar cuánto)
• Pueden ser fácilmente paralelizables (los hashes son independientes)
• tienen un tiempo de consulta constante (ni siquiera una constante amortizada como en el diccionario)

Las estructuras de datos probabilísticas más utilizadas son:

• filtros de floración
• croquis de cuenta-min
• hyperLogLog