频率矩问题

定义与特例 ​

对流的频率向量公理库插入流与 Turnstile 流Insertion-only stream · Turnstile stream以频率向量更新语义区分非负插入、严格 Turnstile 与一般正负流。，非负频率下 (F_p=\sum_i f_i^p)。(F_0=|{i:f_i\ne0}|) 单独定义以避开 (0^0)；(F_1=m) 是流长；(F_2) 是 self-join size。

流 (a,a,b,b) 与 (a,a,a,b) 都长 4；前者 (F_2=2^2+2^2=8)，后者 (F_2=3^2+1^2=10)。任务可要求精确值，或给定 (\varepsilon,\delta) 返回 ((1\pm\varepsilon)) 近似。

从流的 (m) 个位置中有放回独立抽两次，键相同的有序位置对数正是 (F_2)。因此 (F_2/m^2) 是两次抽取命中同键的概率。它不是频率的方差，但与 (\lVert f\rVert_2^2) 相同，并直接测量碰撞集中度。

AMS 二阶矩估计器 ​

选择四独立随机符号 (\xi_i\in{-1,+1})，维护 [ Z=\sum_i\xi_i f_i. ] 更新 ((i,\Delta)) 只做 (Z\leftarrow Z+\xi_i\Delta)，因此同一状态同时支持正负更新。展开可得

$$\mathbb{E}{Z}^2=\sum _i{f}_i^2+2\sum _{i<j}\mathbb{E}[{\xi }_i{\xi }_j]f_i{f}_j=F_2,$$

因为交叉项的符号期望为零。对频率 ((3,1))，符号同号时 (Z^2=16)，异号时为 4，二者平均为 10，恰等于 (3^2+1^2)。

单副本波动很大。四独立性用于控制四阶矩与方差；重复独立副本先分组取均值，再取组间中位数，可把相对误差与失败概率降到目标范围。只写“两两独立使估计无偏”不足以支持集中保证。

各阶任务为何不同 ​

(F_0) 只看支持集，不随同一键重复增长；(F_1) 在 insertion-only 中就是流长，无需 sketch；(F_2) 测量碰撞集中度。更高阶 (p) 更受最大坐标支配，流算法空间随 (p) 出现相变，不能把 AMS 的平方换成任意指数就得到通用估计器。

General turnstile 中通常定义 [ F_p=\sum_i|f_i|^p. ] 若对奇数 (p) 直接使用 (f_i^p)，正负坐标会抵消，甚至产生负的“矩”，失去范数语义。严格 turnstile 的非负性又要求每个前缀成立，不能只检查最终向量。

近似与输入边界 ​

乘法 ((1\pm\varepsilon)) 在 (F_p=0) 时要求精确返回 0，接口应单独约定空流或完全抵消状态。若结果只有加性误差，必须说明相对于 (\lVert f\rVert_1^p)、尾部范数还是其他尺度；不能把两者统称“近似”。(p) 是算法参数，引用空间界时也不能固定后隐藏。

参考资料

• Alon, Matias, Szegedy, JCSS 1999.
• Muthukrishnan, Data Streams, 2005.