Count sketch is a type ofdimensionality reduction that is particularly efficient instatistics,machine learning andalgorithms.^[1][2]It was invented by Moses Charikar, Kevin Chen and Martin Farach-Colton^[3] in an effort to speed up theAMS Sketch by Alon, Matias and Szegedy for approximating thefrequency moments of streams^[4] (these calculations require counting of the number of occurrences for the distinct elements of the stream).

The sketch is nearly identical^{[citation needed]} to theFeature hashing algorithm by John Moody,^[5] but differs in its use of hash functions with low dependence, which makes it more practical.In order to still have a high probability of success, themedian trick is used to aggregate multiple count sketches, rather than the mean.

These properties allow use for explicitkernel methods, bilinearpooling inneural networks and is a cornerstone in many numerical linear algebra algorithms.^[6]

The inventors of this data structure offer the following iterative explanation of its operation:^[3]

• at the simplest level, the output of a singlehash functions mapping stream elementsq into {+1, -1} is feeding a singleup/down counterC. After a single pass over the data, the frequency${\displaystyle n(q)}$ of a stream elementq can be approximated, although extremely poorly, by theexpected value${\displaystyle \mathbf{E}[C\cdot s(q)]}$;
• a straightforward way to improve thevariance of the previous estimate is to use an array of different hash functions${\displaystyle s_i}$, each connected to its own counter${\displaystyle C_i}$. For each elementq, the${\displaystyle \mathbf{E}[C_i\cdot s_i(q)]=n(q)}$ still holds, so averaging across thei range will tighten the approximation;
• the previous construct still has a major deficiency: if a lower-frequency-but-still-important output elementa exhibits ahash collision with a high-frequency element,${\displaystyle n(a)}$ estimate can be significantly affected. Avoiding this requires reducing the frequency of collision counter updates between any two distinct elements. This is achieved by replacing each${\displaystyle C_i}$ in the previous construct with an array ofm counters (making the counter set into a two-dimensional matrix${\displaystyle C_{i,j}}$), with indexj of a particular counter to be incremented/decremented selected via another set of hash functions${\displaystyle h_i}$ that map elementq into the range {1..m}. Since${\displaystyle \mathbf{E}[C_{i,h_i(q)}\cdot s_i(q)]=n(q)}$, averaging across all values ofi will work.

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{m}\mathrm{i}\mathrm{n}\{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)}}$.

Alternatively Count-Sketch can be seen as a linear mapping with a non-linear reconstruction function.Let${\displaystyle M^{(i\in [d])}\in \{-1,0,1{\}}^{w\times n}}$, be a collection of${\displaystyle d=2t+1}$ matrices, defined by

${\displaystyle M_{h_i(j),j}^{(i)}=s_i(j)}$

for${\displaystyle j\in [w]}$ and 0 everywhere else.

Then a vector${\displaystyle v\in {\mathbb{R}}^n}$ is sketched by${\displaystyle C^{(i)}=M^{(i)}v\in {\mathbb{R}}^w}$.To reconstruct${\displaystyle v}$ we take${\displaystyle v_j^{\ast }={\text{median}}_i{C}_j^{(i)}{s}_i(j)}$.This gives the same guarantees as stated above, if we take${\displaystyle m_1=\Vert v{\Vert }_1}$ and${\displaystyle m_2=\Vert v{\Vert }_2}$.

The count sketch projection of theouter product of two vectors is equivalent to theconvolution of two component count sketches.

The count sketch computes a vectorconvolution

${\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 theouter product of vectors, where${\displaystyle \otimes }$ denotesKronecker product.

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

• Count–min sketch is a version of algorithm with smaller memory requirements (and weaker error guarantees as a tradeoff).
• Tensor sketch

• Charikar, Moses; Chen, Kevin; Farach-Colton, Martin (2004)."Finding frequent items in data streams"(PDF).Theoretical Computer Science.312 (1). Elsevier BV:3–15.doi:10.1016/s0304-3975(03)00400-6.ISSN 0304-3975.
• Faisal M. Algashaam; Kien Nguyen; Mohamed Alkanhal; Vinod Chandran; Wageeh Boles. "Multispectral Periocular Classification WithMultimodal Compact Multi-Linear Pooling"[1].IEEE Access, Vol. 5. 2017.
• Ahle, Thomas; Knudsen, Jakob (2019-09-03)."Almost Optimal Tensor Sketch".ResearchGate. Retrieved2020-07-11.

• Dimension reduction
• Hash-based data structures
• Probabilistic data structures

• Articles with short description
• Short description matches Wikidata
• All articles with unsourced statements
• Articles with unsourced statements from September 2023
• Pages that use a deprecated format of the math tags