Problema de recuento distinto

Aritmética matemática

En informática, el problema de recuento de elementos distintos ^[1] (también conocido en matemáticas aplicadas como el problema de estimación de cardinalidad ) es el problema de 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 a través de 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 .

Definición formal

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

Objetivo : Encontrar una estimación del uso de solo unidades de almacenamiento, donde . ${\displaystyle {\widehat {n}}}$ ${\displaystyle n}$ ${\displaystyle m}$ ${\displaystyle m\ll n}$

Un ejemplo de una instancia para el problema de estimación de cardinalidad es la secuencia: . Para esta instancia, . ${\displaystyle a,b,a,c,d,b,d}$ ${\displaystyle n=|\left\{{a,b,c,d}\right\}|=4}$

Solución ingenua

La solución ingenua al problema es la siguiente:

Inicializa un contador, c , a cero, . Inicializa una estructura de datos de diccionario eficiente, D , como una tabla hash o un árbol de búsqueda en el que se puede realizar la inserción y la pertenencia rápidamente. Para cada elemento , se emite una consulta de pertenencia. Si no es un miembro de D ( ) Suma a D Incrementa c en uno, De lo contrario ( ) no hace nada. Salida . ${\displaystyle c\leftarrow 0}$ ${\displaystyle x_{i}}$ ${\displaystyle x_{i}}$  ${\displaystyle x_{i}\notin D}$  ${\displaystyle x_{i}}$ ${\displaystyle c\leftarrow c+1}$ ${\displaystyle x_{i}\in D}$ ${\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 un almacenamiento limitado o si se debe minimizar el cálculo realizado para cada elemento. En tal caso, se han propuesto varios algoritmos de transmisión que utilizan un número fijo de unidades de almacenamiento. ${\displaystyle x_{i}}$

Algoritmo HyperLogLog

Algoritmos de streaming

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 específico de elementos, . Los estimadores de última generación convierten cada elemento en un bosquejo de datos de baja dimensión utilizando una función hash, . Las diferentes técnicas se pueden clasificar según los bosquejos de datos que almacenan. ${\displaystyle n}$ ${\displaystyle e_{j}}$ ${\displaystyle h(e_{j})}$

Bocetos mínimos y máximos

Los esbozos mínimos/máximos ^{[2] [3]} almacenan únicamente los valores hash mínimos/máximos. Ejemplos de estimadores de esbozos mínimos/máximos conocidos: Chassaing et al. ^[4] presenta el esbozo máximo, que es el estimador imparcial de varianza mínima para el problema. El estimador de esbozos máximos continuos ^[5] es el estimador de máxima verosimilitud . El estimador de elección en la práctica es el algoritmo HyperLogLog . ^[6]

La intuición detrás de estos estimadores es que cada boceto lleva información sobre la cantidad deseada. Por ejemplo, cuando cada elemento está asociado con un RV uniforme , , el valor mínimo esperado de es . La función hash garantiza que sea idéntico para todas las apariencias de . Por lo tanto, la existencia de duplicados no afecta el valor de las estadísticas de orden extremo. ${\displaystyle e_{j}}$ ${\displaystyle h(e_{j})\sim U(0,1)}$ ${\displaystyle h(e_{1}),h(e_{2}),\ldots ,h(e_{n})}$ ${\displaystyle 1/(n+1)}$ ${\displaystyle h(e_{j})}$ ${\displaystyle e_{j}}$

Existen otras técnicas de estimación además de los bocetos de min/max. El primer artículo sobre estimación de recuento distinto ^[7] describe el algoritmo Flajolet–Martin , un boceto de patrón de bits. En este caso, los elementos se convierten en un vector de bits y el boceto contiene el OR lógico de todos los valores codificados. El primer algoritmo asintóticamente óptimo en el espacio y el tiempo para este problema fue propuesto por Daniel M. Kane , Jelani Nelson y David P. Woodruff. ^[8]

Abajo-metrobocetos

Los bocetos inferiores m ^[9] son ​​una generalización de los bocetos min, que mantienen los valores mínimos, donde . Consulte Cosma et al. ^[2] para obtener una descripción general teórica de los algoritmos de estimación de recuento distinto, y Metwally ^[10] para obtener una descripción general práctica con resultados de simulación comparativos. ${\displaystyle m}$ ${\displaystyle m\geq 1}$

Algoritmo CVM

En comparación con otros algoritmos de aproximación para el problema de recuento distinto, el algoritmo CVM ^[11] (nombrado por Donald Knuth en honor a las iniciales de Sourav Chakraborty, NV Vinodchandran y Kuldeep S. Meel) utiliza muestreo en lugar de hash. El algoritmo CVM proporciona un estimador imparcial para el número de elementos distintos en un flujo, ^[12] además de las garantías estándar (ε-δ). A continuación se muestra el algoritmo CVM, incluida la ligera modificación de Donald Knuth, que agrega el bucle while para garantizar que B se reduzca. ^[12]

 Inicializar ${\displaystyle p\leftarrow 1}$ Inicializar el tamaño máximo del búfer , donde Inicializar un búfer vacío, B Para cada elemento en el flujo de datos de tamaño hacer: Si está en B entonces Eliminar de B un número aleatorio en Si entonces Insertar en B Mientras entonces Eliminar cada elemento de con probabilidad Fin Mientras Fin Para devolver . ${\displaystyle s}$ ${\displaystyle s\geq 1}$  ${\displaystyle a_{t}}$ ${\displaystyle A}$ ${\displaystyle n}$ ${\displaystyle a_{t}}$  ${\displaystyle a_{t}}$  ${\displaystyle u\leftarrow }$ ${\displaystyle [0,1)}$  ${\displaystyle u\leq p}$ ${\displaystyle (a_{t},u)}$  ${\displaystyle |B|=s}$ ${\displaystyle B}$ ${\displaystyle {\frac {1}{2}}}$  ${\displaystyle p\leftarrow {\frac {p}{2}}}$    ${\displaystyle |B|/p}$

Problema de recuento ponderado y distinto

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

Instancia : Un flujo de elementos ponderados con repeticiones y un entero . Sea el número de elementos distintos, es decir , y sean estos elementos . Por último, sea el peso de . ${\displaystyle x_{1},x_{2},\ldots ,x_{s}}$ ${\displaystyle m}$ ${\displaystyle n}$ ${\displaystyle n=|\left\{{x_{1},x_{2},\ldots ,x_{s}}\right\}|}$ ${\displaystyle \left\{{e_{1},e_{2},\ldots ,e_{n}}\right\}}$ ${\displaystyle w_{j}}$ ${\displaystyle e_{j}}$

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

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

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

Solución del problema de recuento ponderado-distinto

Cualquier estimador estadístico de orden extremo (bosquejos mín/máx) para el problema no ponderado se puede generalizar 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 bosquejos máximos continuos se extiende para resolver el problema ponderado. En particular, el algoritmo HyperLogLog ^[6] se puede extender 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.

Véase también

• Boceto de conteo mínimo
• Algoritmo de transmisión
• Máxima verosimilitud
• Estimador imparcial de varianza mínima

Referencias

1. Ullman, Jeff ; Rajaraman, Anand; Leskovec, Jure . "Minería de flujos de datos" (PDF) . {{cite journal}}: Requiere citar revista |journal=( ayuda )
2. Cosma, Ioana A.; Clifford, Peter (2011). "Un análisis estadístico de algoritmos de conteo probabilístico". Revista Escandinava de Estadística . arXiv : 0801.3552 .
3. Giroire, Frederic; Fusy, Eric (2007). Actas de 2007 del Cuarto Taller sobre Algoritmia Analítica y Combinatoria (ANALCO) . pp. 223–231. CiteSeerX 10.1.1.214.270 . doi :10.1137/1.9781611972979.9. ISBN .  978-1-61197-297-9.
4. Chassaing, Philippe; Gerin, Lucas (2006). "Estimación eficiente de la cardinalidad de grandes conjuntos de datos". Actas del 4º Coloquio sobre Matemáticas y Ciencias de la Computación . arXiv : math/0701347 . Bibcode :2007math......1347C.
5. Cohen, Edith (1997). "Marco de estimación de tamaño con aplicaciones al cierre transitivo y la accesibilidad". J. Comput. Syst. Sci . 55 (3): 441–453. doi : 10.1006/jcss.1997.1534 .
6. Flajolet, Philippe ; Fusy, Eric; Gandouet, Olivier; Meunier, Frederic (2007). "HyperLoglog: el análisis de un algoritmo de estimación de cardinalidad casi óptimo" (PDF) . Análisis de algoritmos .
7. Flajolet, Philippe ; Martin, G. Nigel (1985). "Algoritmos de conteo probabilísticos para aplicaciones de bases de datos" (PDF) . J. Comput. Syst. Sci . 31 (2): 182–209. doi :10.1016/0022-0000(85)90041-8.
8. Kane, Daniel M. ; Nelson, Jelani ; Woodruff, David P. (2010). "Un algoritmo óptimo para el problema de elementos distintos". Actas del 29.º Simposio anual de la ACM sobre principios de sistemas de bases de datos (PODS) .
9. Cohen, Edith ; Kaplan, Haim (2008). "Estimación más estricta utilizando bocetos bottom k" (PDF) . PVLDB .
10. Metwally, Ahmed; Agrawal, Divyakant; Abbadi, Amr El (2008), ¿Por qué utilizar el método logarítmico si podemos utilizar el método lineal?: Hacia un recuento diferenciado y eficaz del tráfico de búsqueda , Actas de la 11.ª conferencia internacional sobre la extensión de la tecnología de bases de datos: avances en la tecnología de bases de datos, págs. 618-629, CiteSeerX 10.1.1.377.4771 
11. Chakraborty, Sourav; Vinodchandran, NV; Meel, Kuldeep S. (2022). "Elementos distintos en secuencias: un algoritmo para el libro (de texto)". Schloss Dagstuhl – Leibniz-Zentrum für Informatik: 6 páginas, 727571 bytes. arXiv : 2301.10191 . doi : 10.4230/LIPIcs.ESA.2022.34 . ISSN  1868-8969. {{cite journal}}: Requiere citar revista |journal=( ayuda )
12. Knuth, Donald (mayo de 2023). "El algoritmo CVM para estimar elementos distintos en flujos" (PDF) . {{cite journal}}: Requiere citar revista |journal=( ayuda )
13. Cohen, Reuven ; Katzir, Liran; Yehezkel, Aviv (2014). "Un esquema unificado para generalizar estimadores de cardinalidad a la agregación de sumas". Cartas de procesamiento de información . 115 (2): 336–342. doi :10.1016/j.ipl.2014.10.009.