---

0.前言

  XGBoost不仅在单机上通过OMP实现高度并行化，还通过MPI接口与近似分位点算法（论文中是weighted quantiles sketch）实现高效的分布式并行。其中weighted quantiles sketch框架基于$\epsilon$-approximate quantile近似分位点算法。不得不说分位点算法在分布式系统、流式系统中使用是个很天才的想法，很多分布式算法的基石。早在2001年，M.Greenwald和S. Khanna提出了GK Summay分位点近似算法（ϵ−approximate ϕ−quantile），直到到2007年被Q. Zhang和W. Wang提出的多层level的merge与compress/prune框架进行高度优化，而被称为A fast algorithm for approximate quantiles，目前XGBoost框架套用A fast algorithm算法结构。

  本文主要介绍GK Summay算法，后续博客会持续更新分布式GK Summay算法以及A fast algorithm for approximate quantiles算法，最后还会分析XGBoost中使用的weighted quantiles sketch算法，博客内容来源主要是原始论文与Emory大学的流式数据库的课程内容，本文仅提取出关键内容加入笔者的个人理解，有错误还望谅解与告知。

1.背景

  $\phi-quantile$分位点概念：排序为$rank = \lfloor \phi N \rfloor$的元素，其中$N$为序列中元素的个数。考虑以下例子数据：

$$11 \ ,\ 21 \ ,\ 24 \ ,\ 61 \ ,\ 81 \ ,\ 39 \ ,\ 89 \ ,\ 56 \ ,\ 12 \ ,\ 51$$

  查询

ϕ−quantile
$\phi-quantile$分位点所在数据前，需要对无序数据进行排序：

$$\begin{array}{cc}input:&11&21&24&61&81&39&89&56&12&51 \\sort:&11&12&21&24&39&51&56&61&81&89 \\rank:&1&2&3&4&5&6&7&8&9&10\end{array}$$

  排序后很容得到：

0.5−quantile
$0.5-quantile$对应

rank=5
$rank=5$，值为39。 此外还有，

0.1−quantile
$0.1-quantile$对应

rank=1
$rank=1$，值为11。

  $\epsilon-approximate \ \phi-quantile$分位点概念：考虑误差近似，即给定误差$\epsilon$和分位点$\phi$，只需要给定排序区间$r^ \prime \in [(\phi-\varepsilon) N, \ (\phi+\varepsilon) N]$内任意元素即可。类似地，给定$\varepsilon=0.1, ϕ=0.5$，可得rank值在区间$\{4,5,6\}$。给定区间内任意元素，都满足排序误差$\epsilon N$要求。

  为了满足对数据近似分位点的频繁查询，考虑以下几种场景：

  1. 固定不变的数据集
  2. 流式数据，数据长度不断增加
  3. 数据源分布存储，但数据长度固定
  4. 数据源分布存储+流式数据，数据长度不断增加

  对于场景1，可以对数据进行预排序，每次查询采用二分法精确查找，时间复杂度为$O(\log N)$。考虑排序误差$\epsilon N$， 我们可以对数据进行分桶，分桶长度为$\epsilon N$来保证误差，即分$1/\epsilon$个桶，时间复杂度降低为$O(\log (1/\epsilon))$，简单的离线排序和分桶都属于offline算法，无法满足场景2、3、4场景，这就需要本文介绍online算法来构建查询summary。

2. GK Summary算法

2.1 GK Summary定义

  GK Summary原本是针对流式系统分位点查询设计的，基于上述场景2。对于$\epsilon-approximate$分位点查询，可以构建查询summary结构，包含$m$个summary tuple的集合：

