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

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,有限存储下一趟扫描计算近似中值及其他分位数,Approximate Medians and other,Quantiles,in One Pass and with Limited Memory,要,解决的问题：给定有,N,个元素的乱序数据集合，怎样计算将这,N,个数据排序后位于正中间的那个元素(或者位于0.35,N,位置的元素)？,分位数(,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,无关,但正确性的保证是概率型的，即只能保证用户给定的,百分比下算法的结果是正确的。,有限存储下一趟扫描计算近似中值及其他分位数,什么情况下需要使用采样技术？文中给出了当取不同的近似度时需要使用采样技术的,N,的阈值，当,N,大于这个阈值时，使用采样技术能有效减少算法的存储,试验结果显示，文中的算法在使用少量存储下，能得到近似度非常好的结果,