插入流与 Turnstile 流

三种更新语义 ​

在数据流模型公理库数据流算法模型Data-stream model · Streaming algorithm输入顺序到达且不能保存全文，以扫描趟数、工作空间、处理时间和输出保证评价算法。中，以频率向量 (f\in\mathbb Z^n) 表示状态，更新 ((i,\Delta)) 令 (f_i\leftarrow f_i+\Delta)。Insertion-only 要求每次 (\Delta\ge0)；strict turnstile 允许负更新，但每个前缀后仍有 (f_i\ge0)。

库存入库是插入流；含出库且库存从不为负是 strict turnstile；两个数据源差值的更正可产生负频率，属于 general。严格模型约束每个时间前缀，仅最终向量非负仍不够。

一条序列的逐态判定 ​

从 (f_a=0) 开始，序列 [ (a,+3),(a,-2) ] 使坐标依次成为 3、1，因而在 strict turnstile 合法。反序执行则经过 (-2,1)，只能属于 general turnstile。两条序列最终向量相同，允许的前缀集合却不同，算法的正确性与下界也可能随之改变。

若实现把负计数饱和截成 0，反序输入会先得到 0、再得到 3，而不是语义要求的 1。这个错误在最终只检查“非负”时不易发现，因此测试必须观察每次更新后的实际频率。

范数与查询定义 ​

Insertion-only 中 (\lVert f\rVert_1=\sum_i f_i) 等于总更新质量并随时间单调。strict turnstile 允许它因删除下降，但坐标仍可解释为库存或次数。general 中正负坐标会在 (\sum_i f_i) 中抵消，heavy hitter 通常要按 (|f_i|) 相对于 (\ell_1) 或 (\ell_2) 范数定义。

“支持删除”不能替代模型名称。Count-Min 一类使用非负计数上界的论证常依赖插入语义；线性 sketch 则因状态是 (Af)，可直接接收正负 (\Delta)。同一查询在三个模型中的误差形式也应分别证明。

分布式合并 ​

两个站点产生局部频率 (f^{(1)},f^{(2)})，全局向量是二者之和。若共享随机矩阵 (A)，linear sketch 可合并为 [ Af^{(1)}+Af^{(2)}=A(f^{(1)}+f^{(2)}). ] 若各站只见插入，合并后仍是插入流；若站点用正负日志互相抵消，全局接口就至少需要 turnstile 语义。

Misra–Gries 等非线性摘要需要专门 merge 后重新压缩，状态字节不能直接逐项相加。可合并也不等于撤销任意历史更新：算法只看净频率状态，未必保留哪条日志产生了它。

与动态集合的分界 ​

动态字典可随机访问并精确保存活动键，空间通常随宇宙中出现的键数增长；streaming 只保留次线性状态，删除后不能回看被遗忘信息。两者都使用“插入/删除”词汇，资源与接口并不相同。

模型还应说明更新值的位宽、流长是否已知、坐标宇宙能否动态增长，以及查询是一次性还是持续输出。这些参数会影响计数器空间和失败概率的合成。

参考资料

• Cormode, Muthukrishnan, data stream surveys.
• Alon, Matias, Szegedy, 1999.