Loading [MathJax]/jax/input/TeX/config.js
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >大数据计数原理1+0=1这你都不会算(八)No.60

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

作者头像
大蕉
发布于 2018-02-05 10:55:37
发布于 2018-02-05 10:55:37
8820
举报

今天跟小伙伴们聊聊另外一个统计算法, Roaring BitMaps。

这个该怎么翻译呢??咆哮的位图?s?我翻译不出来,但是小蕉头一歪,就给它起了一个狂拽酷霸叼扎天的翻译 -> 咆哮吧,位图君们。

照例甩一波链接。

大数据计数原理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(二)


来了喔。

根据官方统计,已经有这么多大项目在用Roaring BitMaps了,老牛逼了。

  • Apache Lucene and derivative systems such as Solr and Elasticsearch,
  • Metamarkets’ Druid,
  • Apache Spark,
  • Apache Hive,
  • Apache Tez,
  • Netflix Atlas,
  • LinkedIn Pinot,
  • OpenSearchServer,
  • Cloud Torrent,
  • Whoosh,
  • Pilosa,
  • Microsoft Visual Studio Team Services (VSTS),
  • Jive Miru,
  • eBay’s Apache Kylin.

那么勤劳又聪明的你一定会问了,这是什么东西?用来干啥的?怎么用的?从用途来看,Roaring BitMaps 就是一个用来进行基数统计的算法。

用途有三只:

第一只当然就是基数统计啦,count之类的,可节省空间了。

第二只呢,数据库在执行Join的时候,要知道Join之前是多少量级,Join完又是什么量级,再执行相应的优化策略。

第三只呢,是作为索引存在,可以作为数据库判断唯一索引的唯一性。

等等。

关于这个算法呢,也不是什么非常难的东西,原始论文其实讲得蛮详细的了,看看原始论文一般就能看懂了。但小蕉在这里,其实用三句话就可以把这个算法说清楚了。

1、把n长的区间划分为2^16个桶(n为Roaring BitMaps 的总长度),每个桶放一个Container,作为一级索引存在。

2、每个int数值k为32位的bit,我们取前16位找到对应的桶(k % 2^16),Container里面只保存后16位 (k mod 2^16) 。若Container为BitMap,直接把第 (k mod 2^16) 位设置为1即可,若Container为Array,则用二分查找插入法,有序插入。

3、若一个Container里面的Integer数量小于4096,就用Short类型的有序数组来存储值。若大于4096,就用BitMap来存储值。数据用来放稀疏的数据,BitMap用来放紧密的数据(至于为啥,请重新看BitMap的定义及使用范围)。

实际使用的时候怎么找到值呢?跟原来插入值一样,因为Containers是有序的嘛,也有自己的数据范围,所以首先用二分查找找到数据对应的Container。然后分两种情况,如果是Container是数组,就再用一次二分查找。如果Container是BitMap,直接找到对应的位是不是1就行了。

好啦,算法方面就这样说完了,但是又有小朋友要问了,那这样存储完有什么用呢?只需要定义三种操作,AND,OR,NOT,就可以快速进行两个集合的操作了。

因为Container有两种,BitMap和Array ,所以进行合并操作的时候会有三种情况。

1、Array vs Array

2、Array vs BitMap

3、BitMap vs BitMap

分别是怎么处理呢,下面所说的操作指的你所希望的功能是AND、OR、还是NOT?选一种操作进行计算就行了。

Array vs Array ,直接用算法merge成一个数组,再进行相应的操作即可。

Array vs BitMap,遍历一下Array,把它的值一个一个映射到BitMap上并操作,最终统计一下BitMap即可。

BitMap vs BitMap,直接按位操作即可。

实际实现的时候,不仅仅会有Short类型的Array,拓展开可以是任何基础数据类型的Array,功能越来越丰富了。

论文连接:链接: https://pan.baidu.com/s/1pKGrNcf 密码: s449 GitHub地址:https://github.com/RoaringBitmap/RoaringBitmap

