框架总览
三个组件，前两个组件压缩梯度值，第三个组件压缩梯度键
- Quantile-Bucket Quantification
- MinMaxSketch
- delta encoding
编码阶段
- Quantile Sketch用于生成候选分割，我们使用桶排序来总结梯度值。
- 梯度值由桶的索引表示。
- 通过对键应用哈希函数，将桶索引插入MinMaxSketch。
- 将梯度键转换为增量，本文用增量键表示。
- 我们使用二进制编码用更少的字节来编码delta键，而不是使用四字节整数。
解码阶段
- 增量键恢复到原始键。
- 使用恢复的密钥查询MinMaxSketch。
- 每个值的桶指数由示意图得到。
- 通过使用bucket索引查询bucket值来恢复该值。
Quantile-Bucket Quantification
步骤1:分位数分裂
- 我们扫描所有的梯度值并将它们插入分位数草图。
- q分位数用于从分位数草图中提取候选分位数。具体来说，我们生成了q的平均分位数{0,1/q,2/q,…,q-1/q}。
- 我们使用分位数和最大值作为分割值，用{rank(0),rank(1/q)， rank(2/q),…,rank(1)}。注意，值位于两个连续分割之间的项的数量是N/q，这意味着我们用项的数量而不是值除以项的数量。两个分割之间的每个区间都有相同数量的梯度值。
步骤2:桶排序
- 我们称两次分割之间的每个间隔为一个桶。
- 较小的分割是桶的较低阈值，较大的分割是较高的阈值。
- 根据桶的阈值，每个梯度值属于一个特定的桶。例如，图3中0.21的值被分类到第四个桶中。
- 每个桶用均值表示，即平均值。
- 将每个梯度值转换为对应的桶均值。
步骤3:索引编码
虽然我们用桶的平均值来量化梯度值，但是所消耗的空间是相同的。为了降低空间成本，我们选择了存储bucket索引的替代方法。我们将桶的平均值编码为桶索引。例如，将0.21量化为用均值表示的第四个桶之后，我们通过桶索引从零开始对其进行编码，即0.21对应的是数字3。
步骤4:二进制编码
通常，桶的数量是一个小整数。我们通过将bucket索引编码为二进制数来压缩它们。如果q=256，一个字节就足够对bucket索引进行编码。通过这种方式，我们将占用的空间减少，我们可以在很大程度上减少传输的数据。
MinMaxSketch
插入的阶段
每个输入项由原始密钥和已编码的桶索引(kj,b(vj))组成。
使用s哈希函数计算哈希码。在图5中，有三个哈希函数，h1(-)、h2(-)和h3(-)。
在第i个哈希表中选择一个哈希bin后，比较当前值H(i,hi(kj))和b(vj)。如果H(i,hi (kj)) > b(vj)，我们用b(vj)替换当前值。否则，我们不更改当前值。
查询阶段
输入为梯度键，用kj表示。s哈希函数应用于kj，每个哈希函数从哈希表中选择一个哈希bin。
给定不同行的s个候选项，选择最大的作为最终结果。在图5中，三个候选项是{0,2,2}，我们选择2作为结果。
Delta-Binary Encoding
通过对梯度键数据分布的分析，发现梯度键具有三个特征。
首先，键是非重复的。
其次，键按升序排列。
第三，尽管在许多高维应用中键可以非常大，但是相邻键之间的差别要小得多。
基于以上三点，我们建议只存储键的增量。
步骤1:增量编码
梯度键存储在数组中。我们从头到尾扫描数组，并计算两个相邻键之间的差值。然后，我们得到键的增量，我们称之为键。
步骤2:二进制编码
通过增量编码，很明显增量键要比原始键小得多。
如果我们以整数或长整数的格式存储delta键，那么压缩是没有意义的，因为所消耗的内存空间和通信成本保持不变。
为了解决这个问题，我们将不同的空间分配给不同的delta键，并将它们编码为二进制格式。