文档章节

Bloom-Filter布隆过滤器

曾劲松
 曾劲松
发布于 2016/10/31 21:36
字数 287
阅读 11
收藏 1

     Bloom-Filter,即布隆过滤器,1970年由Bloom中提出。它可以用于检索一个元素是否在一个集合中。

     Bloom Filter(BF)是一种空间效率很高的随机数据结构,它利用位数组很简洁地表示一个集合,并能判断一个元素是否属于这个集合。它是一个判断元素是否存在集合的快速的概率算法。Bloom Filter有可能会出现错误判断,但不会漏掉判断。也就是Bloom Filter判断元素不再集合,那肯定不在。如果判断元素存在集合中,有一定的概率判断错误。因此,Bloom Filter不适合那些“零错误”的应用场合。而在能容忍低错误率的应用场合下,Bloom Filter比其他常见的算法(如hash,折半查找)极大节省了空间。 

      它的优点是空间效率和查询时间都远远超过一般的算法,缺点是有一定的误识别率和删除困难。

 

参考文献:

博文一:http://blog.csdn.net/hguisu/article/details/7866173

博文而:http://blog.csdn.net/hguisu/article/details/7856239

© 著作权归作者所有

曾劲松
粉丝 5
博文 200
码字总数 141434
作品 0
武汉
私信 提问
布隆过滤器之Counting Bloom Filter

---title: 布隆过滤器之Counting Bloom Filtersubtitle: Counting Bloom Filterdescription: Spectral Bloom Filterkeywords: [算法,bloom filter,布隆]author: liyzdate: 2019-01-11tags: ......

freeli
01/14
0
0
布隆过滤器(Bloom Filter)

基本概念 如果想判断一个元素是不是在一个集合里,一般想到的是将所有元素保存起来,然后通过比较确定。链表、树、散列表(又叫哈希表,Hash table)等等数据结构都是这种思路。但是随着集合...

行者PHPer
2014/04/12
0
0
如何实现大数据集查询?Bloom Filter或许是你想要的

1、什么情况下需要布隆过滤器? 先来看几个比较常见的例子 字处理软件中,需要检查一个英语单词是否拼写正确 在 FBI,一个嫌疑人的名字是否已经在嫌疑名单上 在网络爬虫里,一个网址是否被访...

流川枫AI
2017/06/18
0
0
Bloom filter在分布式环境中的应用

Bloom filter在分布式环境中的应用 未命名2017-05-0427 阅读 filter技术分布式 概述 布隆过滤器是一个应用非常广泛的概率型数据结构,一般用于判断一个元素是否存在一个集合中,比如在字处理...

未命名
2017/05/04
0
0
BitSet和布隆过滤器(Bloom Filter)

布隆过滤器 Bloom Filter 是由Howard Bloom 在 1970 年提出的二进制向量数据结构,它具有很好的空间和时间效率,被用来检测一个元素是不是集合中的一个成员。如果检测结果为是,该元素不一定...

凯文加内特
2016/01/15
187
0

没有更多内容

加载失败,请刷新页面

加载更多

状态模式

//相当把一个State对象存到Context对象中,然后通过Context实例化对象调用保存的state对象去调用state的相应的方法 https://blog.csdn.net/syc434432458/article/details/51210361...

南桥北木
14分钟前
0
0
基于 Jenkins + JaCoCo 实现功能测试代码覆盖率统计

本文首发于:Jenkins 中文社区 使用 JaCoCo 统计功能测试代码覆盖率? 对于 JaCoCo,有所了解但又不是很熟悉。 "有所了解"指的是在 CI 实践中已经使用 JaCoCo 对单元测试代码覆盖率统计: 当...

Jenkins中文社区
21分钟前
2
0
聊聊Elasticsearch的OsProbe

序 本文主要研究一下Elasticsearch的OsProbe OsProbe elasticsearch-7.0.1/server/src/main/java/org/elasticsearch/monitor/os/OsProbe.java public class OsProbe { private static f......

go4it
22分钟前
0
0
谈谈lucene的DocValues特性之NumericDocValuesField

在默认实现的DocValuesCosumer中,数值有可能分块存储也有可能放在一个数据块中存储。 分块的大小默认是16384,并且通过预先计算如果按一个块存储最大值与最小值的差所占用的比特数和分块存储...

FAT_mt
40分钟前
0
0
【BATJ】面试必问MySQL索引实现原理

BATJ面试题剖析 1、为什么需要使用索引? 2、数据结构Hash、平衡二叉树、B树、B+树区别? 3、机械硬盘、固态硬盘区别? 4、Myisam与Innodb B+树的区别? 5、MySQL中的索引什么数据结构? 6、...

须臾之余
今天
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部