$$\{ (v_1,min_1,max_1), (v_2,min_2,max_2）, ..., (v_m,min_m,max_m) \}$$

  
定义：

vi
$v_i$为命中第

i
$i$个summary的代表值，简单起见，



vi

$v_i$定义为

rank=mini
$rank=min_i$对应值，summary的

rank
$rank$区间为

[mini,maxi]
$[min_i, max_i]$。

  
约束：为了满足给定误差

ϵN
$\epsilon N$，

maxi−mini≤ϵN
$max_i - min_i \leq \epsilon N$。证明：显而易见。

  流式数据是不断更新，这种summary结构存在缺点：每次插入中间值，需要更新插入位置后面的summary，更新复杂度高。流式数据插入更新频率比查询频率要更高，必须优先解决数据插入构建summary的复杂度。

  对此，Greenwald与Khanna提出对数据插入更新友好的GK Summary结构，相对于存绝对值，GK Summary采用相对值的结构，类似地，包含$m$个summary tuple的集合：

$${(v_0,g_0,Δ_0), (v_1,g_1,Δ_1), ..., (v_{s-1},g_{s-1},Δ_{s-1}) }$$

  
定义：

vi
$v_i$为命中第

i
$i$个summary的代表值，



rmin(v)

$r_{min}(v)$为

v
$v$所在summary的下界，



rmax(v)

$r_{max}(v)$为

v
$v$所在summary的上界，则



gi

$g_i$、

Δi
$Δ_i$定义如下：

$$g_i=\begin{cases}r_{min}(v_i) - r_{min}(v_{i-1})&, \ i > 0 \\1&, \ i=0\end{cases}$$

$$Δ_i=\begin{cases}r_{max}(v_i) − r_{min}(v_i)&, \ i < s-1 \\0 &#038;, \ i = s-1 \end{cases}$$

  为了便于理解，

gi
$g_i$、

Δi
$Δ_i$关系如下图：

  
边界条件：

v0
$v_0$为数据中最小值，

vs−1
$v_{s-1}$为数据中最大值。等价于第一种定义的summary，排序相对值转化为绝对值，满足以下性质：

  性质1：$r_{min}(v_i) = \sum_{j=0}^i g_i$， 由$g_i$定义，可以证明：

$$\begin{align}r_{min}(v_i) &=g_i + r_{min}(v_{i-1}) \\&=g_i + g_{i-1} + r_{min}(v_{i-2}) \\&\vdots \\&=g_i + g_{i-1} + g_{i-2}... + r_{min}(v_0) \\\end{align}$$

  
此外，边界设定

rmin(v0)=g0=1
$r_{min}(v_0)=g_0=1$
，得证。

  性质2：$r_{max}(v_i) =\sum_{j=0}^i g_i + Δ_i$ , 由性质1与定义$Δ_i=r_{max}(v_i) − r_{min}(v_i)$可得
  性质3：$\sum_{j=0}^{s-1} g_i = N$, 由性质2与边界设定$Δ_{s-1}=0$可得。

  约束：为了满足给定误差$\epsilon N$，$\max\limits_{i} (g_i + Δ_i) \leq 2\epsilon N$。证明如下：
  设最大误差为$e=\max\limits_{i} (g_i + Δ_i) / 2$, 则$\forall \ g_i + Δ_i \leq 2e \leq 2\epsilon N$
  1) 首先考虑边界情况：$r > N-e$, 直接返回$v_{s-1}$，对应$rank=N$，此时误差为$N-r < e$
  2) 一般情况：$r \leq N-e$, 找到最小的$j$，使得$r_{max}(v_j) > r + e$，必有$r_{max}(v_{j-1}) \leq r + e$。

$$\forall \ g_i + Δ_i \leq 2e \Rightarrow r_{min}(v_{j-1}) = r_{max}(v_j) - (g_i + Δ_i) > r - e$$

  因此，查询返回为

vj−1
$v_{j-1}$, 其代表区间在

[r−e,r+e]
$[r - e, r + e]$内，满足误差

ϵN
$\epsilon N$要求，得证。更直观的图示如下：

  
Summary查询过程：上述证明揭示了对于任意分位点

ϕ
$\phi$，计算出排序位置

r
$r$：1）找到最小



j

$j$，使得

rmax(vj)>r+e
$r_{max}(v_j) > r + e$，则返回

vj−1
$v_{j-1}$值，2）如果找不到则返回

vs−1
$v_{s-1}$。

  只要流式系统中每个时刻都维持这种summary结构，每次查询都能满足精度要求，但是流式数据实时更新，需要解决新增数据的summary更新问题。

