线性 Sketch

线性摘要只保存频率向量经过固定投影后的坐标。每次更新等于给投影状态加一列，两个分片相加等于先合并频率再投影；解码器可以非线性，因为可合并性要求的是内部状态遵守同一代数，而不是最终估计也必须线性。

CountSketch 状态轨迹 ​

一行 CountSketch 选择桶哈希 $h:[n]\to [b]$ 与符号 $s:[n]\to \{\pm 1\}$，维护

更新 $(i,\mathrm{\Delta })$ 只改变 $y_{h(i)}$；估计坐标 $i$ 时计算 $s(i)y_{h(i)}$，碰撞项因随机符号而在期望中抵消，多行中位数再控制失败概率。

若流依次为 $(a,+4),(b,+2),(a,-1)$，最终 sketch 与一次性频率 $(3,2)$ 相同，体现更新顺序无关与 turnstile 兼容。两台机器采用同一 $h,s$ 时桶数组逐项相加正好是全局状态。

空间、种子与数值域 ​

显式矩阵可能有“摘要维数乘宇宙大小”个元素，远超状态预算。实际实现只保存短哈希种子和 sketch 坐标，在更新时由 $i$ 生成所需列 $S{e}_i$。若生成一列需要扫描整个矩阵，空间虽省下，更新时间目标仍未达到。

两个站点若使用 $S_1,S_2$，直接相加 $S_{1}f+S_{2}g$ 不等于共享 $S(f+g)$。seed、哈希族版本、有限域或整数模数都属于合并协议。计数器位宽也必须覆盖可能的频率范围；整数溢出若不在预定模域内，会破坏线性等式。

随机保证还要说明流与查询是否在抽取 $S$ 后自适应。固定输入的高概率界不自动抵抗攻击者逐次查询并学习矩阵核；需要限制查询、刷新随机性或采用专门的鲁棒结构。

不是所有可合并摘要都线性 ​

Reservoir sampling 保存样本身份并按到达位置随机替换，滑动窗口依赖时间边界；两条具有相同最终频率向量的流可能需要不同状态，所以它们不能写成只依赖 $f$ 的 $Sf$。

Misra–Gries 有经过证明的 merge 过程，却要合并计数器后重新压缩，并非严格的向量加法。可合并性要求存在正确组合状态的运算；线性 sketch 是其中代数最简单、但并不覆盖全部摘要的一类。

保证边界 ​

同一个 $Sf$ 可以服务点查询、范数估计或稀疏恢复，但 decoder 和维数各不相同。证明“更新与合并正确”只需线性等式，证明“小空间且精确”还需要碰撞、方差或下界分析；不能用前者替代后者。

下界常把 sketch 状态当作一条消息：Alice 对自己的更新得到 $S{f}_A$，把它发送给 Bob；Bob 加上 $S{f}_B$ 后运行 decoder，这正是单向通信协议公理库单向通信复杂度One-way communication complexity限制 Alice 只向 Bob 发送一次消息，由 Bob 结合自身输入输出，并按消息 bit 数衡量代价。。若 decoder 能从合并状态恢复 Bob 指定的某个隐藏坐标，便可嵌入Indexing公理库Indexing 通信问题Indexing communication problem · INDEX problemAlice 持有 n-bit 串、Bob 持有索引并要恢复对应 bit 的单向通信问题，是流式与摘要空间下界的标准母问题。并把其通信下界转成 sketch 位数下界。这里发送的是包含种子、数值精度与全部计数器的实际状态，而不只是矩阵行数；若 Bob 还需向 Alice 反馈，或双方矩阵不同，模拟就不再是同一单向协议。