Bloom Filter及其在网络中的应用综述

摘要

Bloom filter is the data structure for representing a set , and in smaller cost of misjudgement rate , it achieves storage space saving and instant searching time .In this paper we first study and analyse the Bloom filters and its improved structure , and then emphatically introduce its new applications in a variety of network aspects including the traffic measurement and network security in recent years .In condition of having certain misjudgement rate , Bloom filters provide good solutions for large-scale data set in elements representation and membership query , and for multi-set or dynamic set in elements frequency query et al .%Bloom filter是用来表示集合的数据结构，并以较小的误判率为代价，实现较少的存储空间开销和常数的查找时间。对Bloom filter及其改进结构作了分析研究，并着重介绍最近几年在网络中包括在流量测量和网络安全方面出现的新应用。在一定误判率存在的情况下，Bloom filter为大规模数据集合元素表示、成员查询及多重集和动态集的元素频率查询等提供了解决方案。