count-sketch · research · also Count Sketch, Count-Sketch

CountSketch

CountSketch is a randomized linear summary that estimates individual frequencies using hashed buckets, random signs and the median of signed row estimates.

Related Observatory article: Read on hesela.com

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

  1. Charikar, Chen and Farach-Colton. Finding Frequent Items in Data Streams. Sections 3-4, including additive sketches and frequency changes. (accessed 2026-11-20)
  2. Cormode, Garofalakis, Haas and Jermaine. Synopses for Massive Data. Author manuscript, sections 5.2, 5.3.2 and 5.3.2.1. (accessed 2026-11-20)
  3. Hesela. Exact signed-frequency and expiration examples, with executable tests. Constructed finite maps, not random-hash validation. (accessed 2026-11-20)
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]

JSON: /data/terms/count-sketch.json

Published by Hesela team · Updated

Report a correction · Editorial standards · Reuse guidance

Cite this page
Hesela team. CountSketch. Hesela. 2026-11-20. https://hesela.dev/terms/count-sketch/