博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
DataStructure.BloomFilter
阅读量:6747 次
发布时间:2019-06-25

本文共 1908 字,大约阅读时间需要 6 分钟。

Bloom Filters Ref[1]

1. 简介

Bloom filter(布隆过滤器;有更好的或正确的翻译,告诉我) 是一个数据结构,该数据结构快速并且内存高效,它可以告诉你某个元素是否在集合中。

作为高效的代价,Bloom filter是存在概率的数据结构:它告诉我们某个元素一定不在集合中,或者可能在集合中。

Bloom filter的基本数据结构是Bit Vector。

在Ref[1]中有简单形象的例子来说明Bloom Filter。

1.1 Hash Functions

在Bloom Filter中的hash function应该是独立的并且是均匀分布的。应该选用尽可能快的hash function。(sha1虽然被广泛使用,

但是在Bloom Filter的实现中并不是好的选择)。

hash function有:murmur, fnv, Jenkins Hashes。

1.2 How big should I make my Bloom filter?

false positive rate: (1-e-kn/m)k

false positive rate: 是指假肯定率(Q[1]: false positive rate 是指???)

k: hash function的个数

m: filter中的bits数

n: 已经被插入到filter里的元素个数 

 

1.3 应该使用多少hash function? 

hash function越多,bloom filter越慢,bloom filter就越容易被填满。如果hash function太少,就会得到太多的假肯定(false positive)。

由于在创建filter时必须为k选择一个值,你需要对n的变动范围进行界定。一旦范围确定了,仍然需要选择一个潜在的m和k。

幸运地,给定m和n,我们有一个函数来选择k的最佳值:(m/n)ln(2)

接下来选定bloom filter的尺寸/大小:

  1. 选择一个n的范围值

  2. 为m选择一个值

  3. 计算k的最佳值

  4. 根据n,m,k来计算error rate。如果该值不可接受,需要返回第二步并修改m的值。

 

1.4 How fast and space efficient is a Bloom filter?

一个给定有m个bits和k个hash function的Bloom filter,插入和成员身份的测试是O(k)

 

2. Bloom Filter的应用案例 

[Todo] 


Reference

1. Bloom Filters by Example

http://billmill.org/bloomfilter-tutorial/

1.1 http://blip.tv/pycon-us-videos-2009-2010-2011/pycon-2011-handling-ridiculous-amounts-of-data-with-probabilistic-data-structures-4899047

1.2 Network Application of Bloom Filter: A Survey

http://citeseer.ist.psu.edu/viewdoc/download;jsessionid=6CA79DD1A90B3EFD3D62ACE5523B99E7?doi=10.1.1.127.9672&rep=rep1&type=pdf

1.3 Less Hashing, Same Performance

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.152.579&rank=1

1.4 Scalable Bloom Filters [AAAA]

http://gsd.di.uminho.pt/members/cbm/ps/dbloom.pdf

1.5 

https://sites.google.com/site/murmurhash/

1.6 

http://isthe.com/chongo/tech/comp/fnv/

1.7 

http://www.burtleburtle.net/bob/hash/doobs.html

2. Bloom Filter  [AAAAA]

http://en.wikipedia.org/wiki/Bloom_filter

 

转载于:https://www.cnblogs.com/cwgk/p/4024853.html

你可能感兴趣的文章
Folding Views
查看>>
11 个让你吃惊的 Linux 终端命令
查看>>
基本磁盘、动态磁盘、GPT磁盘、MBR磁盘
查看>>
cookie注入&中转注入笔记
查看>>
生产环境linux服务器系统安全配置
查看>>
我的友情链接
查看>>
MySql中 delimiter 详解
查看>>
浏览器history操作实现一些功能
查看>>
你那么喜欢看”干货“,是因为你根本不想下功夫。
查看>>
Introduction to ASP.NET MVC 4
查看>>
20172303 2017-2018-2 《程序设计与数据结构》结对编程项目-四则运算 第二周
查看>>
程序员需要具备哪些素质
查看>>
LCM性质 + 组合数 - HDU 5407 CRB and Candies
查看>>
python测试一
查看>>
Python之路【第十一篇】:三目运算、不同数据类型的存储方式及深浅拷贝(copy模块)、列表推导式...
查看>>
比map更强大的multimap
查看>>
JS事件中的对象
查看>>
工作流引擎Oozie(一):workflow
查看>>
repo sync下载脚本
查看>>
spfa(前向星)
查看>>