AMS 二阶矩 Sketch

单计数器 ​

对频率向量公理库频率矩问题Frequency moments用 F_k 汇总频率向量，统一不同项数、流长与重复集中度目标。 $f\in {\mathbb{Z}}^U$，取 4-wise independent 符号 $s_i\in \{-1,+1\}$，在更新 $(i,\mathrm{\Delta })$ 时维护

$$Z\leftarrow Z+s_i\mathrm{\Delta }.$$

流结束后 $Z=\sum _i{s}_i{f}_i$，输出 $X=Z^2$。线性更新同时支持 insertion-only 与 turnstile。

无偏与四阶矩 ​

展开平方，异项因 $\mathbb{E}[s_i{s}_j]=0$ 消失：

$$\mathbb{E}[X]=\sum _i{f}_i^2=F_2.$$

控制 $\mathrm{Var}(Z^2)$ 需要展开四个符号的乘积，故 4-wise independence 是自然充分条件；仅 2-wise 不能自动控制四阶矩。标准计算给 $\mathrm{Var}(X)\le 2F_2^2$ 的量级。

置信放大 ​

单个 $Z^2$ 方差很大。每组平均 $\mathrm{\Theta }(1/{\epsilon }^2)$ 个独立副本，经 Chebyshev 得相对误差 $\epsilon$ 的常数成功率；再取 $\mathrm{\Theta }(\log \left(1/\delta \right))$ 组平均值的中位数，把失败率降到 $\delta$。空间还要乘每个计数器存储位宽。

更新例子与边界 ​

同一键多次正负更新只改变一个带固定符号的计数器，最终恰按净频率进入 $Z$；这展示线性 sketch 可合并。一次 $Z^2$ 偶然接近零不说明 $F_2$ 小，不能省略重复。均值和中位数的层次若颠倒，方差缩减与尾部放大的证明也随之失效。

位空间与哈希种子 ​

若流总绝对更新量为 $L_1$, 则 $|Z|\le L_1$，一个计数器需 $O(\log L_1)$ 位，而不是一个抽象“字”。4-wise independent 符号可由有限域低次多项式生成，种子空间也要计入摘要。

两个 AMS sketch 只有使用相同符号函数时才能相加合并；独立副本的编号和种子必须对齐。合并后 $Z$ 等于两频率向量和的投影，平方应在合并后计算，不能把各自 $Z^2$ 直接相加。

更新吞吐与查询时机 ​

所有计数器都在一条更新到来时同步执行

$$Z_{a,b}\leftarrow Z_{a,b}+s_{a,b}(i)\mathrm{\Delta }.$$

因此朴素每次更新需计算并写 $\mathrm{\Theta }({\epsilon }^{-2}\log \left(1/\delta \right))$ 个投影；空间同阶乘以单计数器位宽。批量 SIMD 可以改善常数，却不会让所有副本共享同一个符号，因为组内独立性正用于降低方差。

查询时先对每个计数器平方，再在组内平均、组间取中位数；在投影阶段提前平方会失去后续负更新抵消，也无法合并流片段。若采用模整数避免溢出，模回绕后的平方不再是实数上的 $F_2$ 估计，需另做恢复分析。

参考资料

• Noga Alon, Yossi Matias, Mario Szegedy, The Space Complexity of Approximating the Frequency Moments, JCSS, 1999.
• Graham Cormode, Ke Yi, Small Summaries for Big Data, frequency moment sketches.