您现在的位置:首页 --> 查看专题: bitmap
今天,有个同学向我咨询大数据的一些面试题,其中一类比较有代表性比如判断是否在集合内,比如10个url,判断一个url是否在集合内,还比如有个1~100万个连续无序数字,随机取出里面的N个,求这N个数字等等。这类问题都需要一个大的数据集合,而且每个数据单元都很小,比如一个int 。很大程度上,这类问题可以用Bitmap或者Bloomfilter来做,基本思想就是开辟一块大内存,然后利用一个byte里的8个bit来实现按位标记元素。因为地址空间都是连续的,所以查找都是O(1)的。这里需要说的是,BloomFilter判断属不属于集合,在理论上是存在误判的,如果要求数据100%正确,则不要使用BloomFilter。
这篇文章基于 fastbit 软件包,加以实际的用例对常用的 bitmap 索引算法进行了一个较为系统的介绍。不过生成 bitmap 索引仅仅是第一步,bitmap 索引在存储时会有很大的开销,在不损害(较少损害)查询效率的情况下,对 bitmap 索引进行有效的压缩是一个非常有挑战性的课题。除了 bitmap 索引的生成和存储之外,在不同类型的 bitmap 索引上实现高效的各种类型的查询,也是一个值得进一步探讨的问题。我们很高兴地看到 fastbit 软件包实现了很多这些相关领域的算法,为我们提供了非常宝贵的资料。
[ 共4篇文章 ][ 第1页/共1页 ][ 1 ]
近3天十大热文
- [41] 界面设计速成
- [35] Oracle MTS模式下 进程地址与会话信
- [33] 如何拿下简短的域名
- [32] IOS安全–浅谈关于IOS加固的几种方法
- [32] 程序员技术练级攻略
- [32] 视觉调整-设计师 vs. 逻辑
- [31] 图书馆的世界纪录
- [30] android 开发入门
- [30] 【社会化设计】自我(self)部分――欢迎区
- [27] 读书笔记-壹百度:百度十年千倍的29条法则
赞助商广告