Today we explore the count sketch, another frequency estimation data structure, and see how to count the number of distinct items in a stream in a shockingly small number of bits.
Readings
- Moses Charikar et al. Finding Frequent Items in Data Streams. Flajolet et al. HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm
Links