CountSketch
CountSketch is a randomized linear summary that estimates individual frequencies using hashed buckets, random signs and the median of signed row estimates.
Each row adds sign(key) times the update to one bucket; a query multiplies that bucket by the same sign before taking the row median. Error can be positive or negative. The counter array alone answers supplied-key queries; discovering frequent identities needs an additional mechanism. [1]
For a fixed query and frequency vector, standard bounds scale with its Euclidean norm, not the queried count alone. At a common failure probability, the usual bounds need width proportional to 1/epsilon^2 for CountSketch versus 1/epsilon for ordinary Count-Min. A smaller norm alone therefore does not establish a winner at equal memory. They require suitable random bucket/sign families and independent row repetitions; they are not deterministic guarantees for every key and time. [2]
Compatible arrays add or subtract when dimensions, key encoding and bucket/sign maps agree and arithmetic does not overflow or saturate. Combine arrays, not their median estimates. Subtracting a known contribution is different from discovering what to remove. [1]
In a constructed collision, true counts x=5 and y=3 yield an x estimate of 2 with opposite signs or 8 with matching signs in every row. These fixed maps illustrate two-sided error, not its probability. An identical final count vector can also represent different event-time histories. [3]
Relations
- related
- Turnstile stream, Count-Min sketch
Citations
- Charikar, Chen and Farach-Colton. Finding Frequent Items in Data Streams. Sections 3-4, including additive sketches and frequency changes.
- Cormode, Garofalakis, Haas and Jermaine. Synopses for Massive Data. Author manuscript, sections 5.2, 5.3.2 and 5.3.2.1.
- Hesela. Exact signed-frequency and expiration examples, with executable tests. Constructed finite maps, not random-hash validation.
Sources & caveats
- The original paper's sections 3-4 describe CountSketch, candidate tracking and subtraction between streams. Its top-item algorithm is more than a counter array. [1]
- The linked survey manuscript contains placeholder cover metadata; no publication date or DOI is inferred from that cover. [2]
- The exact examples use BigInt and deliberately chosen finite maps. They implement neither production hashing nor an empirical error study. [3]