Count-Min Sketch는 단측 오차를 허용하여 스트림을 집계했다

데이터 스트림은 정확한 집계를 비현실적으로 만들었다. 가능한 모든 항목에 대해 카운터를 유지하는 것은 스트림 프로세서가 가진 것보다 더 많은 메모리를 소모할 수 있었다. 기존의 요약 기법들은 공간을 개선했지만, 많은 경계는 여전히 너무 비쌌다.

Count-Min Sketch는 작은 카운터 행렬과 여러 해시 함수를 사용했다. 갱신은 상수 시간 증가였고, 점, 범위 및 내적 질의는 근사치였지만 빠르고 메모리 측면에서 준선형이었다.

Cormode와 Muthukrishnan의 출판 페이지는 개선점을 요약한다. 여러 스트림 문제에서 공간 또는 시간 경계는 일반적으로 1/엡실론 제곱의 인자에서 1/엡실론으로 개선되었다.

모든 오차가 위쪽으로 향하게 하라

해시 충돌은 방지하는 대신 허용되므로 메모리가 고정되고 예측 가능해진다.

행 전체에서 최솟값을 취하면 많은 잡음 섞인 카운터가 경계가 있는 과대 추정치로 바뀐다.

이 구조는 단일 헤비 히터 보고서뿐 아니라 여러 스트림 질의를 지원한다.

작고 병합 가능한 형태 덕분에 텔레메트리, 광고, 네트워킹 및 데이터베이스에서 실용적이었다.

근사는 오차에 방향이 있을 때 운영하기 더 쉽다. 단측 오차는 다운스트림 시스템이 결과를 안전한 상한 추정치로 취급할 수 있게 한다.

Count-Min Sketch는 스트리밍 시스템에서 빈도 추정을 위한 표준 스케치 중 하나가 되었다. 영리한 움직임은 충돌이 사라지는 척한 것이 아니라, 충돌의 피해가 측정 가능하고 단측이 되도록 충돌을 배치한 것이었다.