Bloom Filter技术及应用

Bloom Filter technology and its applications

Bloom Filter采用位串向量表示数据集合,能够实现高效集合查询的数据结构。首先介绍了标准布隆过滤器的概念和工作原理,然后通过实验分析布隆过滤器的错误率、空间向量和哈希函数数量三者之间的动态相关关系,并对独立空间布隆过滤器和标准布隆过滤器性能进行对比,最后讨论了Bloom Filter的变种及应用。

Bloom Filter is a data structure that uses bit string vector to represent data set so as to meet efficient membership queries. First,the concept and the operating principle of standard Bloom Filter were given. Second,based on experiments,the dynamic relationships among the false positive,the vector space and the numbers of hash function of Bloom Filter were analyzed. Furthermore,the performance of independence space Bloom Filter and that of standard Bloom Filter were compared. Finally,applications and development of Bloom Filter were discussed.