线性 Sketch

代数接口 ​

对Turnstile 流公理库插入流与 Turnstile 流Insertion-only stream · Turnstile stream以频率向量更新语义区分非负插入、严格 Turnstile 与一般正负流。的频率向量，选择随机矩阵或隐式线性映射 (S)，保存 (y=Sf)。更新 ((i,\Delta)) 只做 [ y\leftarrow y+\Delta Se_i. ] 两段流频率为 (f,g) 时 [ \operatorname{sketch}(f+g)=Sf+Sg, ] 所以机器摘要可逐坐标相加，前提是共享同一矩阵、数值域和坐标编码。

线性只描述状态更新。解码器可以取中位数、求最小值或运行稀疏恢复，因此不必是线性的；摘要维数、误差与失败概率仍需针对 query 单独证明。

CountSketch 状态轨迹 ​

一行 CountSketch 选择桶哈希 (h:[n]\to[b]) 与符号 (s:[n]\to{\pm1})，维护 [ y_j=\sum_{i:h(i)=j}s(i)f_i. ] 更新 ((i,\Delta)) 只改变 (y_{h(i)})；估计坐标 (i) 时计算 (s(i)y_{h(i)})，碰撞项因随机符号而在期望中抵消，多行中位数再控制失败概率。

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

空间、种子与数值域 ​

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

两个站点若使用 (S_1,S_2)，直接相加 (S_1f+S_2g) 不等于共享 (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 反馈，或双方矩阵不同，模拟就不再是同一单向协议。

参考资料

• Alon, Matias, Szegedy, 1999.
• Cormode, Muthukrishnan, “An Improved Data Stream Summary,” 2005.
• Li, Nguyen, Woodruff, linear sketch lower bounds, STOC 2014.