Streaming

Theorem: Chernoff/Hoeffding Bound
Suppose \(X_1, \ldots, X_t\) are i.i.d. in {0, 1}, \(p = E[X_i]\), and \(\epsilon > 0\),
\(\operatorname{Pr}\left[\left|\frac{1}{t} \cdot \sum\limits_{i=1}^{t} X_{i}-p\right| \geq \epsilon\right] \leq 2 e^{-2 \epsilon^{2} t}\)
Markov's Inequality:
if \(X \geq 0\) is a random variable, then \(\forall t, P(X \geq t) \leq \frac{E[X]}{t}\)

Reservoir sampling: read first element, for \(i\)th element, replace remembered element with probability \(\frac{1}{i}\)
Sampling \(t\) elements with replacement: run \(t\) instances in parallel
Sampling \(t\) elements without replacement: reservoir of size \(t\), for \(i\)th element in stream, \(r = \operatorname{randint}(0, i)\) replace reservoir[\(r\)] with \(s_i\) if \(r < t\)

Trivial and exact solution necessarily takes \(\Omega(n)\) space
Choose a hash function \(h: \Sigma \rightarrow [0, 1]\)
Compute the minimum hash value of all the elements \(\alpha\)
Estimate is \(\frac{1}{\alpha}\)
Accuracy (rough):
\(\begin{align*} P(output \leq \frac{k}{2}) &= \prod\limits_{i=1}^k P(r_i \geq \frac{2}{k}) \\ &= (1-\frac{2}{k})^k \\ &\leq e^{-2} \\ P(output \geq 4k) &= P(\min(r_i) \leq \frac{1}{4k} \\ &= P(r_1 \leq \frac{1}{4k} \vee r_2 \leq \frac{1}{4k} \vee \ldots) \\ &\leq \sum_{i=1}^{k} P(r_{i} \leq \frac{1}{4 k})\\ &= \frac{1}{4} \end{align*}\)
Can have estimate between \((k-\epsilon k, k+\epsilon k)\) with probability \(> 90\)

Completely random functions cannot be stored
Universal Hash Family:
If a function \(h\) is picked at random from \(\mathcal{H}=\left\{h_{1}, \dots, h_{M}\right\}\), \(\mathcal{H}\) is universal iff \(\forall x \neq y \in \Sigma, i, j \in R, P(h(x)=i \wedge h(y)=j) = \frac{1}{|R|^2}\)

Trivial for finding an element that appears a majority of times:
Two integers for keeping id and count
More general case: finding all labels that occur more than \(\beta n\) times
Count-Min-Sketch:
parameterized by \(l, B\)
With \(B = 2 / \epsilon\), \(l = \lceil\ln \frac{1}{\delta}\rceil\), estimate \(\hat a_i \leq a_i + \epsilon n\) with probability \(1-\delta\)
or,
- With probability 1, contains all labels that occur more than \(tn\) times in the stream
- With probability \(1-\delta\), does not contain labels that occur less than \((t - \epsilon)n\) times
Keep \(l\) rows of hash tables with \(B\) "buckets", for each element in the stream, for each row, increment the corresponding bucket of the hash value of the element
The estimate for element \(a\) is simply the minimum of the counts in the corresponding buckets
Errors occur when collisions happen, which has a probability of \(\frac{1}{B}\) for each pair of elements
With Markov's inequality, can prove \(P(M\left[i, h_{i}(a)\right]>f_{a}+\frac{2 n}{B}) \leq \frac{1}{2}\), hence the probability of the estimate being larger than \(f_a + \frac{2n}{B}\) is less than \(\frac{1}{2^l}\)

"Compression Algorithm": any injective function that maps bit strings to bit strings
Injective: \(\forall x \neq y, C(x) \neq C(y)\)
Surjective: \(\forall y, \exists x, C(x) = y\)
Theorem: There is no compression algorithm \(C\) than maps all \(L\)-bit strings to \((L-1)\)-bit strings.
Proof: there are \(2^L\) bit strings of length \(L\), and only \(2^{L-1}\) bit strings of length \(L-1\)
If there is a deterministic and exact algorithm for distinct elements that uses \(O(\min(|\Sigma|, n)\), there is a compression algorithm that maps \(L\)-bit strings to length \(O(L)\)
Proof
We can make \(\Sigma\) the set \(\{(0, 0), (0, 1), (1, 0), (1, 1), \ldots, (L, 0), (L, 1)\}\). For each \(i\) in range(\(L\)), insert to the algorithm \((i, b_i)\). To find \(b_i\), we can insert \((i, 0)\) and query the number of distinct elements. If the number changes, \(b_i = 1\), else \(b_i = 0\). Hence we can reconstruct the whole bit string.
Same type of proof for heavy hitters