注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

gmd20的个人空间

// 编程和生活

 
 
 

日志

 
 

redis也支持HyperLogLog数据结构了  

2014-04-02 14:38:52|  分类: 程序设计 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

http://antirez.com/news/75


对HyperLogLog数据结构做了一些说明,和一些参考文档。

通过扔硬币的正反面来说明这个原理,比如,如果你告诉我你扔硬币看到正面的次数是10次,那么我就可以大概估计你扔的次数是20次。 如果这个数值比较到大,那么是结果是比较准确的。

HyperLogLog 就是把这个element 做哈希,然后统计所有hash得到的数值 高位开始0标志位占整个的比例,就可以大概估计总的数目。这就是整个空间不重复数据的数目。


提到了Google的实现的论文

HyperLogLog in Practice: Algorithmic Engineering of a State of The Art Cardinality Estimation Algorithm

[1] http://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf
[2] http://static.googleusercontent.com/media/research.google.com/en//pubs/archive/40671.pdf


我之前也有发过一篇文章了。

基数估计算法的相关资料

http://gmd20.blog.163.com/blog/static/1684392320130523843285/

?

  评论这张
 
阅读(1201)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017