Porque o CVM foi desenvolvido. Imagine que você foi enviado a uma floresta tropical intocada para realizar um censo de vida selvagem. Cada vez que avista um animal, você tira uma foto. Sua câmera digital registra o número total de fotos, mas seu interesse está apenas no número de animais únicos — aqueles que você ainda não contou. A solução óbvia seria lembrar de cada animal que já viu e comparar cada novo animal à lista, mas essa abordagem se torna inviável com milhares de entradas. Lance Fortnow, cientista da computação do Illinois Institute of Technology, menciona que existem métodos mais inteligentes para esse problema.
A situação complica ainda mais se considerarmos um cenário como o do Facebook, onde é necessário contar o número de usuários distintos que fazem login diariamente, mesmo que alguns façam login de múltiplos dispositivos e em vários momentos. Comparar cada novo login com uma lista que pode chegar a bilhões de entradas é um desafio monumental.
O desafio e a solução
Recentemente, cientistas da computação descreveram um novo método para estimar o número de entradas distintas em uma longa lista, exigindo lembrar apenas de um pequeno número de entradas. O algoritmo CVM, nomeado em homenagem aos seus criadores — Sourav Chakraborty, do Instituto Estatístico Indiano, Vinodchandran Variyam, da Universidade de Nebraska, Lincoln, e Kuldeep Meel, da Universidade de Toronto — representa um avanço significativo na resolução do chamado problema dos elementos distintos. Este problema, que cientistas da computação enfrentam há mais de 40 anos, busca uma maneira eficiente de monitorar um fluxo de elementos e estimar o número de elementos únicos.
Funcionamento do algoritmo CVM
Para ilustrar o problema e como o algoritmo CVM o resolve, imagine que você está ouvindo o audiolivro de Hamlet. A peça contém 30.557 palavras. Quantas são distintas? Para descobrir, você poderia ouvir a peça, anotando cada palavra em ordem alfabética em um caderno e pulando palavras já listadas. Ao final, bastaria contar o número de palavras na lista, mas essa abordagem requer uma memória proporcional ao número de palavras únicas.
Em situações típicas de transmissão de dados, pode haver milhões de itens a serem monitorados. “Você pode não querer armazenar tudo”, disse Variyam. É aqui que o algoritmo CVM oferece uma solução mais prática, usando a randomização como truque principal.
Aplicando o algoritmo CVM
Vamos voltar a Hamlet, mas desta vez sua memória de trabalho — um quadro branco — tem espaço para apenas 100 palavras. Quando a peça começa, você anota as primeiras 100 palavras que ouve, ignorando repetições. Quando o espaço está cheio, você pausa e joga uma moeda para cada palavra. Cara, a palavra permanece na lista; coroa, você a deleta. Após essa rodada preliminar, você terá cerca de 50 palavras distintas.
Em seguida, você inicia a Rodada 1, continuando a ouvir Hamlet e adicionando novas palavras à lista. Se encontrar uma palavra repetida, joga a moeda novamente. Se sair coroa, você a deleta; cara, a palavra permanece na lista. Continua assim até ter 100 palavras no quadro, então remove aleatoriamente cerca de metade delas com base em 100 lançamentos de moeda. Isso conclui a Rodada 1.
Na Rodada 2, você segue o mesmo processo, mas agora é mais difícil manter uma palavra. Para palavras repetidas, joga a moeda novamente: coroa, você a deleta; cara, joga a moeda uma segunda vez, e a palavra só fica se sair cara novamente. Após encher o quadro, remove novamente cerca de metade das palavras. Esse processo continua em rodadas subsequentes, com cada rodada exigindo mais lançamentos consecutivos de cara para manter uma palavra.
Conclusão e precisão
No final, após k rodadas, cada palavra tem a mesma probabilidade de estar na lista: 1⁄2k. Se, por exemplo, você tiver 61 palavras na lista ao concluir Hamlet, e o processo levou seis rodadas, pode dividir 61 pela probabilidade 1⁄26 para estimar o número de palavras distintas — o que resulta em aproximadamente 3.904. Variyam e Meel provaram matematicamente que a precisão dessa técnica escala com o tamanho da memória. Hamlet tem exatamente 3.967 palavras únicas. Em experimentos com memória de 100 palavras, a estimativa média após cinco rodadas foi de 3.955 palavras. Com memória de 1.000 palavras, a média melhorou para 3.964.
“Este é um ótimo exemplo de como, mesmo para problemas muito básicos e bem estudados, às vezes existem soluções muito simples, mas não óbvias, esperando para serem descobertas,” disse William Kuszmaul, da Universidade de Harvard.
Fonte: Quanta Magazine
