En informática , el croquis de recuento mínimo ( croquis CM ) es una estructura de datos probabilística que sirve como tabla de frecuencia de eventos en un flujo de datos . Utiliza funciones hash para asignar eventos a frecuencias, pero a diferencia de una tabla hash usa solo espacio sublineal , a expensas de contar en exceso algunos eventos debido a colisiones . El boceto 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 boceto de conteo mínimo es una alternativa al boceto de conteo y al boceto de AMS y puede considerarse una implementación de un filtro Bloom de conteo (Fan et al., 1998 [3] ) o un filtro de etapas múltiples. [1] 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.
El objetivo de la versión básica del boceto 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 particular i de un universo de tipos de eventos y devolverá una estimación de esta frecuencia que está dentro de una cierta distancia de la frecuencia real, 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 producto interno . 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 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 más abajo) y e 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 transmisión.
Obviamente, para cada i , se tiene , ¿dónde está la frecuencia real con la que i ocurrió en la corriente?
Además, esta estimación tiene la garantía de que con probabilidad , ¿dónde está el tamaño de la corriente, es decir, el número total de elementos vistos en el boceto?
Se pueden utilizar pequeñas modificaciones en la estructura de datos para esbozar otras estadísticas de flujo diferentes.
Al igual que el boceto de recuento , el boceto de recuento mínimo es un boceto lineal. Es decir, dadas dos secuencias, construir un boceto en cada secuencia y sumar los bocetos produce el mismo resultado que concatenar las secuencias y construir un boceto sobre las secuencias concatenadas. Esto hace que el boceto sea fusionable y apropiado para su uso en entornos distribuidos además de los de transmisión.
Un problema potencial con el estimador mínimo habitual para los 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, si bien el estimador mínimo funciona bien cuando la distribución es muy asimétrica, otros bocetos, como el boceto de recuento basado en medias, son más precisos cuando la distribución no está lo suficientemente sesgada. Se han propuesto varias variaciones del boceto para reducir el error y reducir o eliminar el sesgo. [4]
Para eliminar el sesgo, el hCount*estimador [5]
selecciona repetidamente al azar d entradas aleatorias en el boceto y toma el mínimo para obtener una estimación insesgada 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 mostró que la operación de eliminación de sesgo 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 ellos, 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 {count} [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)