Count sketch

1. For constants ${\displaystyle w}$ and ${\displaystyle t}$ (to be defined later) independently choose ${\displaystyle d=2t+1}$ random hash functions ${\displaystyle h_{1},\dots ,h_{d}}$ and ${\displaystyle s_{1},\dots ,s_{d}}$ such that ${\displaystyle h_{i}:[n]\to [w]}$ and ${\displaystyle s_{i}:[n]\to \{\pm 1\}}$. It is necessary that the hash families from which ${\displaystyle h_{i}}$ and ${\displaystyle s_{i}}$ are chosen be pairwise independent.

2. For each item ${\displaystyle q_{i}}$ in the stream, add ${\displaystyle s_{j}(q_{i})}$ to the ${\displaystyle h_{j}(q_{i})}$th bucket of the ${\displaystyle j}$th hash.

At the end of this process, one has ${\displaystyle wd}$ sums ${\displaystyle (C_{ij})}$ where

${\displaystyle C_{i,j}=\sum _{h_{i}(k)=j}s_{i}(k).}$

To estimate the count of ${\displaystyle q}$s one computes the following value:

${\displaystyle r_{q}={\text{median}}_{i=1}^{d}\,s_{i}(q)\cdot C_{i,h_{i}(q)}.}$

The values ${\displaystyle s_{i}(q)\cdot C_{i,h_{i}(q)}}$ are unbiased estimates of how many times ${\displaystyle q}$ has appeared in the stream.

The estimate ${\displaystyle r_{q}}$ has variance ${\displaystyle O(\mathrm {min} \{m_{1}^{2}/w^{2},m_{2}^{2}/w\})}$, where ${\displaystyle m_{1}}$ is the length of the stream and ${\displaystyle m_{2}^{2}}$ is ${\displaystyle \sum _{q}(\sum _{i}[q_{i}=q])^{2}}$.[7]

Furthermore, ${\displaystyle r_{q}}$ is guaranteed to never be more than ${\displaystyle 2m_{2}/{\sqrt {w}}}$ off from the true value, with probability ${\displaystyle 1-e^{-O(t)}}$.

The count sketch projection of the outer product of two vectors is equivalent to the convolution of two component count sketches.

The count sketch computes a vector convolution

${\displaystyle C^{(1)}x\ast C^{(2)}x^{T}}$, where ${\displaystyle C^{(1)}}$ and ${\displaystyle C^{(2)}}$ are independent count sketch matrices.

Pham and Pagh[8] show that this equals ${\displaystyle C(x\otimes x^{T})}$ – a count sketch ${\displaystyle C}$ of the outer product of vectors, where ${\displaystyle \otimes }$ denotes Kronecker product.

The fast Fourier transform can be used to do fast convolution of count sketches. By using the face-splitting product[9][10][11] such structures can be computed much faster than normal matrices.

• Count–min sketch
• Tensorsketch

• Faisal M. Algashaam; Kien Nguyen; Mohamed Alkanhal; Vinod Chandran; Wageeh Boles. "Multispectral Periocular Classification WithMultimodal Compact Multi-Linear Pooling" . IEEE Access, Vol. 5. 2017.
• Ahle, Thomas; Knudsen, Jakob (2019-09-03). "Almost Optimal Tensor Sketch". ResearchGate. Retrieved 2020-07-11.