Problema de conteo distinto

En informática, el problema de conteo de elementos distintos ^{[ 1 ]} (también conocido en matemáticas aplicadas como problema de estimación de cardinalidad ) consiste en encontrar el número de elementos distintos en un flujo de datos con elementos repetidos. Este es un problema bien conocido con numerosas aplicaciones. Los elementos pueden representar direcciones IP de paquetes que pasan por un enrutador , visitantes únicos a un sitio web, elementos en una gran base de datos, motivos en una secuencia de ADN o elementos de redes RFID / sensores .

Instancia : Consideremos una secuencia de elementos.${\displaystyle x_{1},x_{2},\ldots ,x_{s}}$con repeticiones. Deja${\displaystyle n}$denota el número de elementos distintos en el flujo, con el conjunto de elementos distintos representado como${\displaystyle \{e_{1},e_{2},\ldots ,e_{n}\}}$.

Objetivo : Encontrar una estimación${\displaystyle {\widehat {n}}}$de${\displaystyle n}$utilizando únicamente${\displaystyle m}$unidades de almacenamiento, donde${\displaystyle m\ll n}$.

Un ejemplo de instancia para el problema de estimación de cardinalidad es el siguiente flujo:${\displaystyle a,b,a,c,d,b,d}$. Por este caso,${\displaystyle n=|\left\{{a,b,c,d}\right\}|=4}$.

La solución ingenua al problema es la siguiente:

Inicializa un contador, c , a cero,${\displaystyle c\leftarrow 0}$. Inicialice una estructura de datos de diccionario eficiente , D , como una tabla hash o un árbol de búsqueda en la que la inserción y la pertenencia se puedan realizar rápidamente. Para cada elemento${\displaystyle x_{i}}$, se emite una consulta de membresía. Si${\displaystyle x_{i}}$no es miembro de D (${\displaystyle x_{i}\notin D}$) Agregar${\displaystyle x_{i}}$para D Aumentar c en uno,${\displaystyle c\leftarrow c+1}$ De lo contrario (${\displaystyle x_{i}\in D}$) no hacer nada. Salida${\displaystyle n=c}$.

Siempre que el número de elementos distintos no sea demasiado grande, D cabe en la memoria principal y se puede recuperar una respuesta exacta. Sin embargo, este enfoque no es escalable para almacenamiento limitado, o si el cálculo se realiza para cada elemento.${\displaystyle x_{i}}$debe minimizarse. En tal caso, se han propuesto varios algoritmos de transmisión que utilizan un número fijo de unidades de almacenamiento.

Para manejar la restricción de almacenamiento limitado, los algoritmos de transmisión utilizan una aleatorización para producir una estimación no exacta del número distinto de elementos,${\displaystyle n}$Los estimadores de última generación aplican una función hash a cada elemento .${\displaystyle e_{j}}$en un esquema de datos de baja dimensión utilizando una función hash,${\displaystyle h(e_{j})}$Las diferentes técnicas se pueden clasificar según los esquemas de datos que almacenan.

def algorithm_d ( stream , s : int ):p = 1,0búfer = {}para un flujo en :si a en el búfer :buffer.pop ( a )​​u = uniforme ( 0 , 1 )si u < p :si len ( buffer ) < s :buffer [ a ] ​​= udemás :a_p , u_p = max ( buffer.items ( ), key = lambda x : x [ 1 ] )si u > u_p :p = udemás :buffer.pop ( a_p )​​buffer [ a ] ​​= up = u_pdevolver len ( buffer ) / p

Inicializar${\displaystyle p\leftarrow 1}$ Inicializar tamaño máximo del búfer${\displaystyle s}$, dónde${\displaystyle s\geq 1}$ Inicializa un búfer vacío, B Para cada elemento${\displaystyle a_{t}}$en el flujo de datos${\displaystyle A}$de tamaño${\displaystyle n}$hacer: Si${\displaystyle (a_{t},u),\forall u}$Si está en B , entonces eliminar.${\displaystyle (a_{t},u)}$de B${\displaystyle u\leftarrow }$número aleatorio en${\displaystyle [0,1)}$Si${\displaystyle u<p}$entonces si${\displaystyle |B|<s}$luego insertar${\displaystyle (a_{t},u)}$en B demás ${\displaystyle (a',u')}$de tal manera que${\displaystyle u'=\max\{u'':(a'',u'')\in B,\forall a''\}}$/*${\displaystyle (a',u')}$cuyo${\displaystyle u'}$es máximo en B */ Si${\displaystyle u>u'}$entonces ${\displaystyle p\leftarrow u}$ demás Reemplazar${\displaystyle (a',u')}$con${\displaystyle (a_{t},u)}$${\displaystyle p\flecha izquierda u'}$Fin Para regresar${\displaystyle |B|/p}$.

