Nuevo algoritmo para contar eficientemente elementos únicos

• El algoritmo CVM aproxima la cantidad de elementos distintos en flujos de datos largos, estimando cuántos elementos únicos hay sin almacenar la lista completa
• Se enfoca en el problema de elementos distintos (distinct elements problem) cuando toda la entrada supera la memoria, y puede aplicarse a grandes logs o flujos de eventos con muchas entradas duplicadas
• Conserva solo algunos elementos en memoria limitada y, cada vez que se llena el espacio, repite una eliminación aleatoria para igualar la probabilidad de que cada elemento permanezca
• En el ejemplo de Hamlet, con memoria para 100 palabras estimó en promedio 3,955 elementos tras 5 ejecuciones, cerca del número real de palabras únicas, 3,967; con memoria para 1,000 palabras mejoró a un promedio de 3,964
• A medida que aumenta la memoria, la precisión mejora, y si alcanza para guardar todos los elementos únicos, también puede lograrse 100% de precisión

---

Contar elementos únicos en flujos de datos largos

• El objetivo es estimar eficientemente la cantidad de elementos únicos tras eliminar duplicados en una lista larga donde los elementos van llegando uno por uno
• La forma más simple es guardar todos los elementos vistos hasta el momento y, cada vez que llega uno nuevo, compararlo con la lista existente
  • En un estudio de vida silvestre, habría que seguir revisando la lista de fotos de animales ya vistos
  • Si la lista llega a miles de millones de entradas, como en el conteo diario de usuarios que inician sesión en Facebook, almacenar y comparar se vuelve difícil
• CVM es un algoritmo cuyo nombre proviene de Sourav Chakraborty, Vinodchandran Variyam y Kuldeep Meel
• Puede aplicarse a listas donde los elementos llegan de forma secuencial, como palabras, productos en una cinta transportadora o vehículos en una autopista

Idea central del algoritmo CVM

• CVM no almacena todos los elementos, sino solo una parte de ellos que cabe en memoria limitada
• Usa aleatoriedad para controlar la probabilidad de que cada elemento único permanezca en la lista final
• Andrew McGregor considera que este algoritmo es muy simple y fácil de implementar, y que incluso podría convertirse en el enfoque básico para el problema práctico de elementos distintos

Cómo funciona con el ejemplo de Hamlet

• Hamlet contiene un total de 30,557 palabras, y el algoritmo estima de ellas la cantidad de palabras únicas
• Si suponemos una pizarra con espacio para 100 palabras, al principio se anotan las primeras 100 palabras únicas, saltándose las repetidas
• Cuando el espacio se llena, se lanza una moneda para cada palabra
  • Si sale cara, la palabra se conserva
  • Si sale cruz, la palabra se elimina
  • Después de esta etapa preliminar, quedan alrededor de 50 palabras únicas

Una condición de permanencia más estricta en cada ronda

• En la Ronda 1, se siguen agregando palabras nuevas y, si reaparece una palabra que ya está en la lista, se lanza una moneda y se elimina si sale cruz
• Cuando la lista vuelve a llenarse con 100 palabras, se eliminan aproximadamente la mitad según el resultado de 100 lanzamientos de moneda, y así termina la Ronda 1
• Desde la Ronda 2, sobrevivir se vuelve más difícil para las palabras
  • Si aparece una palabra repetida, se elimina si sale cruz
  • Si sale cara, se lanza la moneda una vez más y solo se conserva si también sale cara en la segunda
• En la tercera ronda hacen falta 3 caras seguidas, y en la cuarta ronda hacen falta 4 caras seguidas
• En general, al final de la k-ésima ronda, la probabilidad de que cada palabra permanezca es de 1/2^k

Cálculo de la estimación y resultados experimentales

• Si se divide la cantidad de palabras que quedan en la lista final por la probabilidad de permanencia, puede estimarse el número total de palabras únicas
• Por ejemplo, si después de 6 rondas quedan 61 palabras, al dividir por la probabilidad 1/2^6 se obtiene una estimación de 3,904
• La cantidad real de palabras únicas en Hamlet es 3,967
• Cuanto mayor es el tamaño de la memoria, más se acerca la estimación al valor real
  • Con memoria para 100 palabras, el promedio de 5 ejecuciones fue de 3,955
  • Con memoria para 1,000 palabras, el promedio fue de 3,964
• Variyam y sus colegas demostraron matemáticamente que la precisión de esta técnica escala según el tamaño de la memoria

Una solución simple pero no trivial

• CVM es considerado un avance importante en el problema de elementos distintos, estudiado durante más de 40 años
• William Kuszmaul cree que incluso en problemas muy básicos y bien estudiados todavía pueden quedar soluciones simples, pero difíciles de imaginar

