Novo algoritmo para contar itens únicos com eficiência
(quantamagazine.org)- O algoritmo CVM aproxima o número de itens distintos em longos fluxos de dados, estimando a quantidade de itens únicos sem armazenar a lista inteira
- Ele se concentra no problema dos elementos distintos (distinct elements problem), em que toda a entrada excede a memória, e pode ser aplicado a grandes logs ou fluxos de eventos com muitas entradas duplicadas
- Mantendo apenas alguns itens em memória limitada e repetindo remoções aleatórias sempre que o espaço enche, ele iguala a probabilidade de cada item permanecer
- No exemplo de Hamlet, com memória para 100 palavras, a média de 5 execuções estimou 3.955 itens, próximo do número real de 3.967 palavras únicas; com memória para 1.000 palavras, a média melhorou para 3.964
- À medida que a memória aumenta, a precisão também melhora, e se ela for suficiente para conter todos os itens únicos, 100% de precisão também é possível
Contando itens únicos em longos fluxos de dados
- O objetivo é estimar com eficiência o número de itens únicos após remover duplicatas em uma longa lista na qual os itens chegam um a um
- A forma mais simples é armazenar todos os itens vistos até agora e, sempre que um novo item entra, compará-lo com a lista existente
- Em pesquisas com vida selvagem, seria preciso continuar verificando a lista de fotos de animais já vistos
- Quando a lista chega à casa dos bilhões, como no número diário de usuários que fazem login no Facebook, armazenar e comparar se torna difícil
- CVM é um algoritmo cujo nome vem de Sourav Chakraborty, Vinodchandran Variyam e Kuldeep Meel
- Ele pode ser aplicado a listas em que os itens entram sequencialmente, como palavras, produtos em uma esteira transportadora ou veículos em uma rodovia
A ideia central do algoritmo CVM
- O CVM não armazena todos os itens; ele mantém apenas uma parte deles, que cabe em memória limitada
- Ele usa aleatoriedade para controlar a probabilidade de cada item distinto permanecer na lista final
- Andrew McGregor avalia que o algoritmo é muito simples e fácil de implementar, podendo até se tornar uma abordagem básica para o problema prático dos elementos distintos
Como ele funciona no exemplo de Hamlet
- Hamlet tem ao todo 30.557 palavras, e o algoritmo estima, dentro delas, o número de palavras únicas
- Supondo uma lousa com memória para 100 palavras, no início ele anota as primeiras 100 palavras únicas, pulando as repetidas
- Quando o espaço fica cheio, ele joga uma moeda para cada palavra
- Se der cara, a palavra é mantida
- Se der coroa, a palavra é apagada
- Depois dessa etapa preliminar, restam cerca de 50 palavras únicas
Critérios de permanência ficam mais rígidos a cada rodada
- Na Rodada 1, novas palavras continuam sendo adicionadas e, se uma palavra já presente na lista aparecer de novo, uma moeda é jogada e ela é apagada se der coroa
- Quando a lista volta a encher com 100 palavras, cerca de metade é apagada com base no resultado de 100 lançamentos de moeda, e a Rodada 1 termina
- A partir da Rodada 2, fica mais difícil para uma palavra sobreviver
- Quando uma palavra repetida aparece, ela é apagada se der coroa
- Se der cara, joga-se a moeda mais uma vez, e ela só permanece se a segunda também der cara
- Na terceira rodada, são necessárias 3 caras seguidas; na quarta, 4 caras seguidas
- Em geral, ao fim da k-ésima rodada, a probabilidade de cada palavra permanecer passa a ser 1/2^k
Cálculo da estimativa e resultados experimentais
- Para estimar o total de palavras únicas, basta dividir o número de palavras que restaram na lista final pela probabilidade de permanência
- Por exemplo, se 61 palavras restarem após 6 rodadas, divide-se por 1/2^6 e obtém-se uma estimativa de 3.904
- O número real de palavras únicas em Hamlet é 3.967
- Quanto maior a memória, mais a estimativa se aproxima do valor real
- Com memória para 100 palavras, a média de 5 execuções foi de 3.955
- Com memória para 1.000 palavras, a média foi de 3.964
- Variyam e seus colegas provaram matematicamente que a precisão dessa técnica escala de acordo com o tamanho da memória
Uma solução simples, mas não trivial
- O CVM é visto como um avanço importante no problema dos itens distintos, estudado há mais de 40 anos
- William Kuszmaul acredita que, mesmo em problemas muito básicos e amplamente estudados, ainda podem existir soluções simples, mas difíceis de imaginar
1 comentários
Comentários do Hacker News
Participei com os autores da implementação da versão deste algoritmo para contagem de volume de DNF. O post relacionado está aqui: https://www.msoos.org/2023/09/pepin-our-probabilistic-approx...
O código está aqui: https://github.com/meelgroup/pepin
O algoritmo é absurdamente rápido, a ponto de às vezes 30% do tempo total ser gasto em E/S de leitura de arquivos. Para referência, Knuth também contribuiu para o algoritmo, e as anotações dele estão aqui: https://cs.stanford.edu/~knuth/papers/cvm-note.pdf
Ele tirou um mês inteiro do trabalho no TAOCP para fazer isso e, como você pode imaginar, foi incrivelmente brilhante
Este algoritmo parece se assemelhar ao HyperLogLog, que também é citado no artigo. Ele usa o mesmo insight de obter uma estimativa rastreando se caras/coroas aparecem em sequência, mas parece inverter a ideia para criar um algoritmo mais simples que descarta valores lembrados conforme a continuidade dos resultados da moeda
Ele funciona de modo especialmente eficiente em cenários de streaming, permitindo manter algo parecido com um “contador” de número de elementos distintos, embora com uma taxa de erro
A vantagem do HyperLogLog, de certa forma, é que ele se comporta como um conjunto hash. Você pode adicionar itens, contar o número de itens distintos e, de forma importante, mesclar dois HLLs para formar uma união, enquanto a memória permanece fixa em alguns KB mesmo para conjuntos com bilhões de itens. Em armazenamentos de dados distribuídos, o cardinality agg do Elasticsearch/OpenSearch e os comandos PFADD/PFMERGE/PFCOUNT do Redis/Redict usam esse truque
Não sei exatamente como o algoritmo CVM se compara ao HLL, mas, como foi revisado por Knuth e dizem que até um aluno de graduação consegue implementá-lo facilmente, deve ser um algoritmo bem bom
http://oertl.github.io/hyperloglog-sketch-estimation-paper/
No meu emprego anterior, implementei exatamente esse algoritmo, mas também armazenávamos ao lado de cada valor uma estimativa de quantas vezes aquele valor havia aparecido. Com isso, conseguíamos criar uma lista aproximada dos valores mais frequentes e a contagem estimada de cada um
Quando trabalhei em um hospital, usei amostragem por reservatório para criar um pequeno subconjunto de registros armazenados em fitas DAT
Levei quase o mesmo tempo para ler o artigo acadêmico que levaria para ler o post do blog, e o artigo foi mais proveitoso
https://arxiv.org/pdf/2301.10191
Ele trata de estimar a cardinalidade do conjunto de elementos vindos de um stream. O algoritmo é tão simples que dá para codá-lo você mesmo e brincar com ele enquanto lê o artigo
Os autores deixam claro que o público-alvo e o objetivo do algoritmo são alunos de graduação e livros-texto
Como o próprio Knuth revisou, talvez tenha dito que esse algoritmo era desse tipo. Se for o caso, colocá-lo no título parece uma ostentação pouco modesta por parte dos autores, mas é algo de que vale a pena se gabar
Eu lembrava que essa expressão era de Knuth, mas minha memória estava errada
Parece menos trabalhoso usar apenas um loop do que explicar https://en.wikipedia.org/wiki/Up_tack. [1]
[1] https://news.ycombinator.com/item?id=40388878
Primeiro, o tratamento da contradição parece apenas um erro ou panic, e não entendi por que foi expresso desse jeito. Além disso, a premissa de 1..m é confusa. Não ficou claro para mim se é preciso saber o tamanho de antemão ou não, mas, lendo mais, parece que não. Você escolhe um limiar e a probabilidade muda conforme o tamanho do stream, mas a descrição do algoritmo dá a entender que há uma única saída, o que é confuso
O limite de Chernoff e delta/epsilon também não são explicados no artigo, o que me confundiu ainda mais. O código que implementei em Go está aqui: https://github.com/betamos/distinct
Faz muito mais sentido extrair a parte do limiar para um helper do que alocar memória demais por engano. Também deveria haver métodos para estimar a confiabilidade ou a taxa de erro. Como ninguém sabe o tamanho do stream de antemão, é mais natural atualizar esse valor ao longo do processamento
Considerando o tema do artigo, a nota de rodapé é particularmente charmosa
Os autores dizem que escolheram uma ordem aleatória em vez da antiga convenção de ordenar os autores alfabeticamente, e a marcaram com r⃝. O registro publicamente verificável da aleatorização está aqui: https://www.aeaweb.org/journals/policies/random-author-order...
[0]: https://arxiv.org/pdf/2301.10191
A explicação do algoritmo não parece errada?
Se você implementar “verificar se está na lista e então remover” conforme a explicação “quando encontrar uma palavra que já está na lista, jogue a moeda de novo e, se der coroa, apague a palavra”, ele roda cerca de 20 iterações e dá uma estimativa absurda como 772800512
Por outro lado, se você primeiro armazenar a palavra e depois remover a mesma palavra, o resultado é 7240, perto do número real de palavras distintas, 7233. Ou seja, a ordem importa na explicação, e parece ter sido transmitida de forma errada
Depois de ler o artigo, consegui a estimativa correta, e o problema era um pequeno else. A explicação da Quanta soa como “se não está na lista, adicione; caso contrário, remova conforme a probabilidade”, mas a implementação correta deve aplicar a condição probabilística depois disso, independentemente de ter adicionado ou não
Estimar o número de elementos distintos em um conjunto e contar o número de elementos distintos em um conjunto são coisas bem diferentes. É um método legal, mas o título não é muito bom
Por exemplo, em eleições dizemos que “contamos os votos”, mas, se a disputa for apertada, há uma “recontagem”, e é perfeitamente esperado que possa sair um número um pouco diferente da contagem original. Então contar votos na verdade também é estimar votos, e uma recontagem é apenas uma estimativa com uma margem de erro menor
O mito das “countless stones” (https://en.wikipedia.org/wiki/Countless_stones) também parece um lembrete folclórico de que não dá para ter tanta certeza de que se contou corretamente nem mesmo algo grande, sólido e estático como menires
Os casos em que contar não é estimar ficam basicamente restritos a situações matemáticas: quando é possível garantir que todos os itens foram tratados sem omissões e que a identidade de nenhum item foi confundida com a de outro
Por exemplo, um mol é um inteiro, mas seu valor é conhecido apenas aproximadamente, e ninguém se importa com o valor exato
Gosto muito de exemplos de pensar fora da caixa desse tipo. Ainda mais porque, profissionalmente, é algo em que não sou muito bom. O importante não é só aprender o jeito certo de resolver um problema, mas o processo de descobrir a pergunta que torna o problema que você tem mais fácil — e, às vezes, possível — de resolver.
Aqui, a pergunta central é: “não preciso de um número exato; basta definir um intervalo probabilístico dentro de parâmetros definidos”. Em outros problemas, haverá outras perguntas. Espero que, vendo exemplos suficientes assim, eu consiga internalizar o processo de pensamento e aplicá-lo corretamente.
Se uma grande empresa pagasse você para ficar o dia todo diante de um quadro branco com engenheiros igualmente inteligentes, certamente daria para produzir algo que, para o resto do mundo, pareceria uma “solução fora da caixa”.
Mas a maioria de nós é paga para trabalhar na linha de produção do JIRA, então o tempo para ficar preso a um único problema e experimentar é limitado.
O exemplo “e se você quiser contar o número de usuários distintos que fazem login diariamente no Facebook, sendo que alguns usuários entram por vários dispositivos e em vários momentos?” não me parece uma situação em que esse algoritmo seja realmente útil.
Se você já sabe que precisa dessa informação ao projetar o processo de login, é simples: armazene a data do último login de cada conta e incremente o contador de usuários únicos apenas quando o valor armazenado for diferente da data atual.
Mesmo que não seja o caso, depois provavelmente seria possível “reproduzir” o fluxo de eventos de login a partir do banco de dados para fazer a análise. Pode ser diferente se você já tiver anos de dados acumulados.
Sobre contagem, gostaria de mencionar um algoritmo eficiente e fácil de implementar para encontrar os k itens mais frequentes em um stream. Acho que ele é menos conhecido do que deveria.
A Simple Algorithm for Finding Frequent Elements in Streams and Bags
Karp, Shenker & Papadimitriou
https://www.cs.umd.edu/~samir/498/karp.pdf
Sua descrição parece indicar que ele encontra um número fixo de k itens e garante que eles sejam necessariamente os mais frequentes. O resumo parece falar de encontrar itens, em quantidade desconhecida de antemão, que satisfaçam uma condição de serem maiores que um certo valor k.
Parece a diferença entre “encontrar os 100 usuários mais velhos” e “encontrar todos os usuários com mais de 30 anos”; entendi mal o que você disse ou o resumo? Inglês não é minha língua materna, então fiquei confuso.
Então cientistas da computação inventaram uma forma eficiente em memória de estimar o tamanho de um subconjunto.