GK 算法简介

GK algorithm introduction 在这里,我们研究了一种算法,该算法可以持续维护汇总信息,并且只需要使用通常需要的一小部分内存就能在小的有界误差范围内回答查询。有许多算法可以解决这个问题,但是我们要研究的是 Greenwald 和 Khanna 在他们的 2001 年的论文 “空间高效的在线计算分位数摘要”。比其他许多算法理解起来要复杂得多,但据我所知,它是空间使用最好的。另外,我们稍后将会研究的其他许多论文将用它来解决有趣的问题。 data structure Greenwald-Khanna(GK 从现在开始)基于一个简单的数据结构。S(n) 这种数据结构包括了一系列排过序的元组,这些元组对应了我们迄今以来观察到的数据的一个子集,对于每个观察到的在 S 中的v,我们维护一个 implicit bound 对于观察点的最大可能的 rank 值和最小可能的 rank 值.令 rmin(v) 和 rmax(v) 分别表示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....

2 min · 250 words · Me

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

1 min · 96 words · Me