Problema de conteo distinto
En informática, el problema de conteo distinto [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 de sensores / RFID .
Un ejemplo de una instancia para el problema de estimación de cardinalidad es la secuencia :. Para este caso ,.
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 se escala para el almacenamiento limitado o si el cálculo realizado para cada elemento 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 ,. Los estimadores de última generación codifican cada elemento en un boceto de datos de baja dimensión utilizando una función hash ,. Las diferentes técnicas se pueden clasificar de acuerdo con los esquemas de datos que almacenan.
Los bocetos mínimo / máximo [2] [3] almacenan solo los valores hash mínimos / máximos. Ejemplos de estimadores de croquis mínimo / máximo conocidos: Chassaing et al. [4] presenta un bosquejo máximo, que es el estimador insesgado de varianza mínima para el problema. El estimador de bocetos 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]