An Improved Data Stream Summary: The Count-Min Sketch and Its Applications
Lecture Notes in Computer Science, 2004 · paper · Computer science
Introduces the Count-Min Sketch, a small data structure summarizing data streams that approximately answers point, range and inner-product queries. It also supports finding quantiles and frequent items, improving earlier space and time bounds, typically from 1/ε² to 1/ε.
Checked: PDF from cs.ox.ac.uk, fetched 4 Oct 2026. Page numbers are those of that PDF.
4 findings
Substance The generalised parameter choice is printed "we can set w = ε/b and d = log_b 1/δ for any b > 1". It should be w = b/ε; with b = e this recovers w = ⌈e/ε⌉.
- p. 7 Paragraph after proof of Theorem 1
more generally, we can set w = ϵ/b and d = logb 1/δ
- p. 7 Discussion after Theorem 1
we can set w = ϵ/b and d = logb
Judge's note: In the page 7 image the text reads w = ε/b. My own working: per-row Markov failure is at most 1/(wε), which needs to be ≤ 1/b so that b^{-d} = δ, which gives w = b/ε. With w = b/ε, wd = b ln(1/δ)/(ε ln b), whose derivative is proportional to (ln b − 1)/ln² b. That is zero at b = e, matching the stated cost (2 + e/ε) ln 1/δ. With the printed ε/b, wd is strictly decreasing for b > 1 and the width is below 1. So the formula as printed is wrong; the fix is evident.
Second check: another model agreed
Report a problem with this finding
Substance Fig. 2 gives Count-Min Range query time as "log(n)/ε", but p.10 states "The time to compute the estimate or to make an update is O(log(n) log 1/δ)", i.e. log(n) once the omitted O(log 1/δ) factor is dropped.
- p. 15 Fig. 2, Count-Min Range row, Query Time column
log(n)/ε
- p. 10 After proof of Theorem 4
The time to compute the estimate or to make an update is O(log(n) log 1/δ)
- p. 10 After Theorem 4
The time to compute the estimate or to make an update is O(log(n) log 1
Judge's note: The p.15 table's CM Range row reads space log(n)/ε, update log(n), query log(n)/ε. Section 4.3 (p.10) answers a range query with at most 2 log n point queries, each costing O(log 1/δ), and states the query time as O(log(n) log 1/δ). The Fig. 2 caption says only the O(log 1/δ) factor is omitted, so the query-time entry conflicts with the text. It looks copied from the space column.
Second check: another model agreed
Report a problem with this finding
Wording Both definitions of the parameters read "the error in answering a query is within a factor of ε with probability δ" (p.2 and p.5). Every theorem gives success probability 1 − δ, so δ is the failure probability.
- p. 2 Introduction, desiderata paragraph
within a factor of ε with probability δ
- p. 5 Section 2, last paragraph
within a factor of ε with probability δ
- p. 2 Introduction, para 1
the error in answering a query is within a factor of ε with probability δ
- p. 5 Section 2, last paragraph
answering a query is within a factor of ε with probability δ
Judge's note: I checked the crops of p.2 and p.5: the wording is printed in both places. Theorems 1, 3, 5, 6 and 7 (pp.7, 8, 12, 13) all say 'with probability (at least) 1 − δ', and the depth is d = ⌈ln 1/δ⌉. So the definitional sentence describes δ the wrong way round. It should say 'with probability 1 − δ' or 'with failure probability δ'. Informal wording, but it states the reverse of the theorems.
Second check: another model agreed
Report a problem with this finding
Wording Proof of Theorem 6: "the probability of mistakenly outputting an infrequent item is bounded by 1 − δ, using the union bound". The failure probability should be bounded by δ.
- p. 12 Proof of Theorem 6, last sentence
mistakenly outputting an infrequent item is bounded by 1 − δ, using the union bound
- p. 12 Proof of Theorem 6
is bounded by 1 −δ, using the union bound
Only the authors can say what is right here.
Judge's note: The page 12 image confirms '1 − δ'. Theorem 6 claims that with probability 1 − δ no infrequent item is output, so the failure probability must be at most δ. With δ scaled to δ/||a||_1 per query, the union bound over ||a||_1 queries gives δ. As printed, the bound on the failure probability is the wrong quantity. The theorem still holds once this slip is fixed (compare p.13, where the analogous argument correctly says 'bounded by δ').
Second check: another model agreed
Report a problem with this finding
23 minor (typos and the like; most checked by the judge only)
Reference or label References [6] ("IEEE Transactions on Knowledge and Data Engineering 15(3):529–541, 2003") and [20] ("15(3):541–554, 2003") give two different articles in the same issue page ranges that both include p. 541.
- p. 17 Reference [6]
15(3):529–541, 2003
- p. 18 Reference [20]
15(3):541–554, 2003
Only the authors can say what is right here.
Judge's note: Rests on outside knowledge: that articles in IEEE TKDE start on a new page and that [6] really ends on p. 540. The crops of pp. 17 and 18 confirm both entries read as quoted, so the shared page 541 is visible in the reference list itself. Only the bibliographic record can say which range is off, so this is put to the authors as a query.
Second check: another model agreed
Report a problem with this finding
Reference or label Reference [23] reads "Proceedings of the 40th Symposium on Foundations of Computer Science, pages 189–197, 2000", but reference [14] places the 40th FOCS in 1999 ("40th Annual Symposium on Foundations of Computer Science, pages 501–511, 1999").
- p. 18 Reference [23]
Proceedings of the 40th Symposium on Foundations of Computer Science, pages 189–197, 2000
- p. 17 Reference [14]
Proceedings of the 40th Annual Symposium on Foundations of Computer Science, pages 501–511, 1999
- p. 18 Reference [23]
Proceedings of the 40th Symposium on Foundations of Computer Science, pages 189–197, 2000.
- p. 17 Reference [14]
Proceedings of the 40th Annual Symposium on Foundations of Computer Science, pages 501–511, 1999.
Only the authors can say what is right here.
Judge's note: Rests on outside knowledge: that FOCS 2000 was the 41st symposium. Inside the files, [14] dates the 40th FOCS to 1999, and [15] gives the 24th FOCS as 1983, which is consistent with one symposium a year. So [23] contradicts the paper's own reference list. Whether the edition number or the year is wrong in [23] is for the authors to confirm. Checked the crops of pp. 17 and 18.
Second check: another model agreed
Report a problem with this finding
Wording The introduction says "for the applications we discuss, our constructions strictly improve the space bounds of previous results from 1/ε² to 1/ε". For turnstile heavy hitters, however, Section 5.2 says "the space bounds agree asymptotically but have been improved in constant factors" compared with [8].
- p. 3 Introduction, para 'We will address all these issues'
for the applications we discuss, our constructions strictly improve the space bounds of previous results from 1/ε2 to 1/ε
- p. 13 Section 5.2, Turnstile case discussion
Here, the space bounds agree asymptotically but have been improved in constant fac-
- p. 13 Section 5.2, Cash register comparison
slightly better than our worst case space usage
Only the authors can say what is right here.
Judge's note: I checked p.3 and p.13. On p.13 the turnstile bound agrees asymptotically with [8]. In the cash-register case, [26]'s expected space O(1/ε log 1/(φδ)) is called 'slightly better than our worst case space usage'. So the blanket claim of a strict 1/ε² → 1/ε improvement for all the applications discussed overstates what Section 5.2 reports. The authors should qualify the scope.
Second check: another model agreed
Report a problem with this finding
Wording The introduction claims bounds for "finding Heavy Hitters and Quantiles in the most general data stream model". Section 2, however, defines the 'general case' as the turnstile model with possibly negative a_i, and the turnstile heavy-hitter solution assumes a_i(t) ≥ 0.
- p. 3 Introduction, lower-bound paragraph
(finding Heavy Hitters and Quantiles in the most general data stream model)
- p. 12 Section 5.2, opening
with the restriction that count of any item is never less than zero
- p. 4 Section 2, turnstile cases
We refer to the first of these as the general case, and the second as the non-negative case.
Judge's note: I checked p.3, p.4 (where the general and non-negative cases are defined) and p.12 (where turnstile heavy hitters assume 'count of any item is never less than zero'). The phrase most likely means the turnstile model as opposed to cash register; p.11 also calls turnstile 'the more general turnstile model'. Given the paper's own 'general case' term, though, the wording is ambiguous.
Second check: another model agreed
Report a problem with this finding
Wording The introduction says "Our analysis is simpler, relying only on the Markov inequality", but the proof of Theorem 2 (general case) says "Applying Chernoff bounds tells us that the probability of the median ... being wrong is less than δ^{1/4}".
- p. 4 Introduction, technical nuances bullet 3
Our analysis is simpler, relying only on the Markov inequality.
- p. 8 Proof of Theorem 2
Applying Chernoff bounds tells us that the probability of
Only the authors can say what is right here.
Judge's note: I checked p.4 and p.8. The p.8 bullet ('without recourse to Chernoff bounds') limits the Markov-only analysis to the non-negative/min estimator. The general-case Theorem 2 does use Chernoff, so the unqualified statement in the introduction overstates.
Second check: another model agreed
Report a problem with this finding
Wording The proof of Theorem 1 states the equality "Pr[∀j. a_i + X_{i,j} > a_i + ε||a||_1] = Pr[∀j. X_{i,j} > eE(X_{i,j})]". Only ≤ holds, because the proof establishes only eE(X_{i,j}) ≤ ε||a||_1.
- p. 7 Proof of Theorem 1, third line of the displayed chain
= Pr[∀j. Xi,j > eE(Xi,j)] < e−d ≤ δ
Only the authors can say what is right here.
Judge's note: Reworked on the page 7 image. Since eE(X) ≤ ε||a||_1, the event {X > ε||a||_1} is contained in {X > eE(X)}, so the step is ≤ and not =. I checked the counterexample under the paper's assumptions: n = 3, a = (1,1,1), ε = 0.5, w = 6, d = 1 (any δ ≥ 1/e), with a fully random h. Pr[X > 1.5] = 1/36, while Pr[X > e/3] = 11/36. The step is false as printed, but the bound goes in the needed direction, so Theorem 1 stands.
Second check: another model agreed
Report a problem with this finding
Wording The proof of Theorem 1 prints "Pr[h_j(i) = h_j(k)] ≤ 1/range(h_j) = ε/e", but range(h_j) = w = ⌈e/ε⌉, so 1/range(h_j) ≤ ε/e rather than =.
- p. 7 Proof of Theorem 1, first display
≤1/ range(hj) = ε e
Only the authors can say what is right here.
Judge's note: In the page 7 image the equality sign is printed. Equality holds only when e/ε is an integer. The argument needs only the upper bound, so the result stands. This is a minor slip in a derivation step.
Second check: another model agreed
Report a problem with this finding
Wording The bound for [21] gives sketch size "O(1/ε′² log(n) log(log n/δ))" but the guarantee as "additive error ε||a||_1 with probability 1−δ′". The primed and unprimed parameters are swapped, and δ′ is never defined.
- p. 11 Paragraph on best previous bounds [21]
to give approximations with additive error ε||a||1 with probability 1−δ′
Only the authors can say what is right here.
Judge's note: I checked the page 11 image and searched the text. ε′ is defined on p.10 as the target range-sum accuracy with probability 1 − δ, and δ′ appears nowhere else. Within the one sentence the primes are used inconsistently, so it is unclear which pair the bound refers to.
Second check: another model agreed
Report a problem with this finding
Wording The worst-case space of the existing quantile algorithms ([25,22]) is given as "O(1/ε log(||a||_1/ε))" on p.11. On p.12 the deterministic solution [22] is given as "O(1/ε log(ε||a||_1))".
- p. 11 Disadvantage (4) of quantile-based range sums
The worst case space bound depends on O(1/ε log ||a||1/ε)
- p. 12 Paragraph after Theorem 5
O(1/ε log(ε||a||1)) space for a deterministic solution [22]
- p. 11 Section 4.3, disadvantage (4)
bound depends on O( 1 ε log ||a||1 ε )
- p. 12 Section 5.1, last paragraph
O( 1 ε log(ε||a||1)) space for a deter- ministic solution [22]
Only the authors can say what is right here.
Judge's note: I checked p.11 and p.12. The fraction ||a||_1/ε is printed on p.11 and ε||a||_1 on p.12. The only deterministic, worst-case algorithm cited on p.11 is [22], so the same quantity is printed two ways. The two forms differ by 2 log(1/ε). Only the authors can say which form is intended; I did not rely on outside knowledge of [22].
Second check: another model agreed
Report a problem with this finding
Typo Missing word: "our goal will be limit this dependence" should read "our goal will be to limit this dependence".
- p. 2 Introduction, first paragraph
our goal will be limit this dependence
Judge's note: The crop of p.2 shows the text exactly as quoted.
Second check: none (judge only)
Report a problem with this finding
Typo Unmatched closing parenthesis in "merely a summary—aka a sketch or synopsis [17])—of it".
- p. 2 Introduction, first line
synopsis [17])—of
- p. 2 Introduction, para 1
aka a sketch or synopsis [17])—of
Judge's note: The crop of p.2 shows the stray ')' after [17]. The aside is set off by em-dashes and there is no opening parenthesis.
Second check: none (judge only)
Report a problem with this finding
Typo The frequency moment is printed "F_k(t) = Σ_k (a_i(t))^k", with summation index k. It should be Σ_i.
- p. 3 Introduction, paragraph on lower bounds
Fk(t) = Σk(ai(t))k
Judge's note: In the page 3 image the subscript under Σ is k, the same letter as the exponent and the moment order, which leaves i free. The intended definition Σ_i a_i(t)^k is evident.
Second check: none (judge only)
Report a problem with this finding
Typo Section 6 defines "The (j, k)th entry of the sketch" as Σ_{i:h_k(i)=j} a_i g_k(i), where j is the bucket and k the hash index. This reverses Section 3's count[j, h_j(i_t)], where j is the row/hash index.
- p. 15 Section 6, generic sketch definition
The (j, k)th entry of the sketch is defined to be
- p. 6 Section 3, Update Procedure
count[j, hj(it)] ←count[j, hj(it)] + ct
Judge's note: Checked the p.6 crop and the p.15 image. Each section is consistent within itself, but the roles of the indices swap between sections without comment. A minor notational point.
Second check: none (judge only)
Report a problem with this finding
Typo The proof of Theorem 1 says "Define the variable X_{i,j} (random over the choices of h_i)". X_{i,j} depends on the row hash function h_j, so it should read h_j.
- p. 7 Proof of Theorem 1
(random over the choices of hi)
- p. 7 Proof of Theorem 1
random over the choices of hi
Judge's note: In the page 7 image the text reads h_i. X_{i,j} = Σ_k I_{i,j,k} a_k depends only on h_j, and two lines later the text says 'by pairwise independence of h_j'.
Second check: none (judge only)
Report a problem with this finding
Typo Missing preposition: "which agree the value of that attribute" should read "which agree on the value of that attribute".
- p. 9 Join size paragraph
which agree the value of that attribute
Judge's note: The crop of p.9 shows the text as quoted.
Second check: none (judge only)
Report a problem with this finding
Typo Duplicated word in Section 4.3, disadvantage (2): "sometimes linear in the size size of the structure".
- p. 11 Disadvantage (2)
sometimes linear in the size size of the structure
- p. 11 Sec 4.3, disadvantage (2)
linear in the size size of the structure
- p. 11
high, sometimes linear in the size size of the structure. (
Judge's note: The page 11 image shows 'size size' in disadvantage (2). It is a plain word duplication.
Second check: code check
Report a problem with this finding
Typo Heading "5.2.0.1 Hierarchical Heavy Hitters" uses a paragraph-level number with no 5.2.0, unlike the rest of the numbering.
- p. 13 Heading before HHH paragraph
5.2.0.1 Hierarchical Heavy Hitters
Judge's note: The page 13 image shows the heading '5.2.0.1'. Other paragraph headings ('Cash Register Case.', 'Turnstile Case.') are unnumbered, so this looks like a LaTeX counter showing through. Cosmetic.
Second check: none (judge only)
Report a problem with this finding
Typo Section 6: "These authors additionally used a second hash set of hash functions, h_j" has a stray 'hash' (intended 'a second set of hash functions').
- p. 14 Section 6, second paragraph
a second hash set of hash functions
- p. 14 Section 6, para 3
used a second hash set of hash functions
Judge's note: The page 14 image confirms the wording.
Second check: none (judge only)
Report a problem with this finding
Typo Reference [4] lists the author as "L. Trevisian".
- p. 16 Reference [4]
L. Trevisian
Only the authors can say what is right here.
Judge's note: Rests on outside knowledge: the co-author's name is spelled Luca Trevisan. The page 16 image confirms that 'Trevisian' is printed.
Second check: none (judge only)
Report a problem with this finding
Typo Conclusions: "Also, the CM Sketch can also be naturally extended" uses 'also' twice.
- p. 16 Conclusions, para 2
Also, the CM Sketch can also be
Judge's note: The page 16 image confirms the wording.
Second check: none (judge only)
Report a problem with this finding
Typo Subject-verb disagreement in Sec. 6, p. 16: "The methods in [13,11] as such seems to use fully independent hash functions" (should be "seem").
- p. 16 Sec 6 end
The methods in [13,11] as such seems to use
Judge's note: Checked the crop of PDF p. 16 at the end of Sec. 6. The sentence reads exactly as quoted. The plural subject "methods" takes the singular verb "seems".
Second check: none (judge only)
Report a problem with this finding
Typo Reference [5] misspells "Proceedings": "In Procedings of the International Colloquium on Automata, Languages and Programming (ICALP)".
- p. 17 Reference [5]
In Procedings
- p. 17 Ref [5]
Procedings
Judge's note: Both crops of p. 17 show "Procedings" in italics in reference [5]. Every other entry in the list spells it "Proceedings".
Second check: none (judge only)
Report a problem with this finding
Typo Reference [24] misspells the name Lipschitz: "Extensions of Lipshitz mapping into Hilbert space".
- p. 18 Reference [24]
Extensions of Lipshitz mapping into Hilbert space
- p. 18 Ref [24]
Extensions of Lipshitz mapping
Judge's note: Checked the crops of p. 18; the text reads "Lipshitz". Lipschitz is the standard spelling of the name. The reviewers also say the published title is "mappings into a Hilbert space", but that rests on outside knowledge and was not used here; only the misspelling is confirmed.
Second check: none (judge only)