MIT 6.1220 — Lecture 19

Streaming Algorithms

Definition (Compression Function). Given an input stream $X$ , we might have a compression function $f(X)$ whose value we would like to compute.

Definition (Sketch). A sketch $C(X)$ is a “summary” of the stream $X$ , with the property that $C(X \cup \{x\})$ is a simple function of $C(X)$ and $x$ , and that $C(X)$ alone is enough to compute or approximate $f(X)$ .

Roughly speaking, the quality of our streaming algorithm has to do with:

The size of the sketch $C(X)$ .
How well we can compute $f(X)$ given $C(X)$ .
How long it takes to update $C(X \cup \{x\})$ given $C(X)$ and $\{x\}$ .

Remark. An easy exercise: find a streaming algorithm for finding the maximum element of a list, such that…

The sketch $C(X)$ has size $O(1)$ .
We can compute $f(X)$ exactly given $C(X)$ .
Updating $C(X)$ takes $O(1)$ time.

Problem. (Distinct Elements) Compute the number of distinct elements of a list $X$ .

In general, our standards for the quality of our estimate $\tilde{f}(X)$ can be summarized by constants $\epsilon, \delta \in [0, 1]$ .

\mathrm{Pr}\left [ \tilde{f}(X) \in ((1 - \epsilon) f(X), (1 + \epsilon)f(X)) \right] \geq 1 - \delta.

The smaller the values of $\epsilon$ and $\delta$ , the better.

Solution. (Flajolet-Martin 1985) Suppose the elements of $X$ come from a universe $\mathcal{U}$ , and pick a “truly random” function $h: \mathcal{U} \to [0, 1]$ . Omit the details of randomness for simplicity.

Initialize $C(X) = 1$ , and update $C(X \cup \{x\}) = \min\{C(X), h(x)\}$ . Then output $\tilde{f}(X) = (C(X))^{-1} - 1$ .

Perhaps expectedly, Flajolet-Martin sucks; let's analyze its quality using the $(\epsilon, \delta)$ definition from above.