2.2 GK Summary插入insert

  流式系统数据实时更新，不断产生新数据，数据量不断增加，尽管查询近似度$\epsilon$不变，随着数据量增加，$\epsilon N$不断变大。为了保证误差，任何时刻都要保证满足约束$\max\limits_{i} (g_i + Δ_i) \leq 2\epsilon N$。首先考虑数据$v$插入情况的summary更新：
  1) 最小值边界情况：$v < v_0$，则插入summary为$(v,1,0)$
  2) 最大值边界情况：$v > v_{s-1}$， 则插入summary为$(v,1,0)$
  3) 一般情况：$v_{i-1} \leq v < v_{i}$，则插入summary为$(v,1,g_i + Δ_i - 1)$

  证明：对于情况1）与2），显而易见的。对于情况3）：

  summary内部tuple按照对应的$v$排序，新增summary是插入到第$i-1$个summary后面，前$i-1$个summary不受影响，对于后面的$i$到$s-1$的summary来说，对应$rank$值均增加，$r_{max}$与$r_{min}$均需加1，因此$g$、$Δ$均不需要改变，也就满足了误差约束条件。这里可以看出：与前文提到的summary相比，GK Summary对于新增数据无需更新其他summary。
  新增summary必须满足$g \geq 1$， $g +Δ \leq g_i + Δ_i$，如果不满足则没有必要插入，因为前后2个summary可以覆盖新增的summary，选择$g=1$的主要原因是有利于后期summary的delete，后续会谈到，设置$Δ=g_i + Δ_i - 1$能使得$g + Δ \leq 2\epsilon N$，原则上$Δ \leq \lfloor 2 \epsilon N \rfloor - 1$任意值即可，后续可以看到新增非边界的summary tuple的$Δ = \lfloor 2 \epsilon N \rfloor - 1$。

2.3 GK Summary删除delete与compress

  每次数据插入都需要新增summary，summary不能持续增加而不删除，因此到达一定程度需要对summary进行delete。为了时刻满足$\max\limits_{i} (g_i + Δ_i) \leq 2\epsilon N$，GK Summary 的delete操作：
  如果存在：$g_j + ... g_i + g_{i+1} + Δ_{i+1} \leq 2\epsilon N$，
  则可以用$(v{i+1}, g_j + ... + g_i+g_{i+1}, Δ_{i+1})$来替代$\{(v_j, g_j, Δ_j) ... (v_i, g_i, Δ_i), (v_{i+1}, g_{i+1}, Δ_{i+1})\}$
  换句话说：
  1）删除summary集合：$\{(v_j, g_j, Δ_j) ... (v_i, g_i, Δ_i)\}$
  2）更新$(v_{i+1}, g_{i+1}, Δ_{i+1}) \Rightarrow (v{i+1}, g_j + ... + g_i+g_{i+1}, Δ_{i+1})$

  delete操作特性：只改变$v_{i+1}$所在summary的$g_{i+1}$, 并不改变$Δ_{i+1}$。也就是说$Δ$越小，在满足误差约束下，具有合并更多summary的潜力。

  为了追求效率，根据delete性质，GK提出compress操作，首先说明论文的概念：
  1. Fullness: 如果$g_i + Δ_i = \lfloor 2 \epsilon N \rfloor$，则说明该summary tuple是full的
  2. Capacity：由于delete操作$Δ$不变性，因此summary达到full，$g$最终为$\lfloor 2 \epsilon N \rfloor$ - $Δ$，因此$Δ$决定了summary tuple的capacity。
  3. Bands：compress操作主要是减少summary总数，每个summary的元素覆盖数coverage取决于$g$， 因此需要保持$g$值尽量大，对应$Δ$尽量少，也就是说$Δ$值小的summary应该越多，引入$bands$主要是对$summary$进行分级，对于给定$Δ$与$p=\lfloor 2 \epsilon N \rfloor$，可以计算$band$值为：

