DataSketches.Frequencies.CountMin

Count-Min sketch for approximate frequency estimation.

"How many times has this particular item appeared?" — imagine counting ad impressions per user, or requests per API key, when there are too many distinct items to keep an exact counter for each one. Count-Min gives you an approximate count using fixed memory.

It is conservative: estimates may overcount (due to hash collisions) but never undercount. If an item truly appeared 100 times, the sketch will report >= 100. This makes it safe for rate limiting and frequency capping — you might act slightly early, but never too late.

Parameters

• epsilon (ε): error tolerance. The estimate is within ε * N of the true count with high probability, where N is the total insertions.

• delta (δ): failure probability. The probability the estimate exceeds the error bound is at most δ.

Space used is O(1/ε * log(1/δ)).

Hashing

Items must be pre-hashed to Word64. Apply a hash function to your domain types before calling insert.

Implementation

Backed by a C implementation (cbits/countmin.c) behind a ForeignPtr. All sketch memory lives outside the GHC heap.

Usage

import qualified DataSketches.Frequencies.CountMin as CM
import Data.Hashable (hash)

main :: IO ()
main = do
  sk <- CM.mkCountMinSketch 0.001 0.01  -- ε=0.1%, δ=1%
  mapM_ (\_ -> CM.insert sk 42) [1..500]
  freq <- CM.estimate sk 42
  putStrLn $ "frequency ≈ " ++ show freq  -- ≈ 500

Mergeability

Fully mergeable via merge. Both sketches must have been constructed with the same ε and δ (i.e. identical dimensions).