[GN⁺]

Comentarios de Hacker News

• Participé con los autores en la implementación de la versión de este algoritmo para contar el volumen de DNF. El artículo relacionado está aquí: https://www.msoos.org/2023/09/pepin-our-probabilistic-approx...
  El código está aquí: https://github.com/meelgroup/pepin
  El algoritmo es ridículamente rápido; a menudo, hasta el 30% del tiempo total se va en E/S de lectura de archivos. Como referencia, Knuth también contribuyó al algoritmo, y sus notas están aquí: https://cs.stanford.edu/~knuth/papers/cvm-note.pdf
  Se tomó un mes entero de su trabajo en TAOCP para hacer esto y, tal como uno se imaginaría, fue increíblemente brillante

  • Es realmente interesante, y me interesan mucho las personas extraordinariamente talentosas. Me da curiosidad por qué Knuth te pareció tan excepcional. Me pregunto si hubo algún momento especial, si fue la velocidad con la que entendía las ideas, o su capacidad para explicarlas con facilidad
  • Esto parece tonto. Muy tonto, ¿pero me estaré perdiendo algo? Esto no es contar, es simplemente muestreo, y si realmente quieres contar todas las palabras distintas, no parece que el uso de memoria cambie en comparación con simplemente contarlas
  • Quizá lo sepan, pero me pregunto por qué no se opta por ordenar priorizando los conteos más altos y, cuando se llena, descartar la mitad inferior. Para otros puede ser obvious, pero quisiera saber la razón
  • Me pregunto cuáles son los principales usos de este algoritmo
  • Ahora ya tenemos a alguien a quien culpar por el retraso del próximo libro de Knuth :)

• Este algoritmo se parece a HyperLogLog, que también se cita en el paper. Usa la misma intuición de obtener una estimación siguiendo si salen caras/cruces de forma consecutiva, pero se siente como si le diera la vuelta a la idea para convertirla en un algoritmo más simple que descarta los valores recordados según la continuidad de los resultados de la moneda
  Funciona de manera especialmente eficiente en escenarios de streaming, de modo que permite mantener algo parecido a un “contador” de la cantidad de elementos distintos, aunque con una tasa de error
  La ventaja de HyperLogLog es que, en cierto sentido, se comporta como un conjunto hash. Puedes agregar elementos, contar la cantidad de elementos distintos y, algo importante, fusionar dos HLL para formar una unión; aun así, incluso con conjuntos de miles de millones de elementos, la memoria queda fija en unos pocos KB. En almacenes de datos distribuidos, la agg de cardinality de Elasticsearch/OpenSearch y PFADD/PFMERGE/PFCOUNT de Redis/Redict usan este truco
  No sé bien cómo se compara exactamente el algoritmo CVM con HLL, pero si fue revisado por Knuth y hasta un estudiante de pregrado puede implementarlo fácilmente, debe ser un algoritmo bastante bueno

  • HLL puede estimar tanto la unión como la intersección de dos HLL, por lo que también puede usarse para estimar la cardinalidad de joins
    http://oertl.github.io/hyperloglog-sketch-estimation-paper/
  • Estas estructuras de datos también se pueden fusionar. Si las “rondas” de las dos instancias que se van a fusionar son distintas, basta con avanzar la que esté en la ronda anterior por la diferencia de rondas. Es decir, descartar aleatoriamente la mitad. Luego se insertan los valores de una lista en la otra y se ignoran los duplicados. Si el resultado es demasiado grande, se descarta aleatoriamente la mitad y se incrementa el número de ronda
    En mi trabajo anterior implementé exactamente este algoritmo, pero también almacenábamos junto a cada valor una estimación de cuántas veces había aparecido. Gracias a eso podíamos generar una lista aproximada de los valores más frecuentes y el conteo estimado de cada uno
  • Haciendo memoria de mis tiempos de escuela, me pregunto: ¿qué relación tienen aquí HLL y CVM con el muestreo de reservorio que aprendí antes?
    Hace tiempo, cuando trabajaba en un hospital, usé muestreo de reservorio para crear un subconjunto pequeño de registros almacenados en cintas DAT

