有限存储下一趟扫描计算近似中值及其他分位数.ppt

有限存储下一趟扫描计算近似中值及其他分位数,Approximate Medians and other Quantiles in One Pass and with Limited Memory 要解决的问题：给定有N个元素的乱序数据集合，怎样计算将这N个数据排序后位于正中间的那个元素(或者位于0.35N位置的元素)？ 分位数(Quantile)：将大小为N的数据集排序后，位于 N(0,1 )位置的元素称为数据集的 分位数。当=0.5时，称为中值(median)。 要计算精确的分位数，考虑将原数据集排序，如果N很大，需要很大的空间(O(N)和很多的处理时间(O(NlogN)。 如果一个元素排序后的位置在 和 之间，我们称之为具有近似度(-approximation)的分位。节省时间和空间。,有限存储下一趟扫描计算近似中值及其他分位数,分位数反应了数据集的分布，如下应用： 数据库的查询优化(例如计算各个字段数据分布的等高柱状图) 从数据集中提取摘要信息 平行运算中的数据集划分 应用要求计算近似分位数时必须保持一定精度,有限存储下一趟扫描计算近似中值及其他分位数,本算法的目标：给定N，和，设计一个一趟扫描算法，以使用尽量少的主存，计算大小为N的数据集的具有近似度的分位数值。 一些约定： 算法只使用b个缓冲区 缓冲区的大小都为k 一个物理的缓冲区可以保存多个逻辑缓冲区，用缓冲区的权重表示代表逻辑缓冲区的个数 不断修正b和k值，使得 保证近似结果的误差范围 bk值尽量小,有限存储下一趟扫描计算近似中值及其他分位数,整个算法简化为三种基本操作 NEW操作，为输入数据集分配缓冲区，缓存输入数据 COLLAPSE操作，合并多个逻辑缓冲区，释放物理缓冲区 OUTPUT操作，在多个缓冲区上输出最后的近似分位数,有限存储下一趟扫描计算近似中值及其他分位数,COLLAPSE操作 多个输入缓冲区 一个输出缓冲区 将输入缓冲区元素排序，均匀采样作为输出缓冲区的元素 输出缓冲区的权重等于输入缓冲区权重之和 COLLAPSE操作的输出可能作为下一次COLLAPSE操作的输入 OUTPUT操作 输入多个缓冲区(COLLAPSE操作的最终结果) 输出一个元素，最终的近似分位数 将输入缓冲区复制权重个拷贝后排序，输出序列中的第 个元素 一个计算近似分位数的算法由一系列NEW操作和COLLAPSE操作组成，最后由一个OUTPUT操作结束。,有限存储下一趟扫描计算近似中值及其他分位数,不同的算法对应于不同的COLLAPSE操作策略：选取什么样的缓冲区合并？选取几个缓冲区合并？ Munro-Paterson算法，每次选两个权重相同的缓冲区合并，对应于二叉树 Alsabti-Ranka-Singh算法，每当b/2个缓冲区满时，在这b/2个缓冲区上调用COLLAPSE 操作，对应于b/2叉树,有限存储下一趟扫描计算近似中值及其他分位数,本文介绍的新算法，首先在b个缓冲区上执行COLLAPSE操作，然后在b-1个缓冲区上，然后在b-2，对应于一棵从左向右、由下向上度数渐减的多叉树。 三种算法的近似度保证分析 (比较复杂，见译文全文),有限存储下一趟扫描计算近似中值及其他分位数,新算法比前面的两个算法更节省内存,有限存储下一趟扫描计算近似中值及其他分位数,为了在N很大时进一步减少所需内存，采用随机采样技术(先采样得到一个较小的采样数据集，然后在采样数据集上运行前面的算法)。 结合随机采用计术后所需存储和N无关 但正确性的保证是概率型的，即只能保证用户给定的 百分比下算法的结果是正确的。,有限存储下一趟扫描计算近似中值及其他分位数,什么情况下需要使用采样技术？文中给出了当取不