CountSketch

形式陈述 ​

CountSketch 属于线性 Sketch理路线性 SketchLinear sketch以线性映射 Sf 压缩频率向量，使更新与分布式摘要可直接相加。：每行对频率向量做带随机符号的桶投影，更新和摘要合并保持线性，坐标估计则在这些线性测量上取作为顺序统计量理路顺序统计量Order statistic有限样本按键排序后第 k 个位置的值，保留重复出现的次数。的中位数。

线性摘要 ​

对从零开始的一般 Turnstile 流理路插入流与 Turnstile 流Insertion-only stream · Turnstile stream以频率向量更新语义区分非负插入、严格 Turnstile 与一般正负流。，先固定与随机哈希独立的净频率向量 $f$ 和查询键 $i$，以及 $0<\epsilon <1$、$0<\delta <1$。一组足够的随机性条件是：每行的桶哈希 $h_j:[U]\to [w]$ 来自碰撞概率至多 $1/w$ 的通用哈希族理路通用哈希Universal hashing · Universal hash family从函数族随机选择哈希函数，使任意预先固定的不同键对以至多 1/m 的概率碰撞。；符号哈希 $s_j:[U]\to \{-1,+1\}$ 均匀且四路独立，并与桶哈希独立；不同行的整组随机选择相互独立。更新 $(i,\mathrm{\Delta })$ 时

第 $j$ 行对 $i$ 的估计为 $X_j=s_j(i)C[j,h_j(i)]$，最终取各行中位数。

无偏与方差 ​

展开得

记碰撞指示量为 $I_k=\mathbf{1}\{h_j(k)=h_j(i)\}$。由于符号与桶哈希独立且 $\mathbb{E}[s_j(i)s_j(k)]=0$，有 $\mathbb{E}[X_j]=f_i$。展开噪声平方，$k\ne l$ 的交叉项含 $\mathbb{E}[s_j(k)s_j(l)]=0$，留下

例如取 $w\ge 3/{\epsilon }^2$，Chebyshev 不等式理路Chebyshev 不等式Chebyshev's inequality随机变量偏离均值至少给定距离的概率由方差除以距离平方控制。给出单行误差超过 $\epsilon \Vert f_{-i}{\Vert }_2$ 的概率至多 $1/3$。跨独立行取中位数后，只有至少一半行同时失准才会失败；对坏行指示量应用Hoeffding 不等式理路Hoeffding 不等式Hoeffding's inequality独立有界随机变量和偏离期望的概率以平方偏差的指数速度衰减。，失败概率至多 $e^{-d/18}$，故取最小的奇数 $d\ge 18\ln \left(1/\delta \right)$ 即可。若 $\Vert f_{-i}{\Vert }_2=0$，查询直接精确，无需使用这一概率界。

资源口径 ​

在哈希求值与计数器算术均按常数时间计的模型下，一次更新处理 $d$ 行，耗时 $O(d)$；一次点查询也耗时 $O(d)$，其中跨行中位数用线性时间选择算法计算，不必排序。摘要保存 $O(wd)$ 个计数器，另存所用哈希函数的描述。计数器位宽须按允许的流质量和更新幅度单独选择并计入空间；上述操作次数不是对任意精度整数的无条件位复杂度保证。