$$capactity=p - Δ \\band= \lfloor\log_2(capactity)\rfloor$$

  对于$band=\alpha$，$capactity$区间为$[2^{\alpha },2^{\alpha+1})$， $Δ$对应区间$(p - 2^{\alpha+1 }, p - 2^{\alpha}]$，注意开闭区间。$band$值越大，$Δ$越小，capacity能力越大。考虑合并策略：对于相连$summary_i$, $summary_{i+1}$合并，合并更新到$band$值较小的$summary$上，由于delete的$Δ$不变性，保留$band$值大的，有更大的$capacity$，后期能够容纳更多的summary。对每个summary都包含$Δ$，可以组织成$bands￥树结构，如下图所示：

  
$band$树结构特性：对于节点$V$,其所有子节点与$V$在$summary$中是连续相连的。

  $summary$更新过程中如何保证这一性质？

  1）每次新数据会插入新$summary$，$Δ=\lfloor 2\epsilon N \rfloor - 1$, 对应$band=0$，为最小值，除非单独节点，否则一定为右边节点的子节点。
  2）合并策略：对于$summary_i$, $summary_{i+1}$合并，合并更新到$band$值较小的$summary$上。

  因此，上述操作会维持这种$band$树结构性质。此外，满足上述条件，论文中给出基于$band$的compress算法：

  算法从右往左扫描，其中 $g^*$为当前节点与其所有子节点 $g$总和，如果遇到：$BAND(Δ_i, 2 \epsilon n) \leq BAND(Δ_{i+1}, 2 \epsilon n)$ 且 $g_i^* + g_{i+1} +Δ_{i+1} < 2 \epsilon n$, 删除 $i$节点与其子节点对应summary tuple。

2.4 GK Summary算法

  此外，需要明确compress操作执行时机：有时候原来的summary是不可合并的，但是随着数据量$N$增加， $p=2\epsilon N$相应增大， $band$、 $capacity$值是会随着阶段性不断变大的，而出现可合并的情况. 论文给出数据每增量 $1/2\epsilon$时，会执行compress操作。因为这种情况下误差值绝对值增量为 $2\epsilon \times 1/2\epsilon = 1$，原本不满足误差约束条件的情况会发生改变，否则正常插入数据到summary，算法如下：

  论文还证明了以下性质和结论，由于章节内容过多，下面仅放置结论，首先继续说个概念：
  Coverage：每个summary tuple会cover新增数据，对于$summary_i$，cover数据来源：1）直接cover：即单个数据插入生成的summary直接merge到$summary_i$；2）间接cover：即该数据原本被merge到$summary_j$， 而$summary_j$又merge到$summary_i$。每个数据初始插入都为$(v,1,\lfloor 2\epsilon N \rfloor - 1)$，开始阶段$Δ$ =0，其中$g$为summary数据覆盖量。

  性质1：任何时刻，$band=\alpha$的summary覆盖的数据点不可能来源于$band=\beta$的summary，其中$\beta > \alpha$
  性质2：任何时刻，所有$band\in[0,\alpha]$构成的summary集合，覆盖数据总和数上界为$2^\alpha/\epsilon$
  性质3：任何时刻，给定$band=\alpha$，最多$3/(2\epsilon)$个父节点
  性质4：任何时刻，给定$band=\alpha$，最多$4/\epsilon$个右侧兄弟节点是full的summary
  性质5：任何时刻，$band=\alpha$的summary总数上界为$11/(2\epsilon)$
  结论：任何时刻，summary的总个数上界为：$11/(2\epsilon)\log_2(2\epsilon N)$。性质5直接可得该结论。

---

参考文献

1. GK Summary算法论文：http://infolab.stanford.edu/~datar/courses/cs361a/papers/quantiles.pdf
2. Emory大学Stream DB System课程关于ϵ-approximate ϕ-quantile材料：http://www.mathcs.emory.edu/~cheung/Courses/584-StreamDB/Syllabus/08-Quantile/Greenwald.html
3. Emory大学Stream DB System课程关于GK Summary算法材料：
   http://www.mathcs.emory.edu/~cheung/Courses/584-StreamDB/Syllabus/08-Quantile/Greenwald2.html

今天的文章GK Summay算法（ϵ−approximate ϕ−quantile）分享到此就结束了，感谢您的阅读，如果确实帮到您，您可以动动手指转发给其他人。