滑动窗口流模型

窗口左边界不断推进，但小空间摘要通常已经忘记最旧的单项身份。可行方法把历史压成带时间范围的桶或后缀锚点：边界之外的整段直接丢弃，边界之内的整段完整保留，只让极少数跨界摘要承担可控误差。

Exponential Histogram ​

以最近窗口中的 1 计数为例。Exponential Histogram 把相邻 1 聚成时间有序的桶，每个桶保存大小与最新或最旧边界时间。对每个二次幂大小，只允许 $O(1/\epsilon )$ 个桶；同级桶过多时，合并最旧的两个为下一等级。

查询时完整计入所有完全处在窗口内的桶，只对跨过左边界的最旧桶作部分估计。除这一桶外，其余桶要么全部有效，要么已整体删除；分级数量界控制了最旧桶相对总量的影响，从而得到指定的近似误差。

状态演化可取 $W=8$，流的 1 出现在序号 $1,2,4,5,8,9$。到序号 9 查询时，有效范围是 $2\dots 9$，序号 1 已过期。算法不会保存六个独立位置，而是让较老的 1 落入较大桶；边界只穿过最老的一个桶，其余桶仍可整块计数。

Smooth Histogram 框架 ​

对满足平滑性条件的非负函数 $f$，Smooth Histogram 保存一串递增起点

及各后缀 $t_i\dots t$ 的流摘要。若相邻后缀的函数值过于接近，就删除中间锚点；新更新到达时扩展所有保留摘要，窗口左端越过某锚点后再淘汰它。

查询选择夹住真实窗口起点的两个锚点，利用函数的平滑性把较长后缀的近似转成窗口近似。这里需要函数级定理，不能仅因摘要“可合并”就断言它支持删除任意前缀。

最近一小时 distinct count ​

网站以事件时间统计最近一小时独立用户。系统可在若干锚点维护 distinct sketch：10:00、10:20、10:35、10:47 等后缀摘要随新用户 ID 更新。当查询时刻从 11:00 推进到 11:08，10:00 锚点已经完全在窗口外，10:20 一带的摘要成为覆盖左边界的候选。

若使用 HyperLogLog 等摘要，合并寄存器可以组合不相交时间段，但不能从“截至现在”的寄存器中减去 10:00 前的用户。锚点框架负责过期语义，distinct sketch 负责每个后缀的集合基数估计；两者的误差和失败概率要共同配置。

同一用户在多个时间段重复出现不会给并集增加新元素。这也是不能用各桶 distinct 估计值直接相加的原因；必须合并能够处理重复的摘要状态，或采用为窗口 distinct 专门证明的结构。

乱序时间戳 ​

若输入按事件时间有序，过期判断只需比较队首时间。真实系统常允许迟到 $L$：可用 watermark 声明时间戳不早于 $\tau -L$ 的事件已基本到齐，并在 watermark 推进时关闭旧桶。

晚于容忍范围才到达的事件必须有明确策略：丢弃、修正历史结果，或触发重算。把处理时间窗口写成事件时间窗口，却没有 watermark 和迟到规则，会使同一输入因网络调度不同而产生不同含义。

边界与对照 ​

滑动窗口不同于 turnstile 流。后者由输入显式给出正负更新，算法看到删除的是哪个键；窗口模型的删除由位置或时钟自动触发，键可能早已被压缩掉。它也不同于保存最后 $W$ 项的普通队列，后者精确但空间线性。

窗口大小若小于一个桶、查询时间倒退、时间戳重复或窗口突然改长，都需要接口约定。经典算法通常假设窗口参数固定且查询时钟单调；动态扩大的窗口无法恢复已经丢弃的历史。