Bloom filter

TBA

Count min sketch

count sketch is a type of dimensionality reduction

CM sketch is a data structure that count the frequency of each event in sub-linear space, at the expense of probable overcounting due to collision.

Use cases

• identify heavy hitter (Google to identify hot keywords)
  • to get the list of hot keywords: need to combine with other data structure, e.g. Misra-Gries, or iterate through the event universe!
• rate limiting
• Database Query Planners: Estimating the size of table joins to compute efficient query execution paths

Implementation

• The data structures is a 2d int array of w columns and d rows, init to 0. Each row has its own separate hash function h_i (h_i output range is 0..d).
• Add an item: when it receives a new record for event type E, for each row i, we increase the counter at column h_i(E), i.e. ++table[i][h_i(E)]
• Query: to estimate the frequency of event E, take min_i {table[i][h_i(E)]}
  • why take min? hash collision is very likely because the event universe size is likely to be much bigger than d → take min to minimize the chance of overestimation
  • CMS doesn’t underestimate but can overestimate!
• Remove: should avoid because the counters are “shared” between different event types due to hash collision → decrement may cause underestimate…
  • if need removal, try other solutions: Count-Mean-Min sketch, counting bloom filter, etc.

Accuracy analysis

parameters can be chosen deliberately to get better estimate:

• w = upper_bound(e / eps)
• d = upper_bound(ln(1 / sigma))
• this guarantees that for a query of event E, assume the true frequency is f_E, then the probability than f_E ≤ answer ≤ f_E * eps * N is (1 - sigma) (N is the number of records processed so far)