CM sketch permite una respuesta rápida a consultas básicas en el resumen del flujo de datos (como consultas de puntos, rangos y productos internos) y también se puede utilizar para resolver varios problemas importantes en el flujo de datos, como encontrar cuantiles y Artículos públicos.
La resolución de estos problemas utilizando bocetos CM muestra mejoras significativas con respecto a problemas previamente conocidos en el tiempo y el espacio, que a menudo van desde hasta.
Consideramos un vector, que se presenta de forma implícita e incremental. La dimensión de este vector es n, y su estado actual en el momento t es:
Inicialmente, a es un vector cero, todo I.
La actualización de una sola entrada del vector se presenta en forma de flujo, t update es, lo que significa:
El significado general es que solo hay una dimensión en el vector. se modifica y otras dimensiones no se modifican.
En los esquemas de flujo de datos recientes, los algoritmos de cálculo de funciones en el contexto del flujo de datos deben cumplir los siguientes requisitos:
En los últimos años, se han propuesto varios algoritmos diferentes en el contexto del flujo de datos. bocetos, que permiten aproximaciones de muchas funciones de conjuntos simples.
Los bocetos diseñados hasta ahora suelen ser funciones lineales de sus entradas, que pueden expresarse como proyecciones de vectores base, utilizando alguna matriz de proyección elegida aleatoriamente para representar los datos.
Esto significa que algunas funciones se pueden calcular fácilmente a partir de los datos distribuidos en el sitio al convertir estas funciones en cálculos en el boceto. Por tanto, también son adecuados para aplicaciones distribuidas.
Aunque los bocetos han demostrado ser poderosos, tienen las siguientes desventajas:
Dado el hecho de que el campo del flujo de datos está impulsado por aplicaciones de monitoreo de alto rendimiento, como las utilizadas para monitorear los flujos de paquetes IP Los requisitos de tiempo de respuesta de los algoritmos de flujo de datos, estas deficiencias limitan en última instancia el uso de muchos algoritmos de flujo de datos conocidos en aplicaciones apropiadas.
Todos estos problemas los solucionaremos proponiendo una nueva construcción del boceto, al que llamaremos Count-Min o CM Sketch.
Este boceto tiene las siguientes ventajas:
En cualquier momento t, la consulta necesita calcular alguna función específica en a(t):
Estas consultas son Los algoritmos específicos de transmisión de datos son necesarios para muchas aplicaciones y han sido ampliamente estudiados.
Count-Min o CM sketch lleva el nombre de dos operaciones básicas utilizadas para responder consultas puntuales. Cuente primero, luego calcule el valor mínimo. Usamos e para representar la parte inferior de la función logaritmo natural ln.
El boceto Count-Min (CM) con parámetros (ε, δ) se representa mediante una matriz bidimensional Count con ancho w y profundidad d: count [1, 1]... count [d , w].
Luego configuramos los parámetros, así como w y d.
Cada elemento de la matriz comienza con cero. Además, la función hash D H1...HD: {1...n} → {1...w} se selecciona aleatoria y uniformemente de familias independientes por pares.
Cuando llega una actualización, significa que el elemento se actualiza por el número, que luego se suma al recuento de cada fila, y el contador está determinado por.
Configuración formal:
El espacio utilizado en el boceto Count-Min es una matriz ordenada por wd, que requiere palabras wd y una función hash D. Cuando se utilizan las funciones por pares descritas en la Ref., cada función hash se puede almacenar en 2 palabras.