The Space Complexity of Approximating the Frequency Moments
Journal of Computer and System Sciences, 1999 · paper · Computer science
Studies the memory that randomized streaming algorithms need to approximate frequency moments of a sequence. It shows the first three moments (F0, F1, F2) can be approximated in logarithmic space, while moments Fk for k≥6 require polynomial space.
Checked: PDF from web.math.princeton.edu, fetched 4 Oct 2026. Page numbers are those of that PDF.
5 findings
Substance In the Fact on p.5 the right-hand side is printed as n^{1−1/k}(Σ_{i=1}^{k} m_i^k)^2. The upper limit should be n, as in the last line of the proof (Σ_{i=1}^{n} m_i^k)^2 and in its use as F_k^2.
- p. 5 Section 2.1, statement of Fact
≤ n^{1−1/k} (Σ_{i=1}^{k} m_i^k)^2
- p. 5 Fact statement
n^{1-1/k} (sum_{i=1}^{k} m_i^k)^2
- p. 5 Fact (displayed inequality)
n1−1/k (Σ_{i=1}^{k} m_i^k)^2
- p. 5 Fact (statement)
≤n1−1/k k X i=1 mk i !2
Only the authors can say what is right here.
Judge's note: Page 5 image: the upper limit is clearly k. Read literally, the Fact is false. With n=3, k=2, m=(1,1,5): the left side is 7*127=889, while the printed right side is about sqrt(3)*4≈6.93. With the limit n, the right side is sqrt(3)*729≈1263, so the corrected Fact holds and Theorem 2.1 is unaffected. This is a misprint in a stated inequality.
Second check: another model agreed
Report a problem with this finding
Substance The Fact in the proof of Theorem 2.1 is printed as (∑_{i=1}^n m_i)(∑_{i=1}^n m_i^{2k−1}) ≤ n^{1−1/k}(∑_{i=1}^k m_i^k)^2. The upper limit on the right-hand sum is k, but the proof shows the bound with the sum running to n.
- p. 5 Fact in the proof of Theorem 2.1
(∑_{i=1}^n m_i)(∑_{i=1}^n m_i^{2k−1}) ≤ n^{1−1/k}(∑_{i=1}^k m_i^k)^2
Only the authors can say what is right here.
Judge's note: I read the Fact and its proof on page image p.5. The right-hand sum's upper limit is printed as k. Every line of the proof that follows, including the last one, has ∑_{i=1}^n m_i^k. I reworked the counterexample against the stated assumption (n positive reals). With n=4, k=2 and all m_i=1, the left side is 4*4=16. The printed right side is 2*(1+1)^2=8, so the printed inequality fails. With the limit n, the right side is 2*16=32 and the inequality holds. The Fact is false as printed, though the proof establishes the version summed to n, which is the one used for Var(Y_i). Theorem 2.1 therefore still stands. This looks like a typesetting slip.
Second check: another model agreed
Report a problem with this finding
Wording The introduction (p.2) says "We prove that for every k > 0, Fk can be approximated randomly using at most O(n^{1−1/k} log n) memory bits", but Theorem 2.1 (p.3) is stated and proved only for "every k ≥ 1".
- p. 2 Introduction, last paragraph
We prove that for every k > 0, Fk can be approximated randomly using at most O(n1−1/k log n) memory bits.
- p. 3 Theorem 2.1
For every k ≥ 1, every λ > 0 and every ϵ > 0
- p. 2 Introduction, last paragraph
We prove that for every k > 0, Fk can be approximated randomly using at most
- p. 3 Theorem 2.1 statement
For every k ≥ 1, every λ > 0 and every ϵ > 0 there exists a randomized algorithm
Judge's note: Pages 1–5 viewed. Page 1 defines Fk for every k ≥ 0, real or integer. The concluding remarks (text line ~1053) list non-integral k < 2 as open. The proof of Theorem 2.1 uses a^k − b^k ≤ (a−b)k a^{k−1} (p.5). That inequality fails for 0<k<1: with k=1/2, a=4, b=1 the left side is 1 and the right side is 0.75. The power-mean step in the Fact also needs k ≥ 1. No other result in the paper covers 0<k<1. The theorem itself stands; the introduction states a wider range than it proves. Fix: "k ≥ 1".
Second check: another model agreed
Report a problem with this finding
Wording Theorem 2.2 (p.6) says "finite field operations on elements of O(log n + log n) bits". The theorem's space bound and the proof (p.7, "Z can be computed using only O(log n + log m) bits") give log n + log m.
- p. 6 Theorem 2.2, last sentence
finite field operations on elements of O(log n + log n) bits
- p. 6 Theorem 2.2 statement, last sentence
finite field operations on elements of O(log n + log n)
- p. 7 Proof of Theorem 2.2
Z can be computed using only O(log n + log m) bits
- p. 6 Theorem 2.2 statement
elements of O(log n + log n)
Judge's note: Pages 6 and 7 viewed. The running sum Z can be as large as m, so the operands need about log m bits. As printed, the term is duplicated; it should read O(log n + log m).
Second check: another model agreed
Report a problem with this finding
Wording Lemma 3.5 conditions on "s − 1 pairwise disjoint t-subsets I′r ⊂ N", but the blocks I_r of the partition have cardinality 2t − 1 (p. 11), so I′r should be (2t−1)-subsets.
- p. 12 Lemma 3.5 statement
For any set of s − 1 pairwise disjoint t-subsets I′r ⊂ N
- p. 11 Definition of distribution µ
|Ij| = 2t − 1 for each 1 ≤ j ≤ s
- p. 12 Lemma 3.5
pairwise disjoint t-subsets I′ r ⊂ N
- p. 12 Lemma 3.5
pairwise disjoint t-subsets I′
Judge's note: Page 11 defines n=(2t−1)s+1 and |I_j|=2t−1. Page 11 also defines a t-subset as a subset of cardinality t. The Lemma 3.5 proof on page 12 needs I_j ∪ {x} to have 2t elements, which holds only if each I′r has 2t−1 elements. Example with s=2, t=16: n=63; removing one 31-element block leaves 32=2t elements, while removing a 16-element block would leave 47.
Second check: another model agreed
Report a problem with this finding
11 minor (typos and the like; most checked by the judge only)
Wording On p.4, l is the value of the sampled element ("Suppose that ap = l"). On p.6 the sampled element itself is written "al" ("choose the member al of the sequence A ... as a1"), which under the earlier notation would mean the element at position l.
- p. 4 Proof of Theorem 2.1
Suppose that ap = l ( ∈N = {1, 2, . . . , n}.)
- p. 6 Proof of Theorem 2.1, unknown-m implementation
choose the member al of the sequence A used in the computation of X as a1
Judge's note: Pages 4 and 6 viewed. The symbol l changes meaning without notice. The intended meaning (the currently sampled element) can be inferred, so this is minor.
Second check: another model agreed
Report a problem with this finding
Wording Proposition 3.9(i) says that for 'a sequence of at most m elements of N = {1, 2, . . . , n}', any randomized algorithm 'must use at least Ω(log n) memory bits'. It states no lower bound on m relative to n, yet the proof relies on 'the construction in the proof of Proposition 3.7', whose sequences have length n/2.
- p. 16 Proposition 3.9, opening and part (i)
Let A be a sequence of at most m elements of N = {1, 2, . . . , n}.
- p. 16 Proposition 3.9(i)
must use at least Ω(log n) memory bits.
- p. 17 Proof of Proposition 3.9(i)
the construction in the proof of Proposition 3.7
Only the authors can say what is right here.
Judge's note: I checked the crops on p.16 and p.17. Proposition 3.7 (text line 982) uses sequences of exactly n/2 elements. The proof of 3.9(i) applies that construction A(G1,G2), which needs m ≥ n/2. I found no assumption anywhere in the paper relating m to n. I checked the counterexample against the stated assumptions and it holds: with m=1, one bit recording whether any element has arrived gives F0 exactly, so the Ω(log n) lower bound fails when n grows with m fixed. The intended regime (m at least about n/2) is clear from the proof, and the result stands under that implicit hypothesis. The defect is a missing hypothesis in the statement, so I rated it minor.
Second check: another model agreed
Report a problem with this finding
Typo On p.6, "the median Yi supplies a good estimate" should read "the median Y".
- p. 6 Proof of Theorem 2.1, first paragraph
the median Yi supplies a good estimate
Judge's note: Page 6 image shows the subscript i. Page 4 defines the output as the median Y of the Yi, and page 7 also says "the median Y".
Second check: none (judge only)
Report a problem with this finding
Typo On p.7, Z is defined as "Z = Σ_{l=1}^{n} ϵ_i m_i": the summation index is l but the summand uses i. It should read Σ_{i=1}^{n} ϵ_i m_i.
- p. 7 Proof of Theorem 2.2, definition of Z
Z = Σ_{l=1}^n ε_i m_i
- p. 7 Proof of Theorem 2.2, definition of Z
Z = Σ_{l=1}^{n} ϵ_i m_i
Judge's note: Page 7 image confirms the subscript l=1 with summand ϵ_i m_i. The following E(X) display sums over i.
Second check: none (judge only)
Report a problem with this finding
Typo In the E(X) display on p.7 the lower limit of the inner sum is printed "i−1" instead of "i=1".
- p. 7 Proof of Theorem 2.2, display for E(X)
(Σ_{i−1}^n ε_i m_i)^2
- p. 7 Proof of Theorem 2.2, display for E(X^2)
1≤i<j≤j
- p. 7 expectation of X
i−1
- p. 7 E(X) formula
i−1 ϵimi
Judge's note: Page 7 image shows i−1 under the sigma in E((Σ ϵ_i m_i)^2). The other sums on the same line use i=1. This cluster also lists the "1≤i<j≤j" range, which is handled in C015.
Second check: none (judge only)
Report a problem with this finding
Typo In the E(X^2) display on p.7 the summation range is printed "1≤i<j≤j"; it should be 1≤i<j≤n, as in the Var(X) line.
- p. 7 Proof of Theorem 2.2, display for E(X^2)
1≤i<j≤j
- p. 7 expectation of X
i−1
Judge's note: Page 7 image shows j≤j. With the range corrected, the derivation holds: Var = Σm^4 + 6S − (Σm^4 + 2S) = 4S ≤ 2F2^2. The "i−1" item listed here is handled in C014.
Second check: none (judge only)
Report a problem with this finding
Typo Distinct coordinates written with non-strict inequalities: "four distinct coordinates 1 ≤ i1 ≤ . . . ≤ i4 ≤ n" (should be i1 < … < i4).
- p. 7 Proof of Theorem 2.2, definition of four-wise independence
four distinct coordinates 1 ≤ i1 ≤ . . . ≤ i4 ≤ n
Judge's note: Page 7 image confirms the ≤ signs; 'distinct' makes the intended meaning clear, so this is cosmetic.
Second check: none (judge only)
Report a problem with this finding
Typo Unbalanced brackets in the Remark after Theorem 2.2: "O( log(1/ϵ)/λ² (log n + log log m + log(1/λ))": the large parenthesis opened after O is never closed.
- p. 7 Remark after proof of Theorem 2.2
(log n + log log m + log(1/λ)) by applying
Judge's note: In the crop, the large parenthesis after O comes before the fraction, and no closing large parenthesis follows λ². The remaining brackets give three openings ('(' after O, '(log n', 'log(') against two closings ('))').
Second check: none (judge only)
Report a problem with this finding
Typo In the E(X) display of the proof of Theorem 2.2, the lower limit of the first sum is printed "i−1" instead of "i=1".
- p. 7 Proof of Theorem 2.2, E(X) display
Σ_{i−1}^{n} ϵ_i m_i
Judge's note: The page 7 image shows a minus sign under the first Σ inside E(·); the other sums in the same display read i=1.
Second check: none (judge only)
Report a problem with this finding
Typo In the definition of j-bad, the partition is written "P = I1 ∪ I2 ∪ · · · ∪ As ∪ {x}"; the last block should be I_s.
- p. 12 Proof of Lemma 3.4, definition of j-bad
A partition P = I1 ∪ I2 ∪ · · · ∪ As ∪ {x} is called j-bad
- p. 12 Definition of j-bad partition
P = I1 ∪ I2 ∪ · · · ∪ As ∪ {x} is called j-bad
- p. 12 definition of j-bad
P = I1 ∪ I2 ∪ · · · ∪ As ∪ {x}
- p. 12 definition of j-bad partition
I1 ∪I2 ∪· · · ∪As ∪{x} is called j-bad
Judge's note: The page 12 image shows A_s, while the same partition is written with I_s on page 11 and in Lemma 3.5.
Second check: none (judge only)
Report a problem with this finding
Typo Missing word in the definition of a box: "each Xi is a set of t-subsets N" (should be 't-subsets of N').
- p. 12 Definition of box
where each Xi is a set of t-subsets N
- p. 12 box definition
each Xi is a set of t-subsets N
Judge's note: The page 12 image confirms the omission; the next sentence reads 's-tuples of t-subsets of N'.
Second check: none (judge only)