沉迷学习,日渐消瘦。大家如果有什么健身、Java入门、大数据机器学习入门方面的问题也可以问我,我看到会回的,有什么想看的想听的也可以告诉我,我会把放入我的需求池的,啊哈哈哈哈哈。

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

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

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

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

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
大数据计数原理1+0=1这你都不会算(六)No.57
照例甩一波链接。 大数据计数原理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 今天开始进入一个全新的领域,嗯
大蕉
2018/02/05
6290
大数据计数原理1+0=1这你都不会算(六)No.57
大数据计数原理1+0=1这你都不会算(九)No.64
大数据计数原理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
大蕉
2018/02/05
5850
不深入而浅出 Roaring Bitmaps 的基本原理
0x00 前言 位图索引被广泛用于数据库和搜索引擎中,通过利用位级并行,它们可以显著加快查询速度。但是,位图索引会占用大量的内存,因此我们会更喜欢压缩位图索引。 Roaring Bitmaps 就是一种十分优秀的压缩位图索引,后文统称 RBM。 压缩位图索引有很多种,比如基于 RLE(Run-Length Encoding,运行长度编码)的WAH (Word Aligned Hybrid Compression Scheme) 和 Concise (Compressed ‘n’ Composable Int
木东居士
2018/05/25
21K6
Roaring Bitmap更好的位图压缩算法
Bitsets(也称为Bitmaps)通常用作快速数据结构。不幸的是,他们可能会占用太多内存。为了降低内存的使用,我们经常会使用压缩的位图。
smartsi
2019/08/07
6.6K0
Roaring Bitmap更好的位图压缩算法
大数据计数原理1+0=1这你都不会算(七)No.59
今天的干货,不是一般的干,噎死人那种干。没下面这些准备的话直接退出吧,回去度娘啊谷哥啊弄懂是什么东西再回来。 知识储备必须有这些: BitMap知识。概率论二项分布。泰勒展开。函数求极限。求期望值。求方差、标准差。log对数变换。极大似然估计。 照例甩一波链接。 大数据计数原理1+0=1这你都不会算(一)No.47 <- HashSet 大数据计数原理1+0=1这你都不会算(二)No.50 <- BitMap 大数据计数原理1+0=1这你都不会算(三)No.51
大蕉
2018/02/05
5840
大数据计数原理1+0=1这你都不会算(七)No.59
大数据计数原理1+0=1这你都不会算(十)No.77
大数据计数原理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
大蕉
2018/02/05
5310
大数据计数原理1+0=1这你都不会算(十)No.77
大数据计数原理1+0=1这你都不会算(五)No.55
Hello哈,又好久没聊大数据相关的东西了,是不是又忘记了吖?这次聊聊B-树的升级版,B+树。前面的内容小伙伴可以回顾一下。 大数据计数原理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 所谓B+树
大蕉
2018/02/05
5800
大数据计数原理1+0=1这你都不会算(五)No.55
大数据计数原理1+0=1这你都不会算(三)No.51
这是本坑的第三篇,之前已经说了关于 HashSet 和 BitMap 了,这次说说 Bloom Filter 布隆过滤器,要是还不知道前面讲了啥的,可以点一下下面的连接看看。 大数据计数原理1+0=1这你都不会算(一)No.47 大数据计数原理1+0=1这你都不会算(二)No.50 我们都知道BitMap已经非常节省空间了,一个值只需要一个 bit 就可以进行统计了,但是,对于上百亿的数据来说,碰撞率即使非常低,但也不是一个可以忽视的问题了。 当时提出这个问题,一个是因为垃圾电子邮箱,每天少说都有几十
大蕉
2018/02/05
6300
大数据计数原理1+0=1这你都不会算(三)No.51
大数据计数原理1+0=1这你都不会算(一)No.47
hello哈,大家是不是好久没见到我啦?我也是一直在摸索小伙伴们喜欢看到什么东西,不喜欢看什么东西,还请大家多多支持。为了表示感谢。小蕉在这给你们一鞠躬,二鞠躬,三。事不过三~ 1+0=1你都不会谈什么大数据? 这篇呢,又是开坑之作,这是一个系列,主要会将大数据下的计数原理。说到计数,不知道大家会第一印象想到什么,我估计会是。。数手指。。没错,小蕉从小学开始就开始数手指,所有20以内的加减法很早就掌握了。研表究明,这估计也是我们现在使用十进制的原因,如果我们每个人每只手都有6只手指,那我们可能就用十二进制了
大蕉
2018/02/05
6830
美团外卖搜索基于Elasticsearch的优化实践
美团外卖搜索工程团队在Elasticsearch的优化实践中,基于Location-Based Service(LBS)业务场景对Elasticsearch的查询性能进行优化。该优化基于Run-Length Encoding(RLE)设计了一款高效的倒排索引结构,使检索耗时(TP99)降低了84%。本文从问题分析、技术选型、优化方案等方面进行阐述,并给出最终灰度验证的结论。
美团技术团队
2022/12/16
1.4K0
美团外卖搜索基于Elasticsearch的优化实践
大数据计数原理1+0=1这你都不会算(四)No.52
这是本坑的第四篇,之前已经说了关于 HashSet 、BitMap 、Bloom Filter 布隆过滤器了,本篇主要讲B-树。要是还不知道前面讲了啥的,可以点一下下面的连接看看。 大数据计数原理1+0=1这你都不会算(一)No.47 大数据计数原理1+0=1这你都不会算(二)No.50 大数据计数原理1+0=1这你都不会算(三)No.51 B+树是现在很多索引系统的数据结构,而B-树是B+树的基础,本次先讲B-树。 而在讲B-树之前,又不得不讲二叉搜索树(BST,Binary Search Tree)
大蕉
2018/02/05
6400
大数据计数原理1+0=1这你都不会算(四)No.52
论文阅读|高效压缩位图RoaringBitmaps设计原理
刚接触编程那会记得用 Bitmap 的 0 和 1 位来标识数据是否存在,主要用于排序;
用户5166556
2023/03/18
7950
论文阅读|高效压缩位图RoaringBitmaps设计原理
Clickhouse在大数据分析平台-留存分析上的应用
导语 | 本文实践了对于千万级别的用户,操作总数达万级别,每日几十亿操作流水的留存分析工具秒级别查询的数据构建方案。同时,除了留存分析,对于用户群分析,事件分析等也可以尝试用此方案来解决。 文章作者:陈璐,腾讯高级数据分析师   背景 你可能听说过Growingio、神策等数据分析平台,本文主要介绍实现留存分析工具相关的内容。 留存分析是一种用来分析用户参与情况/活跃程度的分析模型,可考查进行初始行为后的用户中,有多少人会进行后续行为,这是衡量产品对用户价值高低的重要指标。如,为评估产品更新效果或渠道推广
腾讯云大数据
2020/08/07
3.8K1
大数据计数原理1+0=1这你都不会算(二)No.50
上一次我们说完了用 HashSet 来进行计数了。我们可以发现,如果我们估计有N个数,那么我们至少需要N*32bit(按照int在32位操作系统下占用32个bit)的空间来进行存储,这太费钱了。有没有
大蕉
2018/02/05
4650
大数据计数原理1+0=1这你都不会算(二)No.50
RoaringBitmap介绍(中文翻译)
原地址:https://github.com/RoaringBitmap/RoaringBitmap
从大数据到人工智能
2022/11/16
2.4K0
一文读懂比BitMap有更好性能的Roaring Bitmap
1.什么是bitmap?为什么使用bitmap?Roaring bitmap与其他bitmap编码技术相比有哪些优势?2.Roaring bitmap将32位无符号整数按照高16位分容器,即最多可能有216=65536个容器(container),存储数据时,按照数据的高16位找到container(找不到就会新建一个),再将低16位放入container中。高16位又称为共享有效位,它用于索引应该到哪个容器中查找对应的数值,属于roaring bitmap的一级索引。3.Roaring bitmaps以紧凑高效的两级索引数据结构存储32位整数。高密度块使用位图存储;稀疏块使用16位整数的压缩数组。当一个块包含不超过4096个整数时,我们使用一个排好序的16位整数数组。当有超过4096个整数时,我们使用2^16 位的位图。为什么按4096作为阀值呢?仅仅是因为当数据块中的整数数量超过这个值之后,bitmap将比数组的内存使用率更高。
山行AI
2020/11/26
10K0
大数据计数原理1+0=1这你都不会算No.77
完结篇。 这个系列写到这里算是结束了,真是不容易说实话,查了好多好多的资料,真的很难相信懒得要命的我能写完这个系列 T_T。有兴趣的小伙伴可以在菜单看看整个系列。 好啦,开始今天的主题,今天主要呢,聊最后两个基数估计算法,一个是 Adaptive Counting ,一个是 HyperLogLog Counting 。话不多说,直接简单粗暴从 Adaptive Counting 开始吧。 Adaptive Counting 其实就是一个组合算法。原始论文是 《 Fast and accurate traf
企鹅号小编
2018/01/12
6260
大数据计数原理1+0=1这你都不会算No.77
Flink基于两阶段聚合及Roaringbitmap的实时去重方案
去重是大数据计算中的常见场景,本文介绍了Flink结合数据倾斜问题的一般性解决方案——两阶段聚合,以及位图(Bitmap)的优化版数据结构——Roaringbitmap给出的一种实时去重解决方案,并在最后与其他方案进行了对比。
可君
2023/01/03
3.5K0
位图bitmap的改进版:Roaring Bitmap
咆哮位图,是一种压缩位图,是对bitmap的改进,除了使用bitmap存储数据,还使用了array等数据结构,以达到压缩的目的。
cuiyi
2023/01/09
3K0
Redis 精确去重计数 —— 咆哮位图
如果要统计一篇文章的阅读量,可以直接使用 Redis 的 incr 指令来完成。如果要求阅读量必须按用户去重,那就可以使用 set 来记录阅读了这篇文章的所有用户 id,获取 set 集合的长度就是去重阅读量。但是如果爆款文章阅读量太大,set 会浪费太多存储空间。这时候我们就要使用 Redis 提供的 HyperLogLog 数据结构来代替 set,它只会占用最多 12k 的存储空间就可以完成海量的去重统计。但是它牺牲了准确度,它是模糊计数,误差率约为 0.81%。
老钱
2019/06/11
2.1K1
推荐阅读
相关推荐
大数据计数原理1+0=1这你都不会算(六)No.57
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档