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

gmd20的个人空间

// 编程和生活

 
 
 

日志

 
 

基数估计算法的相关资料  

2013-01-05 14:38:43|  分类: 程序设计 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

基数就是,给一个数组,计算不同的数字的个数就是基数。 下面这些算法当数组非常大的时候,用概率的办法用很小的空间和误差估计大概的基数是多少。 想下面这个文档说的,用1.5kb的空间估算十亿个数字的基数。  淘宝工程师文档提到的一个应用就是统计访问一个链接的独立ip的数目。为每个连接分配一个基数估计需要的空间,然后把不同的ip和cookie之类的通过哈希函数,映射为一个数值。最后就是转换成基数估计问题。得到的基数就是独立ip数目。 Adaptive Counting论文说是应用于网络包内容的来源的统计,检测ddos攻击。  



淘宝开源的库

https://github.com/chaoslawful/ccard-lib


给出的引用相关论文

LogLog Counting and Adaptive Counting

  • Min Cai, Jianping Pan, Yu K. Kwok, and Kai Hwang. Fast and accurate traffic matrix measurement using adaptive cardinality counting. In MineNet ’05: Proceedings of the 2005 ACM SIGCOMM workshop on Mining network data, pages 205–206, New York, NY, USA, 2005. ACM.

  • Marianne Durand and Philippe Flajolet. LogLog counting of large cardinalities. In ESA03, volume 2832 of LNCS, pages 605–617, 2003.

http://gridsec.usc.edu/files/TR/TR-2005-12.pdf  这里可以找到

Linear Counting

  • K.-Y. Whang, B. T. Vander-Zanden, and H. M. Taylor. A Linear-Time Probabilistic Counting Algorithm for Database Applications. ACM Transactions on Database Systems, 15(2):208-229, 1990.

HyperLogLog Counting
  • P. Flajolet, E. Fusy, O. Gandouet, and F. Meunier. Hyperloglog: The analysis of a near-optimal cardinality estimation algorithm. Disc. Math. and Theor. Comp. Sci., AH:127-146, 2007.

http://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf  这里可以找到



淘宝工程师写的介绍系列文章的第一篇

解读Cardinality Estimation算法(第一部分:基本概念)

http://www.codinglabs.org/html/algorithms-for-cardinality-estimation-part-i.html



微博上好像是从csdn翻译这篇文章开始讨论这个话题的。

Big Data Counting: How To Count A Billion Distinct Objects Using Only 1.5KB Of Memory

http://highscalability.com/blog/2012/4/5/big-data-counting-how-to-count-a-billion-distinct-objects-us.html


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

历史上的今天

评论

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

页脚

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