Papers
An Improved Data Stream Summary: The Count-Min Sketch and its Applications
Graham Cormode, S. Muthukrishnan · Journal of Algorithms, vol. 55, pp. 58-75, abril de 2005 (fonte lida: preprint de 16/12/2003, Elsevier Science), 2005
O problema: resumir um fluxo de atualizações em espaço sublinear
O artigo parte de um vetor a de dimensão n, que começa zerado e é alterado por um fluxo de pares (i, c): a cada atualização, o valor c é somado à posição i. Em qualquer instante pode-se perguntar por funções desse vetor. Três consultas são centrais: a consulta pontual, que pede o valor de uma posição; a consulta de intervalo, que pede a soma das posições entre l e r; e o produto interno entre dois vetores, usado, por exemplo, para estimar o tamanho de um join entre relações. Os autores distinguem o caso em que as atualizações são sempre positivas (cash register) do caso em que também podem ser negativas (turnstile). O turnstile tem duas variações: o caso geral, em que posições podem ficar negativas, e o caso não negativo, em que a aplicação garante que nenhuma posição fica abaixo de zero. Como a memória deve ser bem menor que n, o resumo (sketch) só pode dar respostas aproximadas, com parâmetros ε e δ: o erro fica dentro de um limite com probabilidade alta. Segundo o artigo, os sketches anteriores tinham limitações: o espaço crescia com um fator da ordem de 1/ε², muitos exigiam tempo linear no tamanho do sketch a cada atualização, usavam funções de hash com independência forte e serviam a um único agregado pré-definido. O Count-Min Sketch foi proposto para atacar essas limitações: espaço proporcional a 1/ε, atualização bem mais rápida que o tamanho do sketch, apenas hash com independência par a par e uso em várias consultas.
A estrutura: uma matriz de contadores e d funções de hash
Um Count-Min Sketch com parâmetros (ε, δ) é uma matriz de contadores com d linhas e w colunas, toda zerada no início. A largura é w = ⌈e/ε⌉, em que e é a base do logaritmo natural, e a profundidade é d = ⌈ln(1/δ)⌉. Cada linha j tem sua própria função de hash h_j, que leva um item do universo {1…n} a uma coluna em {1…w}, sorteada de uma família de funções com independência par a par. Para processar a atualização (i, c), o algoritmo soma c ao contador da coluna h_j(i), em cada uma das d linhas; ou seja, só d contadores são tocados, e o custo da atualização depende de d, não do tamanho total da matriz. O espaço é o de w·d contadores mais as d funções de hash, e cada função par a par pode ser guardada com duas palavras. O nome vem das duas operações usadas na consulta pontual: primeiro contar (os contadores acumulados) e depois calcular o mínimo entre as linhas. Itens diferentes podem cair na mesma coluna de uma linha, o que se chama colisão; cada contador guarda, portanto, o valor do item consultado somado aos valores de outros itens que colidiram com ele. Essa observação é a chave da análise da próxima seção. O fato de a matriz ser uma soma linear das atualizações também a torna fácil de combinar entre locais distribuídos, como o artigo observa para sketches em geral.
Consulta pontual: o mínimo entre as linhas e a garantia de erro
Para estimar o valor a_i no caso não negativo, o algoritmo devolve o mínimo, entre as d linhas, do contador na coluna h_j(i). O Teorema 1 afirma duas coisas: a estimativa nunca é menor que o valor real a_i, e, com probabilidade de pelo menos 1 − δ, ela não passa de a_i + ε·||a||₁, em que ||a||₁ é a soma dos valores absolutos do vetor. O erro é, portanto, de um só lado, para cima. A prova segue a intuição das colisões: em cada linha, o contador vale a_i mais a soma dos itens que colidem com i, e, como as atualizações são não negativas, esse excesso nunca é negativo, o que garante que o mínimo não subestima. Com hash par a par, a chance de dois itens colidirem numa linha é de no máximo ε/e, então o excesso esperado é de no máximo (ε/e)·||a||₁. Pela desigualdade de Markov, o excesso passa de ε·||a||₁ numa linha com probabilidade menor que 1/e; para que o mínimo passe do limite, todas as d linhas precisam falhar, o que ocorre com probabilidade menor que e^(−d), no máximo δ. O artigo destaca que usar só Markov, e não variância com Chebyshev e Chernoff, é o que reduz a dependência de 1/ε² para 1/ε e deixa as constantes pequenas. O tempo de consulta e de atualização é O(ln(1/δ)). Se os valores puderem ser negativos, usa-se a mediana (Teorema 2): o erro fica entre −3ε·||a||₁ e +3ε·||a||₁, nos dois sentidos, mas com probabilidade de pelo menos 1 − δ^(1/4), uma garantia mais fraca que a do caso não negativo.
Produto interno e consultas de intervalo
Para o produto interno de dois vetores não negativos, a e b, mantêm-se dois sketches com as mesmas funções de hash. Em cada linha, multiplica-se coluna a coluna e soma-se; a estimativa é o mínimo entre as linhas. O Teorema 3 diz que ela nunca fica abaixo do valor real e, com probabilidade de pelo menos 1 − δ, não passa dele mais ε·||a||₁·||b||₁, usando espaço O((1/ε)·log(1/δ)). Isso permite estimar o tamanho de um join entre duas relações, com a_i e b_i contando as tuplas que têm o valor i em cada uma. O artigo adverte que os métodos anteriores (tug-of-war) davam garantia em termos da norma L2, que pode ser bem menor que a L1, mas com espaço da ordem de 1/ε². Para intervalos, escrever a consulta como produto interno com um vetor indicador faria o erro crescer com o tamanho do intervalo e o custo depender de r − l. Em vez disso, adota-se a ideia de intervalos diádicos, de tamanho potência de 2: mantêm-se log₂ n sketches, um por tamanho, e cada atualização entra em todos. Qualquer intervalo é coberto por no máximo 2·log₂ n intervalos diádicos, cada um consultado como uma consulta pontual, e as respostas são somadas. O Teorema 4 dá erro de até 2ε·log n·||a||₁ com probabilidade de pelo menos 1 − δ. Para obter erro ε′·||a||₁, escolhe-se ε = ε′/(2·log n), o que leva a espaço O((log²n/ε′)·log(1/δ)).
Aplicações, comparação com o estado da arte e limites
Com o sketch como bloco básico, o artigo melhora os limites de dois problemas. Nos quantis aproximados no modelo turnstile, a busca binária por intervalos cuja soma atinge uma fração do total passa a usar as somas de intervalo do Count-Min no lugar de Random Subset Sums, e o espaço cai de dependência em 1/ε² para 1/ε (Teorema 5). Nos heavy hitters, itens com frequência acima de uma fração φ do total, no caso cash register mantém-se o total ||a||₁ e uma heap de candidatos cujo valor estimado supera o limite. Como o sketch nunca subestima, nenhum heavy hitter é perdido, e, com probabilidade de pelo menos 1 − δ, nenhum item abaixo de (φ − ε)·||a||₁ é devolvido. No caso turnstile não negativo (nenhuma contagem fica abaixo de zero), desce-se pela hierarquia diádica, dividindo os intervalos acima do limite, e todo item com frequência de pelo menos (φ + ε)·||a||₁ é devolvido, com certeza. A comparação com os métodos anteriores mostra que, para consultas pontuais, o Count Sketch tinha espaço da ordem de 1/ε², enquanto o Count-Min tem 1/ε, com atualização e consulta em O(log(1/δ)). O artigo também reconhece limites: as estimativas dependem da norma L1, e não da L2, o que as torna menos justas em consultas individuais, e o Count-Min não é eficaz para estimar normas, usadas em correlações e na contagem de itens distintos; projetar sketches tão simples quanto ele para esses casos fica como problema em aberto.
Veja as ideias em ação
Pratique na escola de System Design os desenhos que usam este paper.