O Count-Min Sketch contava fluxos aceitando erro unilateral

Os fluxos de dados tornavam a contagem exata impraticável: manter um contador para cada item possível poderia custar mais memória do que o processador de fluxo tinha. Resumos mais antigos melhoravam o espaço, mas muitos limites ainda eram caros demais.

O Count-Min Sketch usava uma pequena matriz de contadores e várias funções de hash. As atualizações eram incrementos em tempo constante; as consultas pontuais, de intervalo e de produto interno eram aproximadas, mas rápidas e sublineares em memória.

A página de publicação de Cormode e Muthukrishnan resume a melhoria: para vários problemas de fluxo, o limite de espaço ou de tempo tipicamente melhorava de um fator de 1/epsilon ao quadrado para 1/epsilon.

Fazer todo erro apontar para cima

As colisões de hash são toleradas em vez de evitadas, o que torna a memória fixa e previsível.

Tomar o mínimo entre as linhas transforma muitos contadores ruidosos em uma superestimativa limitada.

A estrutura suporta várias consultas de fluxo, não apenas um único relatório de itens frequentes.

Seu formato pequeno e mesclável a tornou prática para telemetria, publicidade, redes e bancos de dados.

A aproximação é mais fácil de operar quando seus erros têm uma direção; o erro unilateral permite que os sistemas a jusante tratem o resultado como uma estimativa superior segura.

O Count-Min Sketch tornou-se um dos sketches padrão para estimativa de frequência em sistemas de streaming. O movimento inteligente não foi fingir que as colisões desaparecem; foi organizar as colisões de modo que seu dano fosse mensurável e unilateral.