两种窗口语义
设流更新依次到达。计数窗口给定 (W)，在时刻 (t) 只保留序号 [ \max(1,t-W+1),\ldots,t ] 的最近 (W) 项。时间窗口给定持续长度 (\Delta)，在查询时钟 (\tau) 只让时间戳落入 ((\tau-\Delta,\tau]) 的更新生效。
端点必须写清。把左端改为闭区间，会使恰在 (\tau-\Delta) 的事件多存一个查询时刻；在高频边界上，这不是可忽略差异。窗口查询也要标明返回精确值、加性近似、相对近似，还是以概率至少 (1-\delta) 成立。
过期不是一次反向更新
最直接实现是队列保存所有活跃项，到达时入队，越过边界时出队。这需要 (\Theta(W)) 项空间。滑动窗口流算法希望在远小于 (W) 的空间中近似统计，因此通常无法记住每个将来要删除的元素。
append-only 摘要也不能直接复用。某元素过期时，算法未必还知道它是什么；而 distinct、分位数等摘要通常没有可逆的“减去最旧项”操作。有效结构要把历史压缩成带时间范围的桶或多个锚点摘要，使整段历史能够按边界批量淘汰。
Exponential Histogram
以最近窗口中的 1 计数为例。Exponential Histogram 把相邻 1 聚成时间有序的桶，每个桶保存大小与最新或最旧边界时间。对每个二次幂大小，只允许 (O(1/\varepsilon)) 个桶；同级桶过多时，合并最旧的两个为下一等级。
查询时完整计入所有完全处在窗口内的桶，只对跨过左边界的最旧桶作部分估计。除这一桶外，其余桶要么全部有效，要么已整体删除；分级数量界控制了最旧桶相对总量的影响，从而得到指定的近似误差。
状态演化可取 (W=8)，流的 1 出现在序号 (1,2,4,5,8,9)。到序号 9 查询时，有效范围是 (2\ldots9)，序号 1 已过期。算法不会保存六个独立位置，而是让较老的 1 落入较大桶；边界只穿过最老的一个桶，其余桶仍可整块计数。
Smooth Histogram 框架
对满足平滑性条件的非负函数 (f)，Smooth Histogram 保存一串递增起点 [ t_1<t_2<\cdots<t_k ] 及各后缀 (t_i\ldots 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) 项的普通队列，后者精确但空间线性。
窗口大小若小于一个桶、查询时间倒退、时间戳重复或窗口突然改长，都需要接口约定。经典算法通常假设窗口参数固定且查询时钟单调；动态扩大的窗口无法恢复已经丢弃的历史。
参考资料
- Mayur Datar, Aristides Gionis, Piotr Indyk and Rajeev Motwani, Maintaining Stream Statistics over Sliding Windows, SIAM Journal on Computing, 2002.
- Vladimir Braverman and Rafail Ostrovsky, Smooth Histograms for Sliding Windows, FOCS, 2007.
- Graham Cormode, The Continuous Distributed Monitoring Model, SIGMOD Record, 2011.