Q-Digest 算法简介
introduction 数据结构在设计时考虑了传感器网络，其中最小化无线电传输开销是非常重要的。它最初出现在 “Medians and Beyond: New Aggregation Techniques for Sensor Networks” 由 Shrivastava 等人提出． example Q-Digest 只是一个完整的二叉树，在值的范围内，其中叶节点本身就是值。在下面的例子中，我们对包含 1 到 4 的值进行了摘要，我们看到值 1 和值 4 都是 7 次。 新颖性是压缩算法，它允许低频值在树上传播并合并。在下面的例子中，我们有一些信息丢失。我们知道在 1 和 2 之间有 10 个值，但是我们不知道每个值的确切数量 在构建 qdigest 时，要记住一个不变的因素。一个节点，其兄弟和它的父节点的总数必须大于 n / k，其中 n 是所有计数的总和，k 是我们选择的压缩因子。根节点是一个例外。在本文中，这被称为属性 2. 属性 1 指出，除非是叶节点，否则节点的数量必须小于 n / k。在原始文件中使用属性 1 来证明对 qdigest 的一些保证。 requirement 数据结构提供了一些很好的保证，使其非常实用： 给定一个压缩因子 k，摘要的大小不会超过 3k 合并两个 q - 摘要时，如分布式设置中常见的那样，所有必须做的就是将这两个 q - 摘要合并，并运行压缩算法。这比 GK 算法的分布式扩展简单得多。 在回答分位数查询时，误差受 log（σ）/ k 限制，其中σ是存储在摘要中的值的最大范围。因此，我们对中位查询的回答总是在 0....