插入流与 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公理库Count–Min SketchCount-Min Sketch · CMS用多行哈希计数器给非负频率提供不低估、带全局 L1 加性误差的点查询。 的单边上界依赖当前频率非负，因此也适用于 strict turnstile；先 $+3$ 再 $-2$ 的碰撞键只留下 $+1$ 的噪声。线性 sketch 的状态是 $Af$，更新接口可以接收正负 $\mathrm{\Delta }$，但这不自动保证其解码器适用于允许负频率的一般 turnstile。若要在多个时刻或自适应输入上使用概率界，还须另查随机性与失败概率约定。

分布式合并 ​

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

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

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

与动态集合的分界 ​

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

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