基数估计算法概览

标签: IT技术 算法 | 发表时间:2012-11-23 16:25 | 作者:
出处:http://blog.jobbole.com

英文原文: Damn Cool Algorithms: Cardinality Estimation,编译: 张洋@敲代码的张洋

译注:给定一个数据集,求解数据集的基数(Cardinality,也译作“势”,表示一个数据集中不同数据项的数量)是非常普遍的一个需求。许多业务需求最终可以归结为基数求解,如网站访问分析中的UV(访客数,指一段时间内访问网站的不同用户的数量)。由于数据集基数是不可聚集指标(两个数据集总的基数无法通过分别的基数简单计算),因此如果要得到N个数据集任意组合的基数,需要2N次数据集去重计算,是一个复杂度非常高的计算过程。当数据量较小时,可以采取bitmap“按位或”方法获得较高的计算速度;而当数据量很大时,一般会采取概率算法对基数进行估计。这篇文章是对基数估计算法的一个非常好的概览。

以下为译文

——————–

假如你有一个巨大的含有重复数据项数据集,这个数据集过于庞大以至于无法全部放到内存中处理。现在你想知道这个数据集里有多少不同的元素,但是数据集没有排好序,而且对如此大的一个数据集进行排序和计数几乎是不可行的。你要如何估计数据集中有多少不同的数据项?很多应用场景都涉及这个问题,例如设计数据库的查询策略:一个良好的数据库查询策略不但和总的数据量有关,同时也依赖于数据中不同数据项的数量。

我建议在继续阅读本文前你可以稍微是思考一下这个问题,因为接下来我们要谈的算法相当有创意,而且实在是不怎么直观。

一个简单直观的基数估计方法

让我们从一个简单直观的例子开始吧。假设你通过如下步骤生成了一个数据集:

1、随机生成n个服从均匀分布的数字

2、随便重复其中一些数字,重复的数字和重复次数都不确定

3、打乱这些数字的顺序,得到一个数据集

我们要如何估计这个数据集中有多少不同的数字呢?因为知道这些数字是服从均匀分布的随机数字,一个比较简单的可行方案是:找出数据集中最小的数字。假如m是数值上限,x是找到的最小的数,则m/x是基数的一个估计。例如,我们扫描一个包含0到1之间数字组成的数据集,其中最小的数是0.01,则一个比较合理的推断是数据集中大约有100个不同的元素,否则我们应该预期能找到一个更小的数。注意这个估计值和重复次数无关:就如最小值重复多少次都不改变最小值的数值。

这个估计方法的优点是十分直观,但是准确度一般。例如,一个只有很少不同数值的数据集却拥有很小的最小值;类似的一个有很多不同值的数据集可能最小值并不小。最后一点,其实只有很少的数据集符合随机均匀分布这一前提。尽管如此,这个原型算法仍然是了解基数估计思想的一个途径;后面我们会了解一些更加精巧的算法。

基数估计算法概览

基数估计的概率算法

最早研究高精度基数估计的论文是Flajolet和Martin的 Probabilistic Counting Algorithms for Data Base Applications,后来Flajolet又发表了 LogLog counting of large cardinalitiesHyperLogLog: The analysis of a near-optimal cardinality estimation algorithm两篇论文对算法进行了进一步改进。通过逐篇阅读这些论文来了解算法的发展和细节固然有趣,不过在这篇文章中我会忽略一些算法的理论细节,把精力主要放在如何通过论文中的算法解决问题。有兴趣的读者可以读一下这三篇论文;本文不会介绍其中的数学细节。

Flajolet和Martin最早发现通过一个良好的哈希函数,可以将任意数据集映射成服从均匀分布的(伪)随机值。根据这一事实,可以将任意数据集变换为均匀分布的随机数集合,然后就可以使用上面的方法进行估计了,不过只是这样是远远不够的。

接下来,他们陆续发现一些其它的基数估计方法,而其中一些方法的效果优于之前提到的方法。Flajolet和Martin计算了哈希值的二进制表示的0前缀,结果发现在随机数集合中,通过计算每一个元素的二进制表示的0前缀,设k为最长的0前缀的长度,则平均来说集合中大约有2k个不同的元素;我们可以用这个方法估计基数。但是,这仍然不是很理想的估计方法,因为和基于最小值的估计一样,这个方法的方差很大。不过另一方面,这个估计方法比较节省资源:对于32位的哈希值来说,只需要5比特去存储0前缀的长度。

值得一提的是,Flajolet-Martin在最初的论文里通过一种基于bitmap的过程去提高估计算法的准确度。关于这点我就不再详述了,因为这种方法已经被后续论文中更好的方法所取代;对这个细节有兴趣的读者可以去阅读原始论文。

到目前为止,我们这种基于位模式的估计算法给出的结果仍然不够理想。如何进行改进呢?一个直观的改进方法就是使用多个相互独立的哈希函数:通过计算每个哈希函数所产生的最长0前缀,然后取其平均值可以提高算法的精度。

