Finding Frequent Items in Data Streams
Theoretical Computer Science, 2004 · paper · Computer science
Presents a one-pass streaming algorithm using a data structure called Count Sketch to estimate the most frequent items with limited memory. It gives better space bounds than prior methods for several natural frequency distributions and extends to finding items with the largest frequency change between two streams.
2 findings
Wording "Lemma 2. E[v_i^{>k}[q]] = (Σ_{q'=k+1}^{m} n_{q'}^2)/b" is printed as an equality, but with A_i^{>k}[q] = {q′: q′ ≠ q, q′ > k, h_i[q′] = h_i[q]} it holds only as ≤ when q is not among the top k.
- p. 7 Lemma 2
Lemma 2. E[v_i^{>k}[q]] = (Σ_{q'=k+1}^{m} n_{q'}^2)/b.
- p. 6 Section 4, definition of A_i^{>k}[q]
A_i^{>k}[q] = {q′: q′ ≠ q, q′ > k, h_i[q′] = h_i[q]}
Only the authors can say what is right here.
Judge's note: Definition read on PDF p6 and Lemma 2 on PDF p7. Reworked: by pairwise independence Pr[h_i[q']=h_i[q]] = 1/b for q' ≠ q, so E[v_i^{>k}[q]] = (Σ_{q'>k, q'≠q} n_{q'}^2)/b. For q > k this is the printed value minus n_q^2/b. Counterexample: m=3, k=1, b=2, n=(5,2,1), q=2 gives E = 1/2, while the printed formula gives 5/2. The lemma is stated for arbitrary q with no restriction. Rated S3 rather than S1 because Lemma 2 is used only through Markov's inequality for (1), which needs just the upper bound, so Lemmas 3–5 and Theorem 1 stand; '=' should be '≤'.
Second check: another model agreed
Report a problem with this finding
Wording Text calls [14] "the recent unpublished manuscript of Karp et al. [14]" while the reference list gives it as published: "ACM Transactions on Database Systems 28 (2003) 51–55".
- p. 11 Section 4.1, paragraph after Table 1
recent unpublished manuscript
- p. 13 Reference [14]
ACM Transactions on Database Systems 28 (2003) 51–55
- p. 11 Section 4.1, paragraph after Table 1
the recent unpublished manuscript of Karp et al. [14]
- p. 11 Sec. 4.1, after Table 1
recent unpublished manuscript of Karp et al. [14]
Judge's note: Both confirmed on the images (PDF p11 body text; PDF p13 reference [14]). This is an internal inconsistency within the paper: the body text was not updated when the reference entry was. No correction notice is among the files.
Second check: another model agreed
Report a problem with this finding
7 minor (typos and the like; most checked by the judge only)
Wording Introduction states the guarantees strictly ("frequency n_i > (1−ε)n_k"; "every item o_i with n_i > (1+ε)n_k"), whereas Lemma 5 says "occur at least (1 − ε)n_k times" and "all elements with frequencies at least (1 + ε)n_k".
- p. 2 Section 1, APPROXTOP definition and following paragraph
every item oi with ni > (1+ε)nk
- p. 8 Lemma 5
all elements with frequencies at least (1 + ε)nk occur amongst the estimated top k elements
Judge's note: Both wordings confirmed on the images of PDF p2 and p8. The Lemma 5 proof argues only for elements whose counts "differ by more than 16γ", so the boundary case is treated loosely. The difference concerns boundary ties only and does not affect the asymptotic result; either form could be intended.
Second check: another model agreed
Report a problem with this finding
Wording Section 3.1 writes "E[c·s[q_i]] = E[Σ_{j=1}^{m}(n_j · s[q_j] · s[q_i])] = n_i", indexing stream items q_j (defined for j = 1..n) where objects o_j (j = 1..m, with counts n_j) are meant.
- p. 4 Section 3.1, second paragraph
(n_j · s[q_j] · s[q_i])] = n_i
- p. 2 Section 1, definitions
Let object o_i occur n_i times in S
Judge's note: Formula confirmed on the PDF p4 image; definitions of q_i (stream elements) and o_i/n_i (objects and counts) confirmed on PDF p2. The sum over j = 1..m with weights n_j only makes sense over objects. The paper announces conflating q with its index only at the start of Section 4 (PDF p6), after this formula. Notational looseness; the meaning is recoverable.
Second check: another model agreed
Report a problem with this finding
Wording Text says "The bounds for the two algorithms are compared in Table 1" but Table 1 is captioned "Comparison of space requirements for SAMPLING, KPS and our algorithm" with three columns; "KPS" is never defined.
- p. 10 Section 4.1, last paragraph of the page
The bounds for the two algorithms are compared in Table 1.
- p. 11 Table 1 caption and column header
Comparison of space requirements for SAMPLING, KPS and our algorithm
- p. 13 Reference [14]
R. Karp, S. Shenker, C.H. Papadimitriou
Judge's note: Confirmed on PDF p10 (pointer sentence) and PDF p11 (Table 1 with SAMPLING, KPS and COUNT SKETCH columns). A text search finds "KPS" only in the table caption and header. The paragraph after the table ("In addition, we compare our results with ... Karp et al. [14]") informally explains the third column, so this is a minor labelling and wording gap. The point about author order in [14] (Karp, Shenker, Papadimitriou) is not a defect in itself.
Second check: another model agreed
Report a problem with this finding
Typo Subject-verb disagreement: "A summary of our final results are as follows" should read "is as follows".
- p. 2 Section 1, paragraph after the APPROXTOP definition
A summary of our final results are as follows
Judge's note: Read on the page image (PDF p2, journal p4), last paragraph. The text is as quoted. Purely grammatical.
Second check: none (judge only)
Report a problem with this finding
Typo Typo: "most frequent elements can only by preceded by elements" should read "can only be preceded by".
- p. 9 Section 4.1, first paragraph
can only by preceded by elements
- p. 9 Section 4.1, first paragraph
most frequent elements can only by preceded by elements
Judge's note: Confirmed on the full page image of PDF p9, Section 4.1, first paragraph.
Second check: none (judge only)
Report a problem with this finding
Typo Missing words: "the actual distribution of search engine queries is less than 1 [17]" — the Zipf parameter of the distribution is meant.
- p. 10 Section 4.1, last paragraph on the page
distribution of search engine queries is less than 1
- p. 10 Section 4.1, last sentence of the page
the actual distribution of search engine queries is less than 1 [17]
Judge's note: Confirmed on the PDF p10 image, last sentence. The preceding sentence refers to "Zipfian distributions with parameter less than 1", so the meaning is recoverable; words such as "Zipf parameter of the" are missing.
Second check: none (judge only)
Report a problem with this finding
Typo Subject-verb disagreement: "this give the COUNT SKETCH algorithm an advantage" should read "this gives".
- p. 12 Section 5, first paragraph
this give the
Judge's note: Confirmed on the PDF p12 image, Section 5, first paragraph.
Second check: none (judge only)