En informática , el esquema de conteo mínimo ( esquema CM ) es una estructura de datos probabilística que sirve como una tabla de frecuencias de eventos en un flujo de datos . Utiliza funciones hash para mapear eventos a frecuencias, pero a diferencia de una tabla hash , utiliza solo espacio sublineal , a expensas de sobrecontar algunos eventos debido a colisiones . El esquema de conteo mínimo fue inventado en 2003 por Graham Cormode y S. Muthu Muthukrishnan [1] y descrito por ellos en un artículo de 2005. [2]
El bosquejo de conteo mínimo es una alternativa al bosquejo de conteo y al bosquejo AMS y puede considerarse una implementación de un filtro Bloom de conteo (Fan et al., 1998 [3] ) o un filtro multietapa. [1] Sin embargo, se usan de manera diferente y, por lo tanto, tienen un tamaño diferente: un bosquejo de conteo mínimo generalmente tiene un número sublineal de celdas, relacionado con la calidad de aproximación deseada del bosquejo, mientras que un filtro Bloom de conteo generalmente tiene un tamaño que coincide con el número de elementos del conjunto.
El objetivo de la versión básica del esquema count–min 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 esquema para conocer la frecuencia de un tipo de evento 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 se fijan cuando se crea el boceto y determinan las necesidades de tiempo y espacio y la probabilidad de error cuando se consulta el boceto para una frecuencia o un producto interno . Asociada a 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 pueden elegir estableciendo w = ⌈ e / ε ⌉ y d = ⌈ln 1/ δ ⌉ , donde el error al responder una consulta está dentro de un factor aditivo de ε con probabilidad 1 − δ (ver a continuación), y e es el número de Euler .
Cuando llega un nuevo evento de tipo i, realizamos la actualización 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, incrementamos el valor en la fila j , columna k en uno.
Son posibles varios tipos de consultas en el stream.
Obviamente, para cada i , uno tiene , donde es la frecuencia real con la que i ocurrió en la corriente.
Además, esta estimación tiene la garantía de que con probabilidad , donde es el tamaño del flujo, es decir, el número total de elementos vistos por el boceto.
Se pueden utilizar pequeñas modificaciones a la estructura de datos para esbozar otras estadísticas de flujo diferentes.
Al igual que el esquema de conteo , el esquema de conteo mínimo es un esquema lineal. Es decir, dadas dos secuencias, construir un esquema en cada secuencia y sumar los esquemas produce el mismo resultado que concatenar las secuencias y construir un esquema en las secuencias concatenadas. Esto hace que el esquema sea fusionable y apropiado para su uso en entornos distribuidos además de en entornos de transmisión.
Un problema potencial con el estimador min habitual para los esquemas de recuento-min es que son estimadores sesgados de la frecuencia real de los eventos: pueden sobreestimar, pero nunca subestimar, el recuento real en una consulta puntual. Además, mientras que el estimador min 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 hCount*estimador [5]
selecciona aleatoriamente repetidamente d entradas aleatorias en el bosquejo y toma el mínimo para obtener una estimación imparcial del sesgo y lo resta.
En Ting se derivó 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 artículo también demostró que la operación de eliminación de sesgo hCount* es un procedimiento de bootstrap que se puede calcular de manera eficiente sin muestreo aleatorio y se puede generalizar a cualquier estimador.
Dado que los errores surgen de colisiones de hash con elementos desconocidos del universo, existen varios enfoques que corrigen las colisiones cuando se conocen o consultan varios 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 y luego se actualiza para cada fila j . Si bien este procedimiento de actualización hace que el boceto no sea lineal, aún se puede fusionar.
![{\displaystyle {\hat {a}}_{i}=\min _{j}\mathrm {cuenta} [j,h_{j}(i)]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/12f24e88e904481b525a7a814a131ae51d838d80)
![{\displaystyle \mathrm {cuenta} [j,h_{j}(i)]\leftarrow \max\{\mathrm {cuenta} [j,h_{j}(i)],{\hat {a_{i}}}+c\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/90d2b8fbfaafb793895ddda34a4a43eee448f9f7)