Proof: For any $\epsilon \in [0, 1]$ and sufficiently large $n := (\# \text{ distinct elements of } X) = f(X)$ , we have:

\begin{align*}\mathrm{Pr}\left [ \tilde{f}(X) \in ((1 - \epsilon) n, (1 + \epsilon)n) \right] = \left(1 - \dfrac{1}{(1 + \epsilon)n + 1}\right)^n - \left(1 - \dfrac{1}{(1 - \epsilon)n + 1}\right)^n \approx e^{-1/(1 + \epsilon)} - e^{-1/(1 - \epsilon)}.\end{align*}

Notably, $\delta \approx 1 - (e^{-1/(1 + \epsilon)} - e^{-1/(1 - \epsilon)})$ does not tend to be very small for large $n$ —especially for small $\epsilon$ . $\blacksquare$

Here's a better algorithm than Flajolet-Martin.

Solution. (KMV) Say the elements of $X$ come from a universe $\mathcal{U}$ of size $u := |\mathcal{U}|$ . Say $M = \{1, 2, \dots, u^3\}$ . Pick a hash function $h: \mathcal{U} \to M$ at random from a $2$ -wise independent hash family.

Initialize $C(X) = \emptyset$ , define $k := \lceil 24 \epsilon^{-2} \rceil$ , where $\epsilon$ is one of the “quality constants” from earlier. Update like so:

C(X) = \min_k\{C(X) \cup \{h(x_i)\}\}, \text{ where } \min_k \clubsuit := \{ \text{the $k$ smallest elements of $\clubsuit$}\}.

Finally, return the value:

\tilde{f}(X) := \begin{cases} |C(X)| & \text{if } |C(X)| < k. \\ k u^3 \cdot \left(\max\{C(X)\}\right)^{-1} & \text{otherwise.} \end{cases}

Remark. Think of this as an improved Flajolet-Martin.

Rather than hashing $h: \mathcal{U} \to [0, 1]$ , we discretize the interval $[0, 1]$ into $|\mathcal{U}|^3$ pieces.
Rather than only considering the minimum hashed value, we consider the $k$ least hashed values.

Claim. For all $\epsilon < \frac{1}{2}$ , assuming $u > \frac{1}{\epsilon^2}$ , we have that $\delta = \frac{1}{3}$ holds.

Proof: Say that $X$ has $d := f(X)$ distinct values. Let's justify only the bound $\mathrm{Pr}\left [\tilde{f}(X) \geq (1 + \epsilon) d\right ] \leq \frac{1}{12}$ .

If $|C(X)| < k$ , then we are in the “top case” for $\tilde{f}(X)$ , so this probability is obviously zero.

Otherwise, $\tilde{f}(X) \geq (1 + \epsilon) d$ means that at least $k$ hash values are at most $L = k u^3 \cdot \left [ (1 + \epsilon) d \right ]^{-1}$ . Consider indicator variables $Y_i$ that measure whether the $i^{\text{th}}$ distinct element is hashed to a value at most $L$ . If $Y := \sum_{i = 1}^d Y_i$ , then:

\mathbb{E}[Y] = d \cdot \mathbb{E}[Y_i] = \dfrac{k}{1 + \epsilon} ~~~ \text{ and } ~~~ \mathbb{V}[Y] = d \cdot \mathbb{V}[Y_i] = d \cdot\left(\mathbb{E}[Y_i^2] - (\mathbb{E}[Y_i])^2\right) \leq d \cdot \mathbb{E}[Y_i^2] = \dfrac{k}{1 + \epsilon}.

We're allowed to say $\mathbb{V}[Y] = \sum_{i = 1}^d \mathbb{V}[Y_i]$ because the $2$ -wise independence means $\mathrm{cov}(Y_i, Y_j) = 0$ for $i \neq j$ .

Now Chebyshev's inequality gives us:

\mathrm{Pr}[Y \geq k] = \mathrm{Pr}\left [ Y - \dfrac{k}{1 + \epsilon} \geq \dfrac{\epsilon k}{1 + \epsilon} \right ] \leq \mathrm{Pr} \left [ |Y - \mathbb{E}[Y]| \geq \dfrac{\epsilon k}{1 + \epsilon} \right] \leq \dfrac{\mathbb{V}[Y]}{\left(\frac{\epsilon k}{1 + \epsilon}\right)^2} \leq \dfrac{1 + \epsilon}{\epsilon^2k} \leq \dfrac{1}{12}.

The other direction is $\mathrm{Pr}\left [\tilde{f}(X) \leq (1 - \epsilon) d\right ] \leq \frac{1}{4}$ hence the $\delta = \frac{1}{3}$ constant. It's not exactly symmetric. $\blacksquare$

The space is $O(k \log u) = O\left(\frac{\log u}{\epsilon^2}\right)$ , and the update time is $O(\log k)$ ; the $\log k$ comes from max-heap insertion operations.

Remark. We used the term “ $2$ -wise independent hashing” earlier. Here are the details of what that means:

Definition. A hash family $\mathcal{H} = \{h_i: \mathcal{U} \to M\}$ is $t$ -wise independent if, for all distinct keys $k_1, \dots, k_t \in \mathcal{U}$ and (not necessarily distinct!) values $i_1, \dots, i_t \in M$ , we have:
$\underset{h \sim \mathcal{H}}{\mathrm{Pr}} \left [ \bigwedge_{j = 1}^t h(k_j) = i_j \right ] = \dfrac{1}{|M|^t}.$
For prime values of $m := |M|$ , one possible $t$ -wise independent hash family is:
$\mathcal{H} := \left \{ h_{(a_0, \dots, a_{t - 1})}(k) := \left( \left(\sum_{i = 0}^{t - 1} a_i k^i\right) \% m \right) \right \}_{(a_0, \dots, a_{t - 1}) \in M^t}.$

Note that $2$ -wise independent hash families are guaranteed universal, and $s$ -wise independence implies $t$ -wise independence for $s > t$ .

Problem. (Majority) Given an input stream $X$ with an element $x$ that appears more than half the time, find $x$ .

Solution. (BM81) Store two variables $c$ and $x$ . Initialize $c = 0$ and $x = \textsc{Null}$ . Upon reading a new $x_i$ ,

If $x = \textsc{Null}$ , then set $c = 1$ and $x = x_i$ .
If $x = x_i$ , then increment $c$ and leave $x$ unchanged.
If $x \neq x_i$ , then decrement $c$ . If $c = 0$ now, set $x = \textsc{Null}$ .

Then $x$ is the desired answer.

Proof: Say $M$ is the majority element. Consider some transition $(c, x) \to (c - 1, [x \text{ or } \textsc{Null}])$ upon reading in a new $x_i$ . Think of this instance of $x_i$ as “eliminating” an instance of $x$ earlier in the stream.

In this way, instances of $x$ form disjoint pairs with different values $x_i$ later in the stream. And removing any one of these pairs from the stream does not affect the final answer of the algorithm!

But if we remove all such pairs, the result is an input stream of only $M$ 's—the leftovers are all copies of the final $x$ , and $M$ is too frequent to be paired away entirely. So $M$ must be the final answer. $\blacksquare$

Problem. (Heavy Hitters) Given an input stream $X$ , find all elements that appear more than $\frac{1}{k}$ of the time.

Solution. (MG82) Have $k - 1$ copies of the $(c, x)$ setup from before. Upon reading a new $x_i$ ,

If $x_i$ matches any of the $x$ values, increment its corresponding $c$ .
Otherwise, if some $x$ equals $\textsc{Null}$ , replace that $\textsc{Null}$ with $x_i$ and set $c = 1$ .
Otherwise, decrement all $c$ . Set any $x$ whose $c$ becomes $0$ to Null.

Then every element that appears more than $\frac{1}{k}$ of the time will be one of the $x$ values.

Remark. Note that the algorithm might return values that don't appear more than $\frac{1}{k}$ of the time.

Proof: Similar argument as before. Every transition of the form

\{(c_1, x_1), (c_2, x_2), \dots, (c_{k - 1}, x_{k - 1})\} \stackrel{x_i}{\longrightarrow} \{(c_1 - 1, x_1), (c_2 - 1, x_2), \dots, (c_{k - 1} - 1, x_{k - 1})\}

can be viewed as an instance of $x_i$ “eliminating” an instance of each of $x_1, x_2, \dots, x_{k - 1}$ .

Removing any of these $k$ -tuples from the input stream does not affect the final result of the algorithm. Remove $k$ -tuples until you cannot any longer; the resulting stream still has every $x$ that appears more than $\frac{1}{k}$ of the time. $\blacksquare$

Problem. (Approximate Heavy Hitters) Given an input stream $X$ , find a set $H$ of elements such that:

If an element appears more than $\frac{1}{k}$ of the time, it must be in $H$ .
If an element appears at most $\frac{1}{k} - \epsilon$ of the time, it is in $H$ with probability at most $\delta$ .

In other words, we want to never return elements that barely appear in the stream.

Solution. (Count-Min) Take $d := \lceil \log_2 \delta^{-1} \rceil$ and $m := \lceil 2 \epsilon^{-1} \rceil$ . Furthermore, consider a $2$ -wise independent hash family $\mathcal{H} := \{ h_i : \mathcal{U} \to \{1, 2, \dots, m\}\}$ and sample $d$ hash functions $\{h_1, h_2, \dots, h_d\}$ from $\mathcal{H}$ .

Our sketch is a $d \times m$ two-dimensional array $C$ , where $C[i][j]$ stores the # of $x_k$ in the input stream with $h_i(x_k) = j$ . Then we estimate that the frequency of $x_k$ is $\#(x_k) := \underset{1 \leq i \leq d}{\min} C[i][h_i(x_k)]$ .

Based on these frequency estimates, we select the heavy hitters to be all $x_k$ with $\#(x_k) \geq \frac{n}{k}$ , where $n := |X|$ . (Finding these $x_k$ requires updating a min-heap that keeps track of high-frequency $x_k$ incrementally.)

In other words, Count-Min has $d$ hash functions, each using $m$ space, to try to estimate the frequency of each $x_k$ . Hash collisions will cause hash functions to overestimate, so we use the minimum estimate across all $h_i$ .

Proof: There are two conditions that Approximate Heavy Hitters demands of us. The former is obvious.

Claim 1. If an element appears more than $\frac{1}{k}$ of the time, Count-Min will return it.

Proof: The point is that $\#(x_k)$ is never an underestimate. $\square$

The latter takes some work.

Claim 2. If an element appears at most $\frac{1}{k} - \epsilon$ of the time, Count-Min returns it with probability at most $\delta$ .

Proof: Count-Min returns such an $x_k$ only if every single $h_i$ overestimates by at least $\epsilon n$ . Well,
$\underset{h_i \sim \mathcal{H}}{\mathbb{E}}[\text{how much } h_i \text{ overestimates } (\text{true \#})(x_k)] = \sum_{x_j \neq x_k} \underset{h_i \sim \mathcal{H}}{\mathrm{Pr}} \left [ h_i(x_j) = h_i(x_k) \right ] < \dfrac{n}{m}.$
(This step requires $\mathcal{H}$ to be universal.) Therefore, by Markov's inequality,
$\underset{h_i \sim \mathcal{H}}{\mathrm{Pr}}[h_i \text{ overestimates (true \#)($x_k$) by more than } \epsilon n] \leq \dfrac{n / m}{\epsilon n} \leq \dfrac{1}{2}.$
So the probability that every single $h_i$ overestimates by too much is at most $\left(\frac{1}{2}\right)^{d} \leq \delta$ . $\square$

And that's why we chose $d := \lceil \log_2 \delta^{-1} \rceil$ and $m := \lceil 2 \epsilon^{-1} \rceil$ . $\blacksquare$

Definition (Jaccard Similarity). Given sets $S$ and $T$ , their Jaccard similarity is $J(S, T) := \frac{|S \cap T|}{|S \cup T|}$ .

Problem. (Similarity Search) Consider a collection of $n$ sets $A_1, \dots, A_n \subseteq \mathcal{U}$ and a target set $A \subseteq \mathcal{U}$ , all of size at most $d$ . Given $1 > s > s' > 0$ , output Yes if there is some $A_i$ such that $J(A_i, A) \geq s$ , and No if $J(A_i, A) < s'$ for all $A_i$ .

The solution to this problem is fairly complex and generalizable, so we only give a rough sketch here.

Solution. (Approximate Similarity Search) Sample $tL$ random hash functions $h_{1, 1}, \dots, h_{L, t}: \mathcal{U} \to [0, 1]$ , and define:

\sigma_{\ell}(K) := \left( \underset{k \in K}{\min} \{ h_{\ell, 1}(k) \}, \ \underset{k \in K}{\min} \{ h_{\ell, 2}(k) \}, \ \dots, \ \underset{k \in K}{\min} \{ h_{\ell, t}(k) \} \right).

Then output Yes if there is some set $A_j$ and some $1 \leq \ell \leq L$ such that $\sigma_{\ell}(A_j) = \sigma_{\ell}(A)$ , and No otherwise.

Claim. If $J(A_j, A) = \lambda$ , then $\mathrm{Pr}[\sigma_{\ell}(A_j) = \sigma_{\ell}(A) \text{ for some } \ell] \geq 1 - (1 - \lambda^t)^L$ .

Thus, we should tune the parameters $t$ and $L$ so that $1 - (1 - (s')^t)^L$ is small and $1 - (1 - s^t)^L$ is big. (Bigger $t$ eliminates false positives, whereas bigger $L$ eliminates false negatives.)