We consider the Count Sketch with single array.

Definitions

  1. Let S=(s1,s2,...,sn)S = (s_1, s_2, ..., s_n) be a stream of nn elements from a domain [d][d].
  2. A:A: an array of size mm.
  3. h:[d]→[m]h: [d] \rightarrow [m] a hash function that assigns each value in [d][d] an integer uniformly at random from [m][m].
  4. g:[d]→{−1,1}g: [d] \rightarrow \{ - 1, 1 \} a hash function that assigns each value in [d][d] a random sign.

Algorithm

For each element s∈Ss \in S, Count-Sketch updates AA as follows:

Update (ss):
\qquad A[h(s)]←A[h(s)]+g[s]A[ h(s) ] \leftarrow A[ h(s) ] + g[s]

After processing elements in SS, Count-Sketch answer query for an element's frequency as follows:

Query (vv):
\qquad return f^[v]≐g[v]⋅A[h(v)]\hat f[v] \doteq g[v] \cdot A[ h(v) ]

Error Analysis

For a fixed v∈[d]v \in [d], let f[v]f[v] be its true frequencies in SS (i.e., the number of times it appears in SS). Define indicator random variables

X1,X2,...,Xn, X_1, X_2, ..., X_n,

such that for i∈[n]i \in [n], define

Xi={1, if h(si)=h(v),g(si)=g(v),0, if h(si)≠h(v),−1, if h(si)=h(v),g(si)≠g(v), X_i = \begin{cases} &1, &\text{ if } h(s_i) = h(v), &g(s_i) = g(v), \\ &0, &\text{ if } h(s_i) \neq h(v), & \\ &-1, &\text{ if } h(s_i) = h(v), &g(s_i) \neq g(v), \end{cases}

The XiX_i's are not independent. For i∈[n]i \in [n], if si≠vs_i \neq v, it holds that

E[Xi]=0. \mathbb{E} [ X_i ] = 0.

For i,j∈[n],si≠v,sj≠vi, j \in [n], s_i \neq v, s_j \neq v, we have

E[XiXj]={0, if si≠sj,1m if si=sj. \mathbb{ E } [X_i X_j ] = \begin{cases} &0, &\text{ if } s_i \neq s_j, \\ &\frac{1}{m}&\text{ if } s_i = s_j. \end{cases}

The estimation error of f^[v]\hat f[v] can be written as

∣∑i∈[n],si≠vXi∣. \left| \sum_{ i \in [n], s_i \neq v } X_i \right|.

For given ϵ>0\epsilon > 0, we want to bound.

Pr⁡[∣∑i∈[n],si≠vXi∣≥ϵ] \begin{aligned} \Pr \left[ \left| \sum_{ i \in [n], s_i \neq v } X_i \right| \ge \epsilon \right] \end{aligned}

To do this, we pick some parameter t>0t > 0 and define Vbad≐{u∈[d],h(u)≥t}\mathcal{V}_{bad} \doteq \{ u \in [d], h(u) \ge t \}, and consider

Pr⁡[∣∑i∈[n],si≠vXi∣≥ϵ]≤Pr⁡[∃u∈Vbad:h(u)=h(v)]+Pr⁡[∣∑i∈[n],si≠vXi∣≥ϵ∣∄u∈Vbad:h(u)=h(v)]≤nt⋅m+Pr⁡[∣∑i∈[n],si≠vXi∣≥ϵ∣∄u∈Vbad:h(u)=h(v)]. \begin{aligned} &\Pr \left[ \left| \sum_{ i \in [n], s_i \neq v } X_i \right| \ge \epsilon \right] \\ &\le \Pr \left[ \exists u \in \mathcal{V}_{bad} : h(u) = h(v) \right] + \Pr \left[ \left| \sum_{ i \in [n], s_i \neq v } X_i \right| \ge \epsilon \mid \nexists u \in \mathcal{V}_{bad} : h(u) = h(v) \right] \\ &\le \frac{n}{ t \cdot m} + \Pr \left[ \left| \sum_{ i \in [n], s_i \neq v } X_i \right| \ge \epsilon \mid \nexists u \in \mathcal{V}_{bad} : h(u) = h(v) \right]. \end{aligned}

We consider the second probability.

Var[∣∑i∈[n],si≠vXi∣∣∄u∈Vbad:h(u)=h(v)]=∑i∈[n],si≠vVar[Xi∣∄u∈Vbad:h(u)=h(v)]+∑i∈[n],j∈[n],i≠j,si≠v,sj≠vE[XiXj∣∄u∈Vbad:h(u)=h(v)] \begin{aligned} &\mathbb{Var} \left[ \left| \sum_{ i \in [n], s_i \neq v } X_i \right| \mid \nexists u \in \mathcal{V}_{bad} : h(u) = h(v) \right] \\ &= \sum_{ i \in [n], s_i \neq v} \mathbb{Var} \left[ X_i \mid \nexists u \in \mathcal{V}_{bad} : h(u) = h(v) \right] \\ &\quad + \sum_{ i \in [n], j \in [n], i \neq j, s_i \neq v, s_j \neq v } \mathbb{E} \left[ X_i X_j \mid \nexists u \in \mathcal{V}_{bad} : h(u) = h(v) \right] \end{aligned}

The first term equals to nm\frac{n}{m}. For the second term, if si≠sjs_i \neq s_j, then by independence of XiX_i and XjX_j, it holds that

E[XiXj∣∄u∈Vbad:h(u)=h(v)]=E[Xi∣∄u∈Vbad:h(u)=h(v)]⋅E[Xj∣∄u∈Vbad:h(u)=h(v)]=0. \begin{aligned} &\mathbb{E} \left[ X_i X_j \mid \nexists u \in \mathcal{V}_{bad} : h(u) = h(v) \right] \\ &= \mathbb{E} \left[ X_i \mid \nexists u \in \mathcal{V}_{bad} : h(u) = h(v) \right] \cdot \mathbb{E} \left[ X_j \mid \nexists u \in \mathcal{V}_{bad} : h(u) = h(v) \right]=0. \end{aligned}

If si=sjs_i = s_j, then Xi=XjX_i = X_j. Hence,

∑i∈[n],j∈[n],i≠j,si≠v,sj≠vE[XiXj∣∄u∈Vbad:h(u)=h(v)]=∑i∈[n],j∈[n],i≠j,si≠v,sj≠v,si=sjE[Xi2∣∄u∈Vbad:h(u)=h(v)]=∑i∈[n],j∈[n],i≠j,si≠v,sj≠v,si=sj,f[si]≤t1m≤t2⋅nt⋅1m=t⋅nm. \begin{aligned} &\sum_{ i \in [n], j \in [n], i \neq j, s_i \neq v, s_j \neq v } \mathbb{E} \left[ X_i X_j \mid \nexists u \in \mathcal{V}_{bad} : h(u) = h(v) \right] \\ &= \sum_{ i \in [n], j \in [n], i \neq j, s_i \neq v, s_j \neq v, s_i = s_j } \mathbb{E} \left[ X_i^2 \mid \nexists u \in \mathcal{V}_{bad} : h(u) = h(v) \right] \\ &= \sum_{ i \in [n], j \in [n], i \neq j, s_i \neq v, s_j \neq v, s_i = s_j, f[s_i] \le t } \frac{1}{m} \\ &\le t^2 \cdot \frac{n}{t} \cdot \frac{1}{m} \\ &= \frac{ t \cdot n}{m}. \end{aligned}

By Chebyshev's inequality,

Pr⁡[∣∑i∈[n],si≠vXi∣≥ϵ]≤nt⋅m+t⋅nm⋅ϵ2. \begin{aligned} \Pr \left[ \left| \sum_{ i \in [n], s_i \neq v } X_i \right| \ge \epsilon \right] &\le \frac{n}{ t \cdot m} + \frac{t \cdot n}{m \cdot \epsilon^2}. \end{aligned}

By setting t=ϵt = \epsilon, the probability is minimized to

Pr⁡[∣∑i∈[n],si≠vXi∣≥ϵ]≤nm⋅2ϵ. \begin{aligned} \Pr \left[ \left| \sum_{ i \in [n], s_i \neq v } X_i \right| \ge \epsilon \right] &\le \frac{n}{m} \cdot \frac{2}{\epsilon}. \end{aligned}

Note that this error bound is exactly the same as Count-Min sketch with a single array of size mm.