bloomfilter布隆过滤器学习资料大全资源-CSDN文库

共27个文件

pdf：23个

nh：2个

pot：1个

bloom

filter

5星 · 超过95%的资源需积分: 14 185 浏览量 2011-08-10 13:05:29 上传评论收藏 13.99MB RAR 举报

资源推荐

资源详情

资源评论

收起资源包目录

bloom filter布隆过滤器学习资料.rar （27个子文件）

bloom filter布隆过滤器学习资料

bf源码

基于BloomFilter的路径表达式查询处理.nh 6.52MB

布隆过滤器BF.pdf 835KB

10.1.1.147.9455.pdf 142KB

oceanstore an architechture for global scale persistent storage.pdf 127KB

BloomFilter和WeightedBloomFilte的比较和研究.nh 1.78MB

bfdesigninnovationand novel app.pdf 109KB

HIERACHICAL BF ARRAYS A NOVEL SCALABLE METADATA MANAGEMENT SYSTEM.pdf 232KB

p26-article-pey.pdf 257KB

xiaomingzhong101003-201009-10.pdf 255KB

5701464_Parameterized_bloom_filters.pdf 599KB

BloomFilters散列函数数目多阶段动态优化算法.pdf 4.1MB

Bloom Filter学习心得.pdf 1.19MB

248.pot 206KB

1onthe falsepositive rateof bf.pdf 142KB

multicompressedcountingbf.pdf 259KB

generalizedbf.pdf 439KB

10.1.1.86.3346.pdf 159KB

scaling filename queries in a large scale distributed fs.pdf 158KB

p570-mullin.pdf 182KB

基于bloomfilter的多模式匹配引擎设计与应用.kdh 839KB

Bloom Filter.pdf 138KB

10.1.1.91.6328.pdf 398KB

10.1.1.116.5755.pdf 456KB

cachehashandspaceefficientbf.pdf 209KB

anoptimalbfreplacement.pdf 192KB

dbloom.pdf 170KB

10.1.1.164.7239.pdf 316KB

Bloom Filters 散列函数数目多阶段动态优化算法

张  伟

1, 2

, 王汝传

1, 2

( 1. 南京邮电大学计算机学院, 江苏南京 210003; 2. 南京邮电大学计算机技术研究所, 江苏南京 210003)

  摘 要:  标准 Bloom Filters 在操作前需要知道数据集合中不同元素数目才能确定最佳的 Hash 函数数目, 但是数

据集的分布情况并不容易事先获得. 本文提出一种多阶段 Hash 函数数目动态优化的 Bloom Filters( Multistage Dynamic

optimization Bloom Filters , MDBF) , 它将元素插入过程分为多个阶段, 在每个阶段根据比特向量的使用情况分析插入元

素的分布, 动态调整最优的 Hash 函数数目. 实验表明 MDBF 能够适应元素多样性和偏斜分布的复杂情况, 选择最优的

Hash 函数数目, 获得更低的误检率.

关键词:  Bloom Filters; hash 函数; 偏斜分布; 误检率

中图分类号:  TP393   文献标识码:  A    文章编号:  03722112 ( 2011) 04087706

A MultiStage Dynamic Optimization Algorithm for

Bloom Filters Hash Functions Number

ZHANG Wei

1, 2

, WANG Ruchuan

1, 2

( 1. College of Computer , Nanj ing University of Posts & Telecommunications, N anji ng , Jiangsu 210003, China;

2. Institute of Computer Technology , Nanjing University of Posts & Telecommunications , Nanjing , Jiangsu 210003, China )

Abstract:  Standard Bloom Filters needs to know the number of different elements in data set in order to determine the opti

mal number of hash functions.However, the data distribution information is not easy to obtain prior. This paper proposes a multi

stage dynamic optimization for Bloom Filters hash functions number ( MDBF ) . It splits element insertion procedure into several

stages, and in each stage of element insertion, M DBF decides the optimal hash function number by analyzing the inserted data distri

bution with bit vector usage situation. The experimental results show that MDBF can select the optimal number of hash functions to

obtain low false po sitive probability in complicated applications, which have element multiplicity and skewed distribution.

Key words:  bloom filters; hash function; skewed distribution; false positive probability

1  引言

  标准 Bloom Filters ( Standard Bloom Filters, SBF)

[ 1]

是

一种支持对元素集合成员关系查询的空间压缩数据结

构, 主要用于在有限空间中对大量数据进行管理的场

合. 近年来标准 BF 在网络应用领域中受到越来越多的

重视

[ 2]

, 如在 Web 缓存机制

[ 3]

中, 使用少量的空间生成

标准 BF 来保存大量邻居节点的资源存储情况, BF 应用

还包括 P2P 网络

[ 4]

、数据包分类

[ 5]

、快速 Hash 表查找

[ 6]

和路由过滤

[ 7]

等众多领域. BF 的各种改进版本可以分