Inicializar${\displaystyle p\leftarrow 1}$ Inicializar tamaño máximo del búfer${\displaystyle s}$, dónde${\displaystyle s\geq 1}$ Inicializa un búfer vacío, B Para cada elemento${\displaystyle a_{t}}$en el flujo de datos${\displaystyle A}$de tamaño${\displaystyle n}$hacer: Si${\displaystyle a_{t}}$Si está en B , entonces eliminar.${\displaystyle a_{t}}$de B${\displaystyle u\leftarrow }$número aleatorio en${\displaystyle [0,1)}$Si${\displaystyle u\leq p}$luego insertar${\displaystyle (a_{t},u)}$en B Mientras${\displaystyle |B|=s\wedge u<p}$Luego, elimine todos los elementos de${\displaystyle (a',u')}$de B con${\displaystyle u'>{\frac {p}{2}}}$${\displaystyle p\leftarrow {\frac {p}{2}}}$Fin Mientras Si${\displaystyle u<p}$entonces Insertar${\displaystyle (a_{t},u)}$en B Fin Para regresar${\displaystyle |B|/p}$.

En su versión ponderada, cada elemento está asociado con un peso y el objetivo es estimar la suma total de pesos. Formalmente,

Instancia : Una secuencia de elementos ponderados${\displaystyle x_{1},x_{2},\ldots ,x_{s}}$con repeticiones y un número entero${\displaystyle m}$. Dejar${\displaystyle n}$sea ​​el número de elementos distintos, a saber:${\displaystyle n=|\left\{{x_{1},x_{2},\ldots ,x_{s}}\right\}|}$y que estos elementos sean${\displaystyle \left\{{e_{1},e_{2},\ldots ,e_{n}}\right\}}$. Finalmente, dejemos${\displaystyle w_{j}}$sea ​​el peso de${\displaystyle e_{j}}$.

Objetivo : Encontrar una estimación${\displaystyle {\widehat {w}}}$de${\displaystyle w=\sum _{j=1}^{n}w_{j}}$utilizando únicamente${\displaystyle m}$unidades de almacenamiento, donde${\displaystyle m\ll n}$.

Un ejemplo de instancia para el problema ponderado es:${\displaystyle a(3),b(4),a(3),c(2),d(3),b(4),d(3)}$. Por este caso,${\displaystyle e_{1}=a,e_{2}=b,e_{3}=c,e_{4}=d}$, los pesos son${\displaystyle w_{1}=3,w_{2}=4,w_{3}=2,w_{4}=3}$y${\displaystyle \sum {w_{j}}=12}$.

Como ejemplo de aplicación,${\displaystyle x_{1},x_{2},\ldots ,x_{s}}$podrían ser paquetes IP recibidos por un servidor. Cada paquete pertenece a uno de${\displaystyle n}$flujos IP${\displaystyle e_{1},e_{2},\ldots ,e_{n}}$El peso${\displaystyle w_{j}}$puede ser la carga impuesta por el flujo${\displaystyle e_{j}}$en el servidor. Por lo tanto,${\displaystyle \sum _{j=1}^{n}{w_{j}}}$representa la carga total impuesta al servidor por todos los flujos a los que se envían paquetes${\displaystyle x_{1},x_{2},\ldots ,x_{s}}$pertenecer.

Cualquier estimador de estadísticas de orden extremo (bocetos min/max) para el problema no ponderado puede generalizarse a un estimador para el problema ponderado. ^{[ 13 ]} Por ejemplo, el estimador ponderado propuesto por Cohen et al. ^{[ 5 ]} se puede obtener cuando el estimador de bocetos máximos continuos se extiende para resolver el problema ponderado. En particular, el algoritmo HyperLogLog ^{[ 6 ]} puede extenderse para resolver el problema ponderado. El algoritmo HyperLogLog extendido ofrece el mejor rendimiento, en términos de precisión estadística y uso de memoria, entre todos los demás algoritmos conocidos para el problema ponderado.

• Boceto de conteo-min
• Algoritmo de transmisión
• Máxima probabilidad
• Estimador insesgado de mínima varianza