插入流与 Turnstile 流

一条序列的逐态判定 ​

从 $f_a=0$ 开始，序列

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

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

范数与查询定义 ​

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

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

分布式合并 ​

两个站点产生局部频率 $f^{(1)},f^{(2)}$，全局向量是二者之和。若共享随机矩阵 $A$，linear sketch 可合并为

若各站只见插入，合并后仍是插入流；若站点用正负日志互相抵消，全局接口就至少需要 turnstile 语义。

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

与动态集合的分界 ​

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

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