Chapter 9: Streaming and Sketching II

CountMinSketch is essentially a counting Bloom filter. In a Bloom filter, each element sets \(T\) bits (one per hash function) to 1. A query returns the AND of the \(T\) bits — all must be 1 for a positive. In CMS, each element increments \(T\) counters (one per hash function). A query returns the MIN of the \(T\) counters.

The parallel: BF has false positives (bits set by other elements), CMS has overestimation (counts inflated by collisions). BF uses AND to minimise false positives; CMS uses MIN to minimise overestimation. Both use \(T\) independent hash functions for probability amplification, and both have one-sided error.

\(\|x\|_\infty \leq \|x\|_2\): Let \(x_k\) be the largest absolute value. Then \(\|x\|_\infty^2 = x_k^2 \leq \sum_i x_i^2 = \|x\|_2^2\).

\(\|x\|_2 \leq \|x\|_1\): \(\|x\|_2^2 = \sum x_i^2 \leq \left(\sum |x_i|\right)^2 = \|x\|_1^2\) since all cross-terms \(|x_i||x_j| \geq 0\).

\(\|x\|_2 \geq \|x\|_1/\sqrt{d}\): By Cauchy-Schwarz, \(\|x\|_1 = \sum |x_i| \cdot 1 \leq \sqrt{\sum x_i^2} \cdot \sqrt{d} = \|x\|_2 \sqrt{d}\). Rearranging gives the result. \(\square\)

Misra-Gries advantages:

• Deterministic — guaranteed error bound with no probability of failure.
• Never overestimates: \(\hat{f}_j \leq f_j\).
• No hash functions needed.

CountMinSketch advantages:

• Linear sketch — composable, works in distributed settings.
• Easy point queries: \(O(T)\) time per query vs.\ \(O(\log k)\) for MG.
• Probability amplification is built-in.
• Simpler to implement for large \(k\).

Misra-Gries disadvantages: Not a linear sketch; hard to compose results from distributed computations. CMS disadvantage: always overestimates; requires randomness. \(\square\)

For the same total space \(S\), ignoring logarithmic factors:

• CountSketch: Uses \(k = S\) columns per row. Error \(\leq \|f_{-j}\|_2 / \sqrt{k} = \|f_{-j}\|_2 / \sqrt{S}\).
• CountMinSketch: Uses \(k = S\) columns per row. Error \(\leq \|f_{-j}\|_1 / k = \|f_{-j}\|_1 / S\).

CS is better when \(\|f_{-j}\|_2 / \sqrt{S} < \|f_{-j}\|_1 / S\), i.e., when \(\|f_{-j}\|_1 / \|f_{-j}\|_2 > \sqrt{S}\). This happens when the frequency distribution is spread out (many elements with similar frequencies).

CMS is better when the frequency distribution is concentrated (a few heavy hitters dominate), so \(\|f_{-j}\|_1\) is relatively small compared to \(\|f_{-j}\|_2 \sqrt{S}\). \(\square\)

In the strict turnstile model, updates are \((j, c)\) with \(c \in \{-B, \ldots, B\}\), but \(f_j \geq 0\) always. Modify CMS:

• Update: For each \(t\), set \(C[t][h_t(j)] \leftarrow C[t][h_t(j)] + c\) (allow negative increments).
• Query: Still return \(\hat{f}_j = \min_t C[t][h_t(j)]\).

The guarantee \(f_j \leq \hat{f}_j\) still holds because: at any time, \(C[t][h_t(j)] = f_j + \sum_{i \neq j, h_t(i) = h_t(j)} f_i \geq f_j\) since all \(f_i \geq 0\) in the strict turnstile model. The upper bound analysis also carries through since \(\|f_{-j}\|_1 = \sum_{i \neq j} f_i\) is still well-defined and non-negative. \(\square\)

Combining MG outputs: Let \(\hat{f}^{(1)}\) and \(\hat{f}^{(2)}\) be the two MG outputs (associative arrays with at most \(k\) keys each).

1. Add them pointwise: \(\hat{f}^{(\text{combined})}[j] = \hat{f}^{(1)}[j] + \hat{f}^{(2)}[j]\).
2. If the combined output has more than \(k\) non-zero keys, find the \((k+1)\)-th largest value \(v_{k+1}\).
3. Subtract \(v_{k+1}\) from all values and remove non-positive entries.

This preserves the MG invariant: at most \(k\) keys, and \(f_j - m/(k+1) \leq \hat{f}_j \leq f_j\). The combined error at most doubles: \(f_j - (m_1 + m_2)/(k+1) \leq \hat{f}_j \leq f_j\).

MG is NOT a linear sketch because the combination involves a non-linear step (finding the \((k+1)\)-th largest and subtracting). Linear sketches require only pointwise addition. \(\square\)

Approach: Run CMS with \(k = \lceil 2e/\varepsilon \rceil\) and \(T = \lceil \ln(n/\delta) \rceil\). Additionally, maintain \(\|f\|_1 = \sum_j f_j\) as a running counter (costs \(O(\log m)\) space).

Finding heavy hitters: After processing the stream, iterate over all \(j \in [n]\) and query CMS for each. Report \(j\) if \(\hat{f}_j \geq \varepsilon \|f\|_1\). By the CMS guarantee:

• If \(f_j \geq \varepsilon \|f\|_1\), then \(\hat{f}_j \geq f_j \geq \varepsilon \|f\|_1\), so \(j\) is reported (no false negatives).
• If \(f_j < \varepsilon \|f\|_1 / 2\), then with high probability \(\hat{f}_j < f_j + \varepsilon\|f\|_1/2 < \varepsilon\|f\|_1\), so \(j\) is not reported.

Space: \(O\!\left(\frac{\log(nm)}{\varepsilon} \cdot \log\frac{n}{\delta}\right)\). The query time is \(O(nT)\), which can be improved using a hierarchical scheme. \(\square\)