布鲁姆过滤器查询算法.pdf

: .
ISSN 1000-9825, CODEN RUXU息
空间给网络资源存储、管理、定位、
算机应用程序的核心,是进行资源查找、定位、访问和交换的关键,是网络和分布式系统资源共享最基本的操
,集合的表示和访问就越来越困难,如何表示海量资源信息,如何快速、高效地在海
量信息中查找所需的资源成为国、,在高速发展的网络和计算机系统环境下,研究
简洁的结构表示资源信息,设计与之对应的高效查询算法查找定位资源信息,成为提升网络软件体系结构,进行

∗ Supported by the National Natural Science Foundation of China under Grant , 90604015 (国家自然科学基金)
Received 2007-09-12; Accepted 2008-08-07谢鲲 等:布鲁姆过滤器查询算法 97

高效的大规模数据管理的关键,亦成为多种网络应用得以最终推广的基础.
作为一种精简的信息表示方案,布鲁姆过滤器(Bloom filter)[1]能够满足高速网络发展中高效资源交互和查
,,支持集合元素查询,又
k 个哈希函数映射到位串向量
,布鲁姆过滤器中哈希表退化成一个位串向量 V,
的树型查询算法和哈希查询算法存储空间与元素自身大小和集合规模直接相关,而布鲁姆过滤器查询算法所
需存储空间与元素自身大小和集合规模无关, m bit 的 V 向量可以表示 n
个元素的集合,每个元素平均只需要 m/n 比特位,(即属于
集合中的元素而误判为不属于集合中)[1,2].因此,布鲁姆过滤器是一种允许存在一定误判的情况下,存储空间节
俭的哈希结构,是在查询准确率和存储代价之间的折衷.
由于哈希查找的常数时间和存储空间开销较小,布鲁姆过滤器查询算法具有很好的实用价值[3,4].自算法首
次提出以来,已广泛应用于各种计算机系统中,用以表达庞大数据集合、
数据库操作、字典查询和文件操作[5−9] 10 年,随着网络研究的发展以及新的覆盖网和 P2P 网络应用
技术的涌现,出现了布鲁姆过滤器查询算法研究高潮,应用于网络的领域和方式越来越多[3,10]:包括覆盖网和
P2P 节点协作交互[11−13]、资源路由[14]、数据帧路由标签[15]、网络测量管理[16−24]、网络入侵检测[25−27]、Ad hoc
网络中信息共享[28]和传感器网络数据过滤和路由[29,30] Brooder 和 Mitzenmacher 预言[3],目
前这些布鲁姆过滤器查询算法在网络上的应用还只是冰山一角,随着布鲁姆过滤器查询算法越来越多地被研
究人员所认识和重视,它将在现代计算机网络和一些新的学术领域得到更为广泛的应用.
,出现了多种
标准布鲁姆过滤器(standard Bloom filter)查询算法[1]的改进算法,包括:计数式布鲁姆过滤器(counting