为应用扩展、性能扩展和结构扩展三类. BF 的应用扩展

以 Counting Bloom Filters

[ 3]

, Compressed Bloom Filters

[ 8]

为

代表, 计数型 BF 使用多比特计数器代替标准 BF 中的

单比特位, 支持频度测量. 压缩型 BF 根据 Shannon 编码

原理, 通过改变标准 BF 比特向量串中 0 和 1 出现的概

率, 达到压缩数据的目的. BF 的性能扩展强调利用数据

信息来优化 BF 的设计, 如Weighted Bloom Filter

[ 9]

和 Bas

ket Bloom Filter

[ 10]

, 加权 BF 针对不同的元素使用不同数

目的 Hash 函数, 具体的Hash 数目取决于元素的查询频

率和集合相似度, 整个加权 BF 的误检值是所有元素查

询频度的加权和. 分档 BF 把元素分为若干集合, 不同

档的集合使用不同数目的 Hash 函数, 使总的查询失效

代价更小. BF 的结构扩展可以看成是多个 BF 的组合,

典型的有拆分型 Bloom Filters

[ 11]

、Dynamic Bloom Filters

[ 12]

和Timedecaying Bloom Filters

[ 13]

. 它们的共同之处是在标

准 BF 结构上进行空间的扩展, 都通过将 BF 的位向量

收稿日期: 20080925; 修回日期: 20100910

基金项目: 国家自然科学基金 ( N o. 60973193, 61003039, 61003236) ; 江苏省自然科学基金( No. BK2008451) ; 省级现代服务业发展专项基金( No.

0801019C) ; 国家博士后基金 (No. 20090451241) ; 江苏高校科技创新计划项目( No. CX09B

153Z, CX10B

260Z, CX10B

261Z, CX10B

262Z) ; 江苏省

六大高峰人才项目( No. 2008118) ; 江苏省计算机信息处理技术重点实验室基金( 2010)



第 4 期

2011 年 4 月

电   子   学   报

ACTA ELECTRONICA SINICA

Vol . 39  No. 4

Apr.  2011



转换为由多个位向量组合来解决 BF 容量溢出时的可

扩展性问题. 不同之处在于增加空间的方式和使用方

式不同, 拆分型 Bloom Filters 和 Dynamic Bloom Filters 增

加方式类似, 是一种简单的空间线性增加, Timedecaying

Bloom Filters 使用预留的缓冲池直接对数值溢出的计数

器进行空间增加. 还有一些具体改进方法融合了两类

或者全部三类扩展, Spectral Bloom filters

[ 14]

使用一种基

于多个计数型 BF 更加精确的频度估计方法、SpaceCode

Bloom Filters

[ 15]

在一个标准 BF 上使用多组 Hash 函数.

BF 结构扩展需要附加空间, 这和 BF 空间受限的使

用背景是相悖的, 因此本文主要针对 BF 性能扩展方

法, 即不使用附加空间, 充分利用数据的自身信息得到

比标准 BF 更好的设计. 加权 BF 和分档 BF 都是在单个

BF 空间上讨论如何利用数据信息来优化 Hash 函数的

使用, 前者侧重于理论探讨, 后者给出了具体的方法和

应用实例. 但是在很多数据流

[ 18]

应用场合, 由于难以预

测数据的分布, 使得这些方法难以应用. 本文提出了一

种 Bloom Filters 散列函数数目多阶段动态优化算法 ( A

Mult istage Dynamic Optimization Algorithm of Bloom Filters

Hash Functions Number, MDBF) , MDBF 不需要对数据集

进行预处理, 而是在元素插入的同时分析比特向量的

使用情况, 推断元素分布信息, 计算并调整更合适的

Hash 函数数目, 从而降低误检率, 提高 BF 的性能.

2  多阶段动态 Bloom Filters

  标准 BF 假设一个样本空间 U 和一个样本元素集

合S= { s

, s

, , s

} , S  U, 其中 n= | S | , N = | U

| , 并且 n< < N . n 个元素使用k 个 Hash 函数映射到一

个长度为 m 的向量 V 中, 每个 Hash 函数互相独立, 其

映射范围为[ 0~ m- 1] , 标准 BF 误检率为

