stream

Bloom Filter introduction 首先，我们假设有四种存储设备，分别是 Tape, HDD, SSD, Memory．当然，我们知道，这四种设备的响应速度是按顺序递增的，也就是说 Memory 的速度最快，当然，我们都希望所有的程序都可以跑在 Memory 中，但是这四种设备的存储大小即容量也是不一样的，价格也是随之递增的．Ex .g 当我们在 Java 中使用 Set 类型去存储数据的时候，数据越多，查询所需的时间越长，同时 Jvm heap 也越大．实际生产环境中的数据量极大，在一些实时性要求比较高的应用当中，不可能将所有的数据都放在 Memory 中，当允许一定的误差的情况下，（即使用准确性去换取实时性，这是一种 tradeoff）这里就提出了，一种　Probabilistic　data structure，它可以在一定程度上去接受一定的误差，从而使响应速度加快，所要存储的数据也大大缩小． Bloom Filter 的概念提出的比较早，早在１９７０年就由一个叫 Bloom（真的叫这个名字）的人在一篇名为＂Space / Time trade-offs in hash coding with allowable errors＂ structure Initial the structure Add an element to this structure query 判断存在还是不存在 If one hash function map to 0, It means NO!（　有一个 map 到０　就不行） But if all hash functions map to 1, it means maybe YES(即使　所有的 hash 函数都能 map 到１，　也不能说明就一定存在，　这里有一定的 false positive，　即认为是正确的，但实际上不是正确的概率)...

GK algorithm introduction 在这里，我们研究了一种算法，该算法可以持续维护汇总信息，并且只需要使用通常需要的一小部分内存就能在小的有界误差范围内回答查询。有许多算法可以解决这个问题，但是我们要研究的是 Greenwald 和 Khanna 在他们的 2001 年的论文 “空间高效的在线计算分位数摘要”。比其他许多算法理解起来要复杂得多，但据我所知，它是空间使用最好的。另外，我们稍后将会研究的其他许多论文将用它来解决有趣的问题。 data structure Greenwald-Khanna（GK 从现在开始）基于一个简单的数据结构。S(n) 这种数据结构包括了一系列排过序的元组，这些元组对应了我们迄今以来观察到的数据的一个子集，对于每个观察到的在 S 中的ｖ，我们维护一个 implicit bound 对于观察点的最大可能的 rank 值和最小可能的 rank 值．令 rmin(v) 和 rmax(v) 分别表示ｖ可能的 rank 的上届和下届．S 包括了 t0,t1,…ts-1 个元组，每一个元组（v，g，Δ）包含了三个元素． vi 表示数据流中实际出现的一个值． gi ＝　rmin(vi) - rmin(vi-1). Δ = rmax(vi) - rmin(vi). 这样，我们可以确保，在任何时刻，最大可能和最小可能都在 description 中．换句话说，v0 和 vs-1 一直表示我们看到的数据流中的最大值和最小值．rmin(vi) = sum(gj),where j<=i. rmax(vi) = sum(gj+Δj),where j<=i ，因此, gi + Δi - 1 是所有数字的上届，sum(gi) = n, 表示所有出现的数字的数量和． 该算法通过相应的插入和压缩算法，以尽量保持尽可能少的元组，同时始终保持对于任何元组我们有 g +Δ<= 2 ε n 的不变量。只要我们能够牢记这一点，算法总会给出正确的ε- 近似的答案。ε的有效值在很大程度上取决于你想要做什么样的查询。例如，如果你想要第 90 百分位数，那么ε= 0....

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....