实践表明从统计意义来说这种方法确实可以提高估计的准确度,但是计算哈希值的消耗比较大。另一个更高效的方法就是随机平均(stochastic averaging)。这种方法不是使用多个哈希函数,而是使用一个哈希函数,但是将哈希值的区间按位切分成多个桶(bucket)。例如我们希望取1024个数进行平均,那么我们可以取哈希值的前10比特作为桶编号,然后计算剩下部分的0前缀长度。这种方法的准确度和多哈希函数方法相当,但是比计算多个哈希效率高很多。

根据上述分析,我们可以给出一个简单的算法实现。这个实现等价于Durand-Flajolet的论文中提出的LogLog算法;不过为了方便,这个实现中统计的是0尾缀而不是0前缀;其效果是等价的。

def trailing_zeroes(num):
  """Counts the number of trailing 0 bits in num."""
  if num == 0:
    return 32 # Assumes 32 bit integer inputs!
  p = 0
  while (num >> p) & 1 == 0:
    p += 1
  return p
 
def estimate_cardinality(values, k):
  """Estimates the number of unique elements in the input set values.
 
  Arguments:
    values: An iterator of hashable elements to estimate the cardinality of.
    k: The number of bits of hash to use as a bucket number; there will be 2**k buckets.
  """
  num_buckets = 2 ** k
  max_zeroes = [0] * num_buckets
  for value in values:
    h = hash(value)
    bucket = h & (num_buckets - 1) # Mask out the k least significant bits as bucket ID
    bucket_hash = h >> k
    max_zeroes[bucket] = max(max_zeroes[bucket], trailing_zeroes(bucket_hash))
  return 2 ** (float(sum(max_zeroes)) / num_buckets) * num_buckets * 0.79402

这段代码实现了我们上面讨论的估计算法:我们计算每个桶的0前缀(或尾缀)的最长长度;然后计算这些长度的平均数;假设平均数是x,桶数量是m,则最终的估计值是2x×m。其中一个没提过的地方是魔法数字0.79402。统计分析显示这种预测方法存在一个可预测的偏差;这个魔法数字是对这个偏差的修正。实际经验表明计算值随着桶数量的不同而变化,不过当桶数量不太小时(大于64),计算值会收敛于估计值。原论文中描述了这个结论的推导过程。

这个方法给出的估计值比较精确 —— 在分桶数为m的情况下,平均误差为1.3/m−−√。因此对于分桶数为1024的情况(所需内存1024*5 = 5120位,或640字节),大约会有4%的平均误差;每桶5比特的存储已经足以估计227的数据集,而我们只用的不到1k的内存!

让我们看一下试验结果:

>>> [100000/estimate_cardinality([random.random() for i in range(100000)], 10) for j in range(10)]
[0.9825616152548807, 0.9905752876839672, 0.979241749110407, 1.050662616357679, 0.937090578752079, 0.9878968276629505, 0.9812323203117748, 1.0456960262467019, 0.9415413413873975, 0.9608567203911741]

不错!虽然有些估计误差大于4%的平均误差,但总体来说效果良好。如果你准备自己做一下这个试验,有一点需要注意:Python内置的 hash() 方法将整数哈希为它自己。因此诸如 estimate_cardinality(range(10000), 10) 这种方式得到的结果不会很理想,因为内置 hash() 对于这种情况并不能生成很好的散列。但是像上面例子中使用随机数会好很多。

提升准确度:SuperLogLog和HyperLogLog

虽然我们已经有了一个不错的估计算法,但是我们还能进一步提升算法的准确度。Durand和Flajolet发现离群点会大大降低估计准确度;如果在计算平均值前丢弃一些特别大的离群值,则可以提高精确度。特别的,通过丢弃最大的30%的桶的值,只使用较小的70%的桶的值来进行平均值计算,则平均误差可以从1.3/m−−√降低到1.05/m−−√!这意味着在我们上面的例子中,使用640个字节可情况下可以将平均误差从4%降低到3.2%,而所需内存并没有增加。

最后,Flajolet等人在HyperLogLog论文中给出一种不同的平均值,使用调和平均数取代几何平均数(译注:原文有误,此处应该是算数平均数)。这一改进可以将平均误差降到1.04/m−−√,而且并没不需要额外资源。但是这个算法比前面的算法复杂很多,因为对于不同基数的数据集要做不同的修正。有兴趣的读者可以阅读原论文。

并行化

这些基数估计算法的一个好处就是非常容易并行化。对于相同分桶数和相同哈希函数的情况,多台机器节点可以独立并行的执行这个算法;最后只要将各个节点计算的同一个桶的最大值做一个简单的合并就可以得到这个桶最终的值。而且这种并行计算的结果和单机计算结果是完全一致的,所需的额外消耗仅仅是小于1k的字节在不同节点间的传输。

结论

