流式分位数摘要 | Codeboy's Blog

形式陈述

保证定义

在数据流模型中，依次读取全序集合中的值 $x_1,\ldots,x_m$ ，本页选择单位插入、 $m\ge1$ 的版本。目标分位 $\phi\in[0,1]$ 对应整数秩

r=\max\{1,\lceil\phi m\rceil\}\in\{1,\ldots,m\},

因此两端分别取最小值与最大值。给定 $0<\varepsilon<1/2$ ，近似查询返回某个已见值 $v$ 。记它在排序后的全部出现位置为

L(v)=1+\#\{t:x_t<v\},\qquad H(v)=\#\{t:x_t\le v\}.

要求 $[L(v),H(v)]\cap[r-\varepsilon m,r+\varepsilon m]\ne\varnothing$ ，等价于返回值至少占据一个距目标不超过 $\varepsilon m$ 的秩。这个顺序统计量约定保留重复次数；它不要求整个并列区间都在误差带内。空流没有已见值可返回，应报告无值。

GK 型秩证书

为清楚区分重复出现，证明中暂按“值、到达位置”作稳定排序。摘要保存按这个次序排列的代表 $(v_i,g_i,\Delta_i)$ ，其中 $g_i\ge1$ 、 $\Delta_i\ge0$ ，并给其真实出现秩 $R_i$ 维护证书

r_{\min}(i)=\sum_{j\le i}g_j \le R_i\le r_{\max}(i)=r_{\min}(i)+\Delta_i.

最小和最大出现位置始终保留，且它们的证书精确为 $1$ 和 $m$ 。当 $2\varepsilon m\ge1$ 时，若所有元组满足

g_i+\Delta_i\le2\varepsilon m,

就能保证全部分位查询的秩误差。流很短、 $2\varepsilon m<1$ 时，先保留全部项并精确选择；此时不能要求每个正整数 $g_i$ 小于 $1$ 。

证书的局部维护可以直接核验。新项插到相邻代表之间时，令新 $g=1$ ，并取 $\Delta=g_{\text{右}}+\Delta_{\text{右}}-1$ ；它的秩至少为旧左证书下界加一，至多为旧右证书上界。插入新极值时取 $(g,\Delta)=(1,0)$ 。删除既非首项也非末项的元组 $i$ 时，将其 $g_i$ 加给右邻居，保留右邻居的 $\Delta$ ；右邻居及后续代表的秩证书都不变。只在

g_i+g_{i+1}+\Delta_{i+1}\le\lfloor2\varepsilon m\rfloor

时执行这次压缩，就保留 gap 上界。

经典 Greenwald–Khanna（GK）算法还按剩余容量的层级安排压缩，并控制每层保留的元组数，取得 $O(\varepsilon^{-1}\log(2+\varepsilon m))$ 个元组的最坏空间界。秩证书与合法局部删除证明负责准确性；这一空间界还依赖其分层和压缩调度，不能仅从“只执行合法删除”推出。

直觉

流式分位数摘要不必保存每个数值，只需让一组有序代表值携带它们可能覆盖的秩区间。相邻代表的区间宽度受控时，查询目标秩便能从证书中选出误差不超过预算的返回值；分位数精度衡量的是秩，不是数值距离。

例子与边界

延迟 p99 例子

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

随机、合并与边界

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

推论与应用

从证书选出返回值

令 $\tau=\varepsilon m$ ，并先处理上述精确保留的小流分支。否则扫描元组，找首个满足 $r_{\max}(j)>r+\tau$ 的位置 $j$ 。如果找不到，返回最大代表：其真实秩 $m$ 满足 $r\le m\le r+\tau$ 。若找到了，最小代表的上界是 $1\le r+\tau$ ，所以 $j\ge2$ ，可以返回前一个代表。由“首个”知

r_{\max}(j-1)\le r+\tau,

同时

r_{\min}(j-1) =r_{\max}(j)-(g_j+\Delta_j) >r+\tau-2\tau=r-\tau.

所以前一个代表的整个秩证书落在允许带内，真实出现秩也落在其中。最终丢弃到达位置、只返回值后，它的并列秩区间自然与该带相交。这给出一个明确的扫描规则和输出证书。

例如排序值为 $[1,2,2,2,9]$ ， $r=3$ 时返回值 $2$ 的秩区间是 $[2,4]$ ，包含精确目标。若只把它记为“秩等于第一次出现的位置 2”，就可能把正确答案误判为超出一个很小的误差带。反过来，排序值 $[1,2,3,10^9]$ 中只移动一个秩，就可能跨过巨大的数值间隔。

更新和合并的适用范围

删除或负权更新会让秩随时间向两侧移动，需要相应版本重新维护证书。滑动窗口还须处理过期项，不能只运行普通 insertion-only 更新。

原始确定性 GK 的标准空间分析也不证明“两份元组直接拼接并沿用原 $\Delta$ ”是正确合并：局部秩证书必须先转换为全局证书。分布式场景应使用具有明确 merge 保证的变体，或选取带失败概率声明的随机摘要。

参考资料

Michael Greenwald, Sanjeev Khanna, Space-Efficient Online Computation of Quantile Summaries, SIGMOD, 2001，§2.1 Proposition 1 与 Corollary 1、§2.2–2.3：秩证书、删除及分层空间分析。
Zohar Karnin, Kevin Lang, Edo Liberty, Optimal Quantile Approximation in Streams, FOCS, 2016.

形式陈述 ​

保证定义 ​

GK 型秩证书 ​

延迟 p99 例子 ​

随机、合并与边界 ​

从证书选出返回值 ​

更新和合并的适用范围 ​

反向链接