Count-Min Sketch
A Count-Min Sketch estimates frequencies with multiple hash functions, using sublinear space at the cost of overestimation; it is used for stream frequency statistics.
Purpose
To provide space-efficient approximate frequency statistics over data streams.
Mechanism
A d-row, w-column counting matrix. Update x: for each row i, count[i][h_i(x)]+=1. Query x: take min_i count[i][h_i(x)]. Overestimation probability is at most we^(-d), with error ≤ε||f||_1.
Use cases
- Stream statistics
- Frequency estimation
- Top-k detection