Change Dir

先知cd——热爱生活是一切艺术的开始

统计

留言簿(18)

积分与排名

“牛”们的博客

各个公司技术

我的链接

淘宝技术

阅读排行榜

评论排行榜

基数估计

问题的背景是在大数据冲击下,很多数据指标(尤其是涉及到去重的)的计算无法在合理的空间和时间内完成,比如uv的计算,数学原型问题等价于持续的向一个集合中写数,重复的不记,要求最终给出集合中不重复的元素的个数(集合的势)。而比较暴力的做法是随着数字增多不断的扩展集合的大小,让它放下所有的数,最终数出这个个数就OK。显然这样的空间复杂度在单机下是做不到的,所以多数做法是利用分布式原理将uv数据隔离到不同的计算节点,每个计算节点自行维护一个类似这样的集合(wdm实时里的布隆过滤器),然后分而治之,最后merge为一份结果数据。

      基数估计的初衷就是为了解决在大数据的前提下,如何以低成本的空间复杂度去计算超大集合的势的问题,换句话说,通过基数估计,单机做到计算亿级别uv,误差在4%以内。解决思路主要是概率估计,具体原理和做法参看 blog和论文原文。

     出于实验的目的,我简单实现了暴力做法bruteforce-bf,布隆过滤器-bbf,loglog-llc和hyperloglog-hllc四个算法,比较一下基数估计这个计算去重指标的逻辑是否可行(llc非常离谱,可能是我分桶数没有调整好,就不贴出结果了)。

预处理方法:1-N生成随机uid,模拟N次(均匀分布),jvm启动-Xmx1024m。

实验结果:

image   image

附加说明一下,期望值如何计算:其实这个实验的数学原型就是一个长度为k的均匀分布的(1-N)的随机数列,求不重复的元素个数的期望。我实验里k=n,这是一种极端情况(实验设计纯为方便计算,如果k较大会导致计算超慢,uv5000w时根本无法计算出来,增大k理论上会提高精度,我实验过的一组数据是100w uv 500wpv时 hllc的值是991234,误差<1%),理论上k相当于pv,在递推公式中k趋于无穷时期望等于n。

这个递推的计算可以通过组合分析推导,推导方法不详说了(当然我有可能推导错了~~数学功底 实在 不行了),通项公式见matlab代码。

syms e n;
e = n-(1/n)*((1-2*n+n*n)*((n-1)/n)^(n-2)+(1-n)*n+n*(n-1));

vpa(subs(e,'n',1000000),10)

另外,我个人认为分布式布隆过滤器的方案是非常好的,因为空间和时间都比较均衡,且精确度高,基数估计的方法本质上空间复杂度O(1),时间复杂度代码高效一点也可以非常快,但是缺点是精确度稍微欠缺,且不易分布式计算(因为它天生适合单进程,llc分桶均衡也是单进程做比较好,分布式完全是牛刀杀鸡)。

ref blog: http://blog.codinglabs.org/articles/cardinality-estimate-exper.html#ref4

算法实现的java代码可见github: https://github.com/changedi/card-estimate



posted on 2013-11-12 10:10 changedi 阅读(2543) 评论(0)  编辑  收藏 所属分类: 数学数据


只有注册用户登录后才能发表评论。


网站导航: