En informática , el esquema de conteo mínimo ( esquema de CM ) es una estructura de datos probabilística que sirve como una tabla de frecuencia de eventos en un flujo de datos . Utiliza funciones hash para mapear eventos a frecuencias, pero a diferencia de una tabla hash, usa solo espacio sub-lineal , a expensas de contar en exceso algunos eventos debido a colisiones . El boceto count-min fue inventado en 2003 por Graham Cormode y S. Muthu Muthukrishnan [1] y descrito por ellos en un artículo de 2005. [2]
Los bocetos de conteo mínimo son esencialmente la misma estructura de datos que los filtros de conteo Bloom introducidos en 1998 por Fan et al. [3] Sin embargo, se usan de manera diferente y, por lo tanto, tienen un tamaño diferente: un boceto de conteo mínimo generalmente tiene un número sublineal de celdas, relacionado con la calidad de aproximación deseada del boceto, mientras que un filtro Bloom de conteo generalmente tiene un tamaño que coincide con el número de elementos del conjunto.
Estructura de datos
El objetivo de la versión básica del esquema de conteo mínimo es consumir un flujo de eventos, uno a la vez, y contar la frecuencia de los diferentes tipos de eventos en el flujo. En cualquier momento, se puede consultar el boceto para conocer la frecuencia de un tipo de evento en particular i de un universo de tipos de eventos., y devolverá una estimación de esta frecuencia que se encuentra dentro de una cierta distancia de la frecuencia verdadera, con una cierta probabilidad. [a]
La estructura de datos del boceto real es una matriz bidimensional de w columnas y d filas. Los parámetros W y d son fijos cuando se crea el dibujo, y determinar las necesidades de tiempo y espacio y la probabilidad de error cuando el boceto se consulta para una frecuencia o producto interior . Asociada con cada una de las d filas hay una función hash separada; las funciones hash deben ser independientes por pares . Los parámetros W y d se puede elegir mediante el establecimiento de w = ⌈ e / ε ⌉ y d = ⌈ln 1 / δ ⌉ , donde el error en responder a una consulta está dentro de un factor aditivo de ε con probabilidad 1 - δ (véase a continuación) , ye es el número de Euler .
Cuando llega un nuevo evento de tipo i actualizamos de la siguiente manera: para cada fila j de la tabla, aplicamos la función hash correspondiente para obtener un índice de columna k = h j ( i ) . Luego incremente el valor en la fila j , columna k en uno.
Son posibles varios tipos de consultas en la secuencia.
- La más simple es la consulta de puntos , que solicita el recuento de un evento de tipo i . El recuento estimado viene dado por el valor mínimo en la tabla para i , a saber, dónde es la mesa.
Obviamente, para cada i , uno tiene, dónde es la verdadera frecuencia con la que me encontré en la corriente.
Adicionalmente, este presupuesto tiene la garantía de que con probabilidad , dónde es el tamaño de la secuencia, es decir, el número total de elementos que ve el boceto.
- Una consulta de producto interno solicita el producto interno entre los histogramas representados por dos bocetos de conteo mínimo, y .
Se pueden utilizar pequeñas modificaciones en la estructura de datos para esbozar otras estadísticas de flujo diferentes.
Al igual que el boceto Count , el boceto Count-Min es un boceto lineal. Es decir, dadas dos corrientes, construir un boceto en cada corriente y sumar los bocetos produce el mismo resultado que concatenar las corrientes y construir un boceto en las corrientes concatenados. Esto hace que el boceto se pueda combinar y sea apropiado para su uso en entornos distribuidos además de los de transmisión.
Reducir el sesgo y el error
Un problema potencial con el estimador mínimo habitual para bocetos de conteo mínimo es que son estimadores sesgados de la frecuencia real de eventos: pueden sobreestimar, pero nunca subestimar el conteo real en una consulta puntual. Además, mientras que el estimador mínimo funciona bien cuando la distribución está muy sesgada, otros esquemas como el esquema de Recuento basado en medias son más precisos cuando la distribución no está lo suficientemente sesgada. Se han propuesto varias variaciones del esquema para reducir el error y reducir o eliminar el sesgo. [4]
Para eliminar el sesgo, el estimador hCount * [5] selecciona repetidamente al azar d entradas aleatorias en el esquema y toma el mínimo para obtener una estimación insesgada del sesgo y lo resta.
En Ting se obtuvo un estimador de máxima verosimilitud (MLE). [6] Al utilizar el MLE, el estimador siempre puede igualar o mejorar el estimador mínimo y funciona bien incluso si la distribución no está sesgada. Este documento también mostró que la operación de eliminación de interferencias de hCount * es un procedimiento de arranque que se puede calcular de manera eficiente sin muestreo aleatorio y se puede generalizar a cualquier estimador.
Dado que los errores surgen de colisiones hash con elementos desconocidos del universo, varios enfoques corrigen las colisiones cuando se conocen o se consultan múltiples elementos del universo simultáneamente [7] [8] [6] . Para cada uno de estos, se debe conocer una gran proporción del universo para observar un beneficio significativo.
La actualización conservadora cambia la actualización, pero no los algoritmos de consulta. Para contar c instancias del tipo de evento i , primero se calcula una estimación, luego actualiza para cada fila j . Si bien este procedimiento de actualización hace que el boceto no sea un boceto lineal, aún se puede fusionar.
Ver también
Notas
- ^ La siguiente discusión asume que solo ocurren eventos "positivos", es decir, la frecuencia de los diversos tipos no puede disminuir con el tiempo. Existen modificaciones de los siguientes algoritmos para el caso más general en el que se permite que las frecuencias disminuyan.
Referencias
- ^ Cormode, Graham (2009). "Boceto de conteo mínimo" (PDF) . Enciclopedia de sistemas de bases de datos . Saltador. págs. 511–516.
- ^ Cormode, Graham; S. Muthukrishnan (2005). "Un resumen de flujo de datos mejorado: el bosquejo de Count-Min y sus aplicaciones" (PDF) . J. Algoritmos . 55 : 29–38. doi : 10.1016 / j.jalgor.2003.12.001 .
- ^ Fan, Li; Cao, Pei; Almeida, Jussara; Broder, Andrei (2000), "Summary Cache: A Scalable Wide-Area Web Cache Sharing Protocol", IEEE / ACM Transactions on Networking , 8 (3): 281–293, CiteSeerX 10.1.1.41.1487 , doi : 10.1109 / 90.851975 , S2CID 4779754. Una versión preliminar apareció en SIGCOMM '98.
- ^ Goyal, Amit; Daumé, Hal III; Cormode, Graham (2012). Dibuje algoritmos para estimar consultas puntuales en PNL . Proc. EMNLP / CoNLL.
- ^ Jin, C .; Qian, W .; Xu, X .; Zhou, A. (2003), mantener dinámicamente elementos frecuentes sobre un flujo de datos , CiteSeerX 10.1.1.151.5909
- ^ a b Ting, Daniel (2018). "Count-Min" : 2319–2328. doi : 10.1145 / 3219819.3219975 . Cite journal requiere
|journal=
( ayuda ) - ^ Deng, Fan; Rafiei, Davood (2007), Nuevos algoritmos de estimación para la transmisión de datos: Count-min puede hacer más , CiteSeerX 10.1.1.552.1283
- ^ Lu, Yi; Montanari, Andrea; Prabhakar, Balaji; Dharmapurikar, Sarang; Kabbani, Abdul (2008). "Contra trenzas". Revisión de la evaluación del desempeño de ACM SIGMETRICS . 36 (1): 121-132. doi : 10.1145 / 1384529.1375472 . ISSN 0163-5999 .
Otras lecturas
- Dwork, Cynthia; Naor, Moni; Pitassi, Toniann; Rothblum, Guy N .; Yekhanin, Sergey (2010). Algoritmos de transmisión pan-privada . Proc. ICS. CiteSeerX 10.1.1.165.5923 .
- Schechter, Stuart; Herley, Cormac; Mitzenmacher, Michael (2010). La popularidad lo es todo: un nuevo enfoque para proteger las contraseñas de los ataques de adivinanzas estadísticas . Taller de USENIX sobre temas candentes en seguridad. CiteSeerX 10.1.1.170.9356 .
enlaces externos
- Preguntas frecuentes sobre recuento mínimo