= ( 1- ( 1-

)

 ( 1- e

- kn / m

)

( 1)

  标准 BF 的 Hash 函数的最优数目为

k = ( m/ n) ln2 ( 2)

  在 BF 中, 同一元素在集合中的多次出现只是对同

一比特位的重复设置, 不会影响其它的比特位. 因此式

(2) 中 n 的准确表示不是集合S 的势, 而是集合 S 中不

同状态元素的势.

  定义 1  C 为集合 S 中的不同元素的数目, C = |

S | , S = { s

| s

 S , i , j  s

 s

}

  定义 2  f

( i ) , 0  t  L , 0  i  n 为 t 阶段处理集

合 S 中第 i 个元素后的不同元素数目, f

( 0) = 0, f

( n)

= C, 该状态下最优Hash 函数数目为 k

( i ) =

( i )

ln2.

在实际应用中 f

( i ) 函数的走向直接反应数据的分

布情况, MDBF 根据 BF 中保持为 0 的比特位的情况来

估计插入 i 个元素后的不同元素数目f

( i ) .

  定义 3  状假设 MDBF 的插入操作分为 L 个阶段,

S= { s

, s

, , s

} 被划分为 L 段S = { d

, d

, ,

} , n

= | d

| 满足 n=



i= 1

, 即存在 L 个检查点对

MDBF 中置0 的比特位进行统计, 得出插入 i 个元素后t

阶段的不同元素状态数 f

( i ), 0  t  L , 0  i  n, 从而

得出 t 阶段的最优Hash 函数数目 k

  定理 1  MDBF 插入 d 段元素后保持为 0 的比特位

数目应该为

Num

NullBits

= m  (1-

)



t= 1

( k

t- 1

( f

- f

t- 1

) )

( 3)

其中,

( i ) = ( ( log

( 1-

)

Num

NullBits

) -



i- 1

t= 1

t- 1

( f

- f

t- 1

) )

/ k

i- 1

+ f

t- 1

( 4)

  证明  一个比特位在一次 Hash 映射后被设置为 1

的概率为 1/ m, 那么保持为 0 的概率为 1- 1/ m, d 段即



i= 1

个元素插入后对特定比特位的影响可以分段来

考虑, 第一段插入 n

个元素, 实际上只有 f

( n

) 个不同

的元素, 所以使用 k

个 Hash 函数插入后, 该比特位保

持为 0 的概率为( 1- 1/ m) M, M = k

( n

) . 第二段插

入 n

个元素, 实际上在第二阶段增加了 f

( n

+ n

) -

( n

) 个不同的元素, 所以使用 k

个Hash 函数插入后,

该比特位保持为 0 的概率为( 1- 1/ m) M  , M  = k

( n

) + k

( n

+ n

) - f

( n

) ) . 依次类推, 最终插入

n 个元素具有不同的状态f

( n) , 不同阶段使用了不同

的 k

, 总计执行的插入次数为 M =



t= 1

( k

t- 1

 ( f

t- 1

) ) . BF 共有 m 个比特位, 那么整个 BF 中保持为 0

的数目应该为 Num

NullBits

= m  M , 即式( 3) , 由式( 3) 直

接可以反推出式( 4) , 证毕.

  定义 4  数据分布偏倚度 = i / f

( i ) , 0< i  n, 

代表整个数据集合中的数据分布情况, 较大的 说明

分布中数据的不同状态数目较少, 即存在重复元素的

越多, 偏斜分布越严重.

878   电  子   学   报 2011 年

评论收藏

内容反馈

zizzyzhao

2013-04-30

不过还是都整理到一起了还有一些英文文献的
x50430618

2011-10-18

东西也太乱了，就是把网上的那些pdf搜集了一下，全部都讲的一样样的- -

Jetway_wmn

粉丝: 11
资源: 15

bloom filter布隆过滤器学习资料大全

最新资源

bloom filter布隆过滤器学习资料大全

【技术分享】Bloomfilter布隆过滤器.pptx

Java版本的BloomFilter (布隆过滤器)

php.bloom.filter:布隆过滤器

bloom filter(C#版自制布隆过滤器)

Bloom_filter_(C).zip_bloom_bloom filter_c++布隆_布隆过滤器

布隆过滤器(bloom filter)及php和redis实现布隆过滤器的方法

介绍Bloom Filter（布隆过滤器）原理、实现及具体应用

硬核 - Redis 布隆（Bloom Filter）过滤器原理与实战.doc

布隆过滤器C源码-bloomfilter.rar

布隆过滤器BloomFilters的一个简单Java库

redis-lua-scaling-bloom-filter：用于缩放布隆过滤器的LUA Redis脚本

Go-布隆过滤器的一个Go实现参考bloomfilter.js

布隆过滤器（利用布隆过滤器实现文字的嵌入和查找功能）

布隆过滤器之C++实现

java实现的布隆过滤器算法

布隆过滤器-BloomFilter

布隆过滤器在网页去重中的应用

利用Java手写一个布隆过滤器Bloom Filter

bloomfilter简介

Python+Redis实现布隆过滤器

Java 实现的高性能布隆过滤器！.zip

解决Win 10与不兼容VirtualBox操作过程文档+（附带软件）.zip

计算机网络知识点总结(谢希仁第八版).pdf

Xshell软件(配色方案&amp;高亮关键字/突出显示集)的相关文件

湖南科技大学《计算机网络》配套课件（PDF版）

《计算机网络自顶向下方法第7版》中文PDF+复习题问题中文版答案

计算机网络自顶向下方法第八版答案

hevc视频扩展免费2.0.53348.0x64

最新资源

Xshell软件(配色方案&高亮关键字/突出显示集)的相关文件