流式分位数摘要

保证定义 ​

在数据流模型公理库数据流算法模型Data-stream model · Streaming algorithm输入顺序到达且不能保存全文，以扫描趟数、工作空间、处理时间和输出保证评价算法。中，流长为 $m$，目标分位 $\varphi \in [0,1]$。$\epsilon$-approximate quantile 返回某个已见值 $v$，使其秩区间包含目标且

$$|\mathrm{rank}(v)-\varphi m|\le \epsilon m$$

（重复值时用下秩/上秩区间精确定义）。这是 rank error；值域间隔可能使很小秩误差对应很大数值误差。

Greenwald–Khanna 图像 ​

确定性 GK 摘要保存按值排序的元组 $(v_i,g_i,{\mathrm{\Delta }}_i)$。$g_i$ 是相邻保留值之间的最小秩增量，${\mathrm{\Delta }}_i$ 是额外不确定量，并维护

$$g_i+{\mathrm{\Delta }}_i\le 2\epsilon m$$

的核心不变量。插入定位位置并设初值，周期性把相邻元组在不破坏不变量时合并；查询扫描累积 $g_i$，选择秩区间覆盖目标的值。空间为 $O((1/\epsilon )\log \left(\epsilon m\right))$ 的经典界。

延迟 p99 例子 ​

监控服务延迟时，p99 摘要保证返回值在排序后位置距离 $0.99m$ 不超过 $\epsilon m$。若分布在尾部有大跳跃，返回延迟可能相差数秒，这仍满足秩保证；把它宣称为“数值误差不超过 $\epsilon$”是错误的。

随机、合并与边界 ​

KLL 以随机压缩得到更优空间和可合并性，但失败概率与随机性需单列；GK 的原始确定性结构并非任意合并后保持同一界。流长是否预知、重复值、权重更新及 merge 顺序都会影响版本。普通直方图只有固定 bucket 分辨率，没有自动的秩误差证明。

查询证书 ​

扫描 GK 元组时，前缀 $\sum _{j\le i}{g}_j$ 给 $v_i$ 的最小可能秩，最大可能秩再加 ${\mathrm{\Delta }}_i$。查询选择一个元组，使目标秩落在其可认证区间附近；误差证明直接来自所有元组的 gap 上界，而非假设数据分布平滑。

删除或负权更新会让秩随时间向两侧移动，原始 insertion-only 不变量无法局部修复。滑动窗口 quantile 还要让过期元素离开摘要，需要 exponential histograms 或专门结构。

查询证书如何选出返回值 ​

GK 摘要按值保存三元组 $(v_i,g_i,{\mathrm{\Delta }}_i)$。前缀和 $r_{min}(v_i)=\sum _{j\le i}{g}_j$ 是该值可能的最小秩，最大秩为 $r_{max}(v_i)=r_{min}(v_i)+{\mathrm{\Delta }}_i$；不变量约束相邻不确定度不超过约 $2\epsilon m$。

查询目标秩 $r=\lceil \varphi m\rceil$ 时，从小到大扫描摘要，选择其可行秩区间穿过 $r$ 附近容差带的值，并用 $r_{min},r_{max}$ 作为证书。插入后压缩相邻元组必须验证合并仍满足不变量；只按值接近合并会让秩误差失控。

确定性 GK 的标准形式并非简单可合并摘要。分布式场景若直接拼接两份元组并沿用原 $\mathrm{\Delta }$，局部秩证书不再对应全局流；应使用有正式 merge 保证的变体或改用 KLL 等随机摘要。

参考资料

• Michael Greenwald, Sanjeev Khanna, Space-Efficient Online Computation of Quantile Summaries, SIGMOD, 2001.
• Zohar Karnin, Kevin Lang, Edo Liberty, Optimal Quantile Approximation in Streams, FOCS, 2016.