Streaming Algorithms & Data Engineering
Count-Min Sketch Sizing & Birthday Collision Formula
Size Cormode-Muthukrishnan Count-Min Sketch tables via width CEILING(EXP(1)/eps, 1) and depth CEILING(LN(1/delta), 1), and audit Birthday-Paradox hash collisions 1 - EXP(-n*(n - 1)/(2*M)).
Bound heavy-hitter streaming memory in O(1/eps * LN(1/delta)) counters — and catch Birthday hash collisions!
Tracking exact per-IP or per-SKU frequencies across billions of streaming events overflows RAM, while naive un-salted hashing collides way earlier than engineers expect! Graham Cormode and S. Muthukrishnan’s (2005) Count-Min Sketch guarantees frequency overestimate <= eps * Total_Events with probability >= 1 - delta using a fixed 2D array of Width w = CEILING(EXP(1) / eps, 1) columns by Depth d = CEILING(LN(1 / delta), 1) pairwise-independent hash rows (Total Counters = w * d, independent of distinct key cardinality n!)! Alongside it, auditing raw ID hashes of cardinality n in bucket space M requires the Birthday Paradox bound P_collision ~ 1 - EXP(-(n * (n - 1)) / (2 * M))!
Verify on Relative_Error_eps = 0.001 (B2 = 0.1%), Failure_Prob_delta = 0.01 (B3 = 1%), Distinct_IDs_n = 3,000 (B4), and Raw_Hash_Buckets_M = 10,000,000 (B5): Count-Min Width is CEILING(2.71828 / 0.001, 1) = 2,719 columns, Depth is CEILING(LN(100), 1) = 5 rows, Total Counters = 2,719 * 5 = 13,595 cells (~54.38 KB of 4-byte integers for ANY stream size!), while raw hashing just 3,000 IDs into 10,000,000 buckets already has a 1 - EXP(-8,997,000 / 20,000,000) = 0.3623 (36.23%!) collision probability!
| Streaming Sketch Metric (eps=0.001, delta=0.01, n=3,000, M=10^7) | Formula | Verified Output |
|---|---|---|
| Sketch Table Width (w) | CEILING(EXP(1) / eps, 1) | 2,719 columns |
| Sketch Hash-Row Depth (d) | CEILING(LN(1 / delta), 1) | 5 hash rows |
| Total Sketch Counter Cells (w * d) | w * d | 13,595 counters |
| Birthday Raw-Hash Collision Risk | 1 - EXP(-n * (n - 1) / (2 * M)) | 0.3623 (36.23% Collision!) |
Count-Min Sketch Total Counter Footprint (w * d) Formula
Validate 0 < eps < 1 and 0 < delta < 1.
=LET(ep_e, B2, dl_p, B3, IF(OR(ep_e <= 0, ep_e >= 1, dl_p <= 0, dl_p >= 1), "Require 0 < eps, delta < 1", LET(w_col, CEILING(EXP(1) / ep_e, 1), d_row, CEILING(LN(1 / dl_p), 1), w_col * d_row)))Birthday-Paradox Hash-Collision Probability Formula
Test n = 1 (zero pairs -> exact 0.0000 collision probability) and n >= M (guaranteed 1.0000 pigeonhole collision!).
=LET(n_id, B4, m_sp, B5, IF(OR(n_id < 1, m_sp < 1), "Invalid Hash Space", IF(n_id > m_sp, 1, ROUND(1 - EXP(-(n_id * (n_id - 1)) / (2 * m_sp)), 4))))Try the example
Use the original values or change them to test your understanding.