简单认识KMV Sketch估算算法

栏目: 编程工具 · 发布时间: 6年前

内容简介:如果你去参加音乐会,你排在队尾,如何估计你的前面还有多少个人?如下图,整个队伍的长度是已知的为

介绍

KMV SketchTheta Sketch 算法的一种,简单来说, KMV Sketch 是用来估算大数据中不重复元素的个数,例如某个网站的唯一身份访客数。本文简单翻译自 datasketches文档 ,用以说明该算法是如何进行估算的。

案例1

如果你去参加音乐会,你排在队尾,如何估计你的前面还有多少个人?如下图,整个队伍的长度是已知的为 1000Ft ,你与前一个人的距离为 2Ft ,那么可以简单的估算,整个队伍共有 1000Ft/2Ft=500 人,此时你用于计算的样本包含的人数为 1 人。

简单认识KMV Sketch估算算法

再次观察这个队伍,你发现人与人之间的距离并不是均匀的,你看到队尾的 11 个人一共占据了 30Ft 的长度,那么再次估算人数为 1000Ft/30Ft*11=11/(30Ft/1000Ft)=366 人,由于此次你用了 11 个人作为样本,估算值应该比之前更精确。

简单认识KMV Sketch估算算法

案例2

现在我们有一份大数据样本,包含的是访客的唯一 id ,为了简单说明原理,假设只有 10 个不同的 id 我们还需要一个特殊的 hash 函数,它能将 id 映射成 0~1 之间的值, 并且映射后的值是有序的,如下图所示:

简单认识KMV Sketch估算算法

如果选取最小的那个值作为估算样本,那么整体数量的估算值为 1/0.008=125 ,如果选第 4 个数,即 0.386 作为样本,那么估算值为 1/(0.386-0.195)=5 。可以看到,在只有一个样本的情况下,估算值与真实值 10 差距较大。

参考估算排队人数的做法,我们同样选择多个样本来估算,例如选择最小的 0.008/0.145/0.1953 个样本,此时估计值的计算方式为 (3-1)/0.195=10.26 ,可以看到,距离真实值已经很接近了。

简单认识KMV Sketch估算算法

KMV 估算法的计算原理就是这样,虽然很简单,但数学上可以严格证明该估计量是整体的无偏估计。

简单认识KMV Sketch估算算法

相关链接: 什么是无偏估计?


以上所述就是小编给大家介绍的《简单认识KMV Sketch估算算法》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

硅谷之火

硅谷之火

保罗·弗赖伯格、迈克尔·斯韦因 / 张华伟 编译 / 中国华侨出版社 / 2014-11-1 / CNY 39.80

《硅谷之火:人与计算机的未来》以生动的故事,介绍了计算机爱好者以怎样的创新精神和不懈的努力,将计算机技术的力量包装在一个小巧玲珑的机壳里,实现了个人拥有计算机的梦想。同时以独特的视角讲述了苹果、微软、太阳微系统、网景、莲花以及甲骨文等公司的创业者们在实现个人计算机梦想的过程中创业的艰辛、守业的艰难、失败的痛苦,在激烈竞争的环境中奋斗的精神以及在技术上不断前进的历程。一起来看看 《硅谷之火》 这本书的介绍吧!

CSS 压缩/解压工具
CSS 压缩/解压工具

在线压缩/解压 CSS 代码

JSON 在线解析
JSON 在线解析

在线 JSON 格式化工具

正则表达式在线测试
正则表达式在线测试

正则表达式在线测试