首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >大数据计数原理1+0=1这你都不会算(十)No.77

大数据计数原理1+0=1这你都不会算(十)No.77

作者头像
大蕉
发布2018-02-05 19:13:40
4670
发布2018-02-05 19:13:40
举报

大数据计数原理1+0=1这你都不会算(一)No.47 <- HashSet

大数据计数原理1+0=1这你都不会算(二)No.50 <- BitMap

大数据计数原理1+0=1这你都不会算(三)No.51 <- BloomFilter

大数据计数原理1+0=1这你都不会算(四)No.52 <- B-Tree

大数据计数原理1+0=1这你都不会算(五)No.55 <- B+Tree

大数据计数原理1+0=1这你都不会算(六)No.57 <- LinearCounting(一)

大数据计数原理1+0=1这你都不会算(七)No.59 <- LinearCounting(二)

大数据计数原理1+0=1这你都不会算(八)No.60 <- RoaringBitMaps

大数据计数原理1+0=1这你都不会算(九)No.64

完结篇。 这个系列写到这里算是结束了,真是不容易说实话,查了好多好多的资料,真的很难相信懒得要命的我能写完这个系列 T_T。有兴趣的小伙伴可以在菜单看看整个系列。

好啦,开始今天的主题,今天主要呢,聊最后两个基数估计算法,一个是 Adaptive Counting ,一个是 HyperLogLog Counting 。话不多说,直接简单粗暴从 Adaptive Counting 开始吧。

Adaptive Counting 其实就是一个组合算法。

原始论文是 《 Fast and accurate traffic matrix measurement using adaptive cardinality counting 》 。思路很简单粗暴,就是将 LC 和 LLC 组合起来使用,我们假设 LC 与 LLC 在同样的条件下,在总统计值 m 等于 M 的时候误差达到一致,那么当 m 小于 M 的时候使用 LC ,当 m 远大于 M 的时候使用 LLC。 为什么呢?我们都知道 LC 其实只是 BitMap 的进化版,如果基数太大的话,那么会占用非常多非常多的内存,如果桶设置得太小的话所有的桶基本都满了,那么这样子误差会很大。而 LLC 则非常稀疏,如果 m 太小的话,那么会出现非常多的空桶,这样子误差也非常大。所以总结起来就是,组合起来用,总统计量小的话用 LC , 统计量太大的话用 LLC 。

HyperLogLog Counting 其实就是 LC 基数估计法从算术平均数换成调和平均数。

先补充一下小学算术,什么叫算术平均数什么叫调和平均数哈。首先是算术平均数,其实就是加起来求和。

第二是调和平均数,其实就是倒数求和除n的倒数。

呐,这样就可以解释清楚了。LC 里边是对 m 个桶里边的值进行求算术平均数然后直接进行基数估计,而 LLC 则是使用调和平均数。那么,这样做有什么道理呢?

对比一下,LLC 是第一个,HyperLogLog Counting 是第二个。

看得出差别了吗?一个是直接求和平均,一个是倒数平均。其中 LLC 使用算术平均数,那么如果数值比较稀疏的时候,也即是有一些偏离值的时候,整个数据的求和会变得很偏远。用人话来说就是,我跟姚明平均身高两米。。。非常容易受到异常值的影响。而 HyperLogLog Counting 使用调和平均数则可以有效降低偏离值的影响。虽然来说也有一点影响但是影响程度没有算术平均数那么大。

最后放出各大算法的空间占用及误差率,看时机使用吧,别什么东西都直接丢一个 HyperLogLog ,有些场景下可能直接丢一个 HashSet 更靠谱喔。

好了这个系列到此结束,总得来说基数估计算法的套路都差不了太多,基本都输基于 BitMap 的思想,然后进行分桶,接着对桶进行统计这样的思路来进行超大数据量的基数估计。

本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2017-12-30,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 一名叫大蕉的程序员 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
相关产品与服务
大数据
全栈大数据产品,面向海量数据场景,帮助您 “智理无数,心中有数”!
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档