Count-Min Sketch 以接受單側誤差來計數串流

資料串流使精確計數變得不切實際：為每個可能項目保留一個計數器，所耗費的記憶體可能超過串流處理器所能負擔。較早的摘要方法改善了空間，但許多界限仍然過於昂貴。

Count-Min Sketch 使用一個小型計數器矩陣與多個雜湊函數。更新是常數時間的增量；點查詢、範圍查詢與內積查詢皆為近似，但快速且記憶體次線性。

Cormode 與 Muthukrishnan 的出版頁面總結了這項改進：對於若干串流問題，空間或時間界限通常從 1/epsilon 平方的因子改善為 1/epsilon。

讓每個誤差都朝上偏

雜湊碰撞被容忍而非被防止，這使記憶體固定且可預測。

取各列的最小值，將許多有雜訊的計數器轉化為有界的上估。

此結構支援多種串流查詢，而不只是單一重擊者報告。

其小巧、可合併的形態，使其適用於遙測、廣告、網路與資料庫。

當近似方法的誤差具有方向性時，它更容易操作；單側誤差讓下游系統能將結果視為安全的上界估計。

Count-Min Sketch 成為串流系統中頻率估計的標準草圖之一。其巧妙之處不在於假裝碰撞不存在；而是安排碰撞，使其損害可量測且為單側。