Contar parece una de las operaciones más sencillas que puede realizar una computadora. Basta con sumar uno, después otro y continuar hasta alcanzar el final. El problema comienza cuando la pregunta cambia ligeramente: ¿cuántas cosas distintas han aparecido dentro de una corriente de datos gigantesca?
Una plataforma puede recibir millones de visitas, aunque muchas pertenezcan al mismo usuario. Una red puede procesar incontables conexiones procedentes de direcciones repetidas. Un sistema de ventas puede registrar millones de operaciones realizadas con unos cuantos miles de productos. Para obtener el número exacto de elementos únicos, la máquina tendría que recordar todo lo visto y comprobar continuamente si cada dato ya había aparecido.
Ese desafío, conocido como el problema de los elementos distintos o estimación de F0, lleva más de cuatro décadas ocupando a los investigadores. Ya existían algoritmos muy eficientes, pero sus demostraciones recurrían a herramientas como funciones hash universales e independencia por pares, conceptos difíciles de explicar fuera de cursos avanzados. Tres científicos encontraron una alternativa sorprendentemente directa: conservar una muestra aleatoria y reducirla mediante el equivalente digital de lanzar monedas.
El verdadero problema no es contar: es recordar todo lo que ya apareció
Imaginemos una lista formada por millones de palabras. Contar cuántas contiene es sencillo, porque cada nueva entrada aumenta el contador. Identificar cuántas son diferentes exige saber si cada palabra ya apareció anteriormente.
La solución exacta consiste en guardar todos los elementos únicos dentro de una estructura de memoria. Funciona bien mientras la lista sea pequeña, pero deja de ser práctica cuando los datos llegan continuamente y su variedad supera con creces la capacidad disponible. Por eso los algoritmos de streaming intentan procesar cada dato una sola vez y conservar únicamente una representación compacta del conjunto.
Sourav Chakraborty, N. V. Vinodchandran y Kuldeep S. Meel presentaron en el European Symposium on Algorithms de 2022 un método basado únicamente en muestreo y probabilidad elemental. El objetivo no era superar todas las soluciones existentes en cada métrica, sino conseguir un algoritmo con un uso reducido de memoria cuya lógica y demostración pudieran entender estudiantes universitarios sin dominar técnicas matemáticas especializadas.
Por tanto, el avance no consiste en que las computadoras hayan aprendido repentinamente a contar. Consiste en que pueden estimar cuántos elementos diferentes han visto sin guardar una copia de cada uno ni depender de una maquinaria criptográfica o estadística difícil de implementar y analizar.
El algoritmo guarda una muestra y lanza monedas cuando la memoria se llena
El funcionamiento básico del CVM resulta casi desconcertante por su sencillez. El sistema comienza guardando los elementos distintos que encuentra con una probabilidad de uno: en otras palabras, conserva inicialmente todo.
También mantiene una variable llamada p, que representa la probabilidad con la que cada elemento ha sido incluido en la muestra. Cuando el espacio disponible alcanza su límite, el algoritmo lanza una moneda virtual para cada elemento almacenado y descarta aproximadamente la mitad. Después divide también entre dos la probabilidad de muestreo.
Si vuelve a llenarse, repite el proceso. La memoria vuelve a reducirse aproximadamente a la mitad y la probabilidad pasa, por ejemplo, de 1/2 a 1/4, después a 1/8 y así sucesivamente. Cuando termina de procesar los datos, divide la cantidad de elementos conservados entre esa probabilidad.
La intuición puede explicarse sin fórmulas. Si una persona guarda una de cada cuatro flores que encuentra y termina sosteniendo cinco, probablemente ha visto unas veinte. El algoritmo realiza esencialmente ese mismo cálculo, pero incorpora reglas para gestionar duplicados y mantener una muestra estadísticamente válida mientras los datos continúan llegando.
Eso no significa que entregue exactamente el mismo resultado en todas las ejecuciones. Es un algoritmo aleatorio y, con muy poca memoria, su estimación puede desviarse. Al aumentar el tamaño del espacio reservado, el margen de error disminuye. El trabajo original demuestra cómo ajustar ese tamaño para obtener una aproximación dentro de un error determinado y con una probabilidad de fallo controlada.
Donald Knuth lo vio y pensó inmediatamente en los futuros libros de informática
La propuesta llamó la atención de Donald Knuth, una de las figuras más influyentes de la informática teórica. En mayo de 2023 publicó una extensa nota sobre el método, lo bautizó como algoritmo CVM por las iniciales de Chakraborty, Vinodchandran y Meel, y aseguró que no podía evitar explicárselo a casi todas las personas con las que hablaba.
Knuth consideró que su combinación de sencillez y profundidad lo convertía en un candidato natural para aparecer en futuros libros de texto. También detectó un problema sutil en una formulación inicial y presentó una versión modificada que conserva la idea central, pero ajusta la manera en que se gestiona el desbordamiento de la memoria.
El interés no terminó allí. En 2025, otro equipo formalizó matemáticamente el algoritmo mediante Isabelle/HOL, un asistente informático utilizado para verificar demostraciones. El trabajo confirmó sus propiedades y presentó una variante adicional que siempre produce un resultado y mantiene una estimación sin sesgo.
El CVM no vuelve irrelevantes a los métodos anteriores ni resuelve el conteo exacto sin coste. Su importancia es más silenciosa: demuestra que un problema estudiado durante décadas todavía podía admitir una solución radicalmente más comprensible.
A veces, la informática avanza construyendo sistemas cada vez más complejos. Otras veces lo hace descubriendo que bastaba con guardar unas pocas cosas, lanzar algunas monedas y multiplicar lo que sobrevivió.