基数估计算法使用很少的资源给出数据集基数的一个良好估计,一般只要使用少于1k的空间存储状态。这个方法和数据本身的特征无关,而且可以高效的进行分布式并行计算。估计结果可以用于很多方面,例如流量监控(多少不同IP访问过一个服务器)以及数据库查询优化(例如我们是否需要排序和合并,或者是否需要构建哈希表)。

相关文章

相关 [基数 计算] 推荐:

基数估计算法概览

- - 博客 - 伯乐在线
英文原文: Damn Cool Algorithms: Cardinality Estimation,编译: 张洋 ( @敲代码的张洋). 译注:给定一个数据集,求解数据集的基数(Cardinality,也译作“势”,表示一个数据集中不同数据项的数量)是非常普遍的一个需求. 许多业务需求最终可以归结为基数求解,如网站访问分析中的UV(访客数,指一段时间内访问网站的不同用户的数量).

oracle license计算

- Fenng - eagle's home
Oracle license的计算是基于CPU core的. 用core的数目乘以一个系数core factor就可以得到所需的oracle license的数目. 对于不同的CPU,core factor是不一样的,可以从oracle提供的这张列表中查到 Oracle Processor Core Factor Table.

理解云计算

- 车东 - oneoo's 私家花园
  现在互联网最热门的关键字“云计算”,大大小小的公司纷纷加入到这块领域. 简单来说,目前的“云计算”主要分为:SaaS、PaaS和IaaS三大类.   其中SaaS云计算,为软件即服务的概念. 把传统客户端软件部署在互联网上,用户只需要一个浏览器就可以使用到软件的模式. 其实早在2000年就已经有B/S结构的软件服务,与现在所说的SaaS云计算相近,但此前的B/S结构软件服务,数据库等服务端是需要用户自行部署的,而非由软件提供商进行统一部署.

钢琴计算器

- 丑秋 - 专利之家-设计发明与创意商机
这款太阳能计算器别出心裁地设计了黑白相间的按键,看起来像钢琴的琴键一样,十分有趣. 或许这样的计算器可以给枯燥的计算工作增添一点乐趣,让它不再乏味.

10问云计算

- - 《商业价值》杂志
与数百位关注和实践云计算的CIO们共同解读云计算热点问题. 被视作IT界第三次革命的云计算,已经从炙手可热的概念逐渐走向了实际应用. 2011年8-11月, ITValue社区联合英特尔公司,与数百位关注和实践云计算的CIO们一起展开深入探讨,话题涉及云计算的商业价值、安全性、开放性、高效性、简单性等方面.

云计算的困局

- Star Ocean - It Talks--上海魏武挥的博客
有个媒体朋友打电话咨询我一个事. 说在江浙一带,有一位搞国际货运代理的民营企业家,想利用云计算来整合各种资源,比如运输车队、仓库、集装箱乃至货船. 这些资源的调配信息对任何一家从事外贸的企业都很重要,如果将这些信息放在所谓的“云”上,并加以运算,这些企业再以各种设备联入这个“云”,这位企业家觉得是一个很有前途的买卖.

开源云计算ERP ErpCore

- Le - 开源中国社区最新软件
  ErpCore是一套强大的云计算ERP开发框架,集数据库设计、软件建模、模型自动生成、界面可视化设计、业务流可自定义、全自动生成用户所需系统于一体. 在此框架上扩展出所有行业的业务系统,它让软件工程师从“建模——写代码——测试”所有繁琐重复的工作变为全自动化生成,大大简化了企业软件的开发时间和成本;同时,使用该框架扩展的所有业务子系统能够无缝连接进行数据共享,这也是云计算ERP的实现基础,杜绝了传统ERP的子.

异构计算的挑战

- Guancheng(冠诚) - 技术改变世界 创新驱动中国 - 《程序员》官网
进入新世纪之后,软件研发面临并行编程的技术变革、硬件架构面临异构计算的挑战,这些改变是否意味着新的机遇,取决于能否建立良好的生态链. 2004年12月,C++标准化委员会主席、著名程序员Herb Sutter在自己的个人网站发表了一篇影响深远的文章《免费午餐已经结束》(中文版发表于本刊2006年11月期).

并行计算的解药

- chengdujin - 牛博山寨 编辑推荐
前几天看到 reddit.com 的 programming 类别第一名是《 Parallelism is Not Concurrency 》. 读完之后发现和我去年的《多核与锁》有很多观点上的共通之处. 《 Parallelism is Not Concurrency 》的开篇行文更流畅幽默,对并发( concurrency )和并行( parallelism )有更精辟的总结.

优秀的Android计算器

- 李龑 - Solidot
Paul Power 写道 "计算器是操作系统自带的基本工具之一. 这些简单的工具提供了满足基本需求所需的足够功能. 但Android设备自带的计算器功能相当有限,仅提供了基本的加减乘除和括号等功能. 这篇介绍了十多款功能丰富的优秀计算器,其中部分还能绘制2D和3D图形,处理复杂的数学函数. 利用这些工具,Android智能手机能变成可随时使用的图形计算器.