• Me tomó casi el mismo tiempo leer el artículo académico que leer el post del blog, y el artículo fue más útil
  https://arxiv.org/pdf/2301.10191
  Trata sobre estimar la cardinalidad del conjunto de elementos que aparecen en un stream. El algoritmo es tan simple que, mientras leía el artículo, pude programarlo yo mismo y jugar con él
  Los autores dejan claro que el público y el propósito de este algoritmo son estudiantes de pregrado y libros de texto

  • El subtítulo del artículo, “An Algorithm for the (Text) Book”, parece aludir a la famosa expresión de Paul Erdős sobre pruebas “salidas de The Book”, tan elegantes por su simplicidad y belleza
    Como Knuth lo revisó personalmente, quizá haya dicho que este algoritmo es de ese tipo. Si es así, que los autores lo hayan puesto en el título puede parecer una fanfarronada poco modesta, pero es una fanfarronada totalmente merecida
    Yo recordaba que la expresión era de Knuth, pero mi memoria estaba equivocada
  • Más de la mitad del post del blog era padding. Que el algoritmo sea tan simple que resulte difícil convertirlo en un post largo es, en realidad, algo bueno
  • Estoy de acuerdo en que el artículo es mejor que el post del blog, pero una crítica al artículo de CVM es que tiene una condición de terminación. Las notas de Knuth sobre CVM que aparecieron en otro hilo simplemente ponen un bucle en el paso de reducir el reservoir a la mitad para que se libere más espacio
    Parece menos engorroso usar simplemente un bucle que explicar https://en.wikipedia.org/wiki/Up_tack. [1]
    [1] https://news.ycombinator.com/item?id=40388878
  • Antes hacía ciencias de la computación, pero no sé si se me alisó el cerebro: esto parece más confuso de lo necesario
    Para empezar, el manejo de contradiction me parece simplemente un error o un panic, y no entiendo por qué lo expresaron así. También confunde la premisa 1..m. No me quedaba claro si había que conocer el tamaño de antemano o no, aunque al seguir leyendo parece que no. Se elige un umbral y la probabilidad cambia según el tamaño del stream, pero la descripción del algoritmo está escrita como si tuviera una única salida, lo cual confunde
    Las cotas de Chernoff y delta/epsilon tampoco se explican en absoluto en el artículo, lo que me confundió aún más. El código que implementé en Go está aquí: https://github.com/betamos/distinct
    Tiene mucho más sentido extraer la parte del umbral a un helper que arriesgarse a asignar demasiada memoria por error. También debería haber métodos para estimar la confianza o la tasa de error. Nadie conoce de antemano el tamaño del stream, así que resulta más natural actualizar estos valores sobre la marcha
  • Si “para estudiantes de pregrado y libros de texto” no significa que sea lo bastante simple para que ellos lo usen, sino que de verdad solo es útil ahí, estaría bien que explicaran por qué no es útil para expertos y solo para estudiantes de pregrado

• Dado el tema del artículo, la nota al pie resulta especialmente encantadora
  Los autores dicen que, en vez de seguir la antigua convención de ordenar los nombres alfabéticamente, eligieron un orden aleatorio y lo marcaron con r⃝. El registro públicamente verificable de la aleatorización está aquí: https://www.aeaweb.org/journals/policies/random-author-order...
  [0]: https://arxiv.org/pdf/2301.10191

• ¿No parece que la explicación del algoritmo está mal?
  Si se implementa “verificar si está en la lista y luego borrar” según la explicación “cuando encuentras una palabra que ya está en la lista, vuelves a lanzar una moneda y, si sale cruz, borras la palabra”, se repite unas 20 veces y la estimación sale disparatada, como 772800512
  En cambio, si primero guardas la palabra y luego borras la repetida, da 7240, cerca del número real de palabras únicas, 7233. Es decir, el orden importa en la explicación y parece que se transmitió mal

  • Me pasó lo mismo. Si implementas solo a partir de la explicación de Quanta Magazine sin ver el artículo de arxiv, siempre salen estimaciones como 461746372167462146216468796214962164
    Después de leer el artículo, obtuve estimaciones correctas, y el problema era un pequeño else. La explicación de Quanta se lee como “si no está en la lista, agrégala; si no, elimínala según la probabilidad”, pero la implementación correcta debe aplicar después la condición probabilística independientemente de si se agregó o no
  • Justo estaba intentando resolverlo y vine a ver si a alguien más le había pasado lo mismo; sí. Si sigues la explicación, sale mal. Hay que implementarlo agregando el nuevo valor en cada ronda, luego podando probabilísticamente y, cuando la memoria llega al límite, eliminando una mitad aleatoria de todo el conjunto

• Estimar la cantidad de elementos únicos de un conjunto y contar la cantidad de elementos únicos de un conjunto son cosas muy distintas. Es un método genial, pero el título no me gusta

  • No son tan distintas. Todos los métodos de conteo del mundo real tienen una tasa de error distinta de cero, así que en la mayoría de los contextos los dos términos se usan de forma intercambiable
    Por ejemplo, en una elección se dice que “se cuentan” los votos, pero si está reñida se hace un “recuento” y se espera perfectamente que salga un número ligeramente distinto al conteo original. Entonces el conteo de votos también es, en realidad, una estimación de votos, y el recuento no es más que una estimación con márgenes de error más estrechos
    El mito de las “countless stones” (https://en.wikipedia.org/wiki/Countless_stones) también se siente como un recordatorio popular de que ni siquiera con algo tan grande, sólido y estático como menhires uno puede estar demasiado seguro de haberlo contado correctamente
    Los casos en los que contar no es estimar se limitan más o menos a situaciones matemáticas: cuando puedes garantizar que trataste todos los elementos sin omitir ninguno y que no confundiste la identidad de ningún elemento con otro
  • Para números relativamente pequeños, eso es cierto. Pero con números muy grandes, normalmente la estimación se trata como equivalente al conteo, y el resultado a veces se expresa no como entero sino en notación científica, es decir, como un número de punto flotante
    Por ejemplo, el mol es un entero, pero su valor solo se conoce de forma aproximada, y a nadie le importa el valor exacto
  • Esto no es estimation, sino approximation

• Me encantan estos ejemplos de pensar fuera de la caja. Más aún porque, profesionalmente, es algo que no se me da muy bien. Lo importante no es solo aprender la forma correcta de resolver un problema, sino el proceso de encontrar las preguntas que hacen que el problema que tienes sea más fácil y, a veces, incluso posible de resolver.
  En este caso, la pregunta clave es: “no necesitamos un número exacto, basta con definir un rango probabilístico dentro de parámetros establecidos”. Para otros problemas habrá otras preguntas. Espero que, al ver suficientes ejemplos de este tipo, pueda interiorizar ese proceso mental y aplicarlo correctamente.

  • Para ser justos, esto lo hizo un equipo de investigación universitario. Literalmente es un equipo de personas que puede pasar todo el día revisando iterativamente un tema con el método científico.
    Si en una gran empresa te pagaran por sentarte todo el día frente a un pizarrón con ingenieros igual de inteligentes, seguro podrías producir algo que al resto del mundo le parecería una “solución fuera de la caja”.
    Pero a la mayoría de nosotros nos pagan por trabajar en una línea de producción de JIRA, así que tenemos tiempo limitado para experimentar con un solo problema.
  • Creo que normalmente se le llama pensamiento lateral. Edward de Bono escribió algunos libros al respecto; podrían resultarte interesantes.

• El ejemplo de “¿y si quieres contar cuántos usuarios distintos inician sesión cada día en Facebook, y algunos usuarios inician sesión desde varios dispositivos y en distintos momentos?” no me parece una situación en la que este algoritmo sea particularmente útil en la práctica.
  Si al diseñar el proceso de inicio de sesión ya sabes que necesitas esa información, es sencillo: guardas la fecha del último inicio de sesión de cada cuenta y aumentas el contador de usuarios únicos solo cuando el valor guardado sea distinto de la fecha actual.
  Incluso si no fuera así, después podrías “reproducir” el flujo de eventos de inicio de sesión desde la base de datos para analizarlo. Sería distinto si ya tuvieras años de datos acumulados.

  • Ese enfoque requiere rastrear “la fecha del último inicio de sesión de cada cuenta”, así que necesita memoria proporcional al número de usuarios. El punto de este algoritmo es hacerlo con mucha menos memoria y con memoria fija.

• A propósito de conteos, quiero mencionar un algoritmo eficiente y fácil de implementar para encontrar los k elementos principales en un stream. Creo que es menos conocido de lo que debería.
  A Simple Algorithm for Finding Frequent Elements in Streams and Bags
  Karp, Shenker & Papadimitriou
  https://www.cs.umd.edu/~samir/498/karp.pdf

  • La expresión “los k elementos principales en un stream” suena distinta a la descripción del resumen. El resumen dice que encuentra símbolos cuya frecuencia supera un umbral dado en una cadena muy larga de símbolos provenientes de un alfabeto grande.
    Tu descripción suena como si se buscaran k elementos fijos y se garantizara que necesariamente son los más frecuentes. El resumen suena como si encontrara elementos cuyo número no se conoce de antemano y que cumplen una condición de ser mayores que cierto valor k.
    Me parece la diferencia entre “encontrar los 100 usuarios de mayor edad” y “encontrar todos los usuarios mayores de 30 años”; ¿entendí mal lo que dijiste o el resumen? El inglés no es mi lengua materna, así que me confundí.

• Así que los científicos de la computación inventaron una forma eficiente en memoria de estimar el tamaño de un subconjunto.

  • Si se puede obtener una estimación con menos rondas de lanzamientos de moneda, también parece ser más rápido. Puede que no haga falta recorrer todo el “libro” hasta el final para estimar el número de palabras distintas.
  • Aquí lo importante es el subconjunto. Concretamente, un subconjunto de elementos únicos.