K分组合型Bloom Filter方法的设计  

K-Divided Bloom Filter Algorithm and Its Analysis

作　　者：李珺[1] 刘晓光[1] 王刚[1] 刘璟[1] 

机构地区：[1]南开大学计算机科学与技术系,天津300071

出　　处：《计算机研究与发展》2008年第z1期48-52,共5页Journal of Computer Research and Development

基　　金：国家自然科学基金项目(90612001);天津市科技发展计划基金项目(043185111-14);南开大学科技创新基金;科学计算机研究所支持

摘　　要：Bloom Filter是一种采用位向量表示数据集合并利用Hash函数支持有效数据查找的方法.它能够很好地判定某个元素是否属于给定的集合.拆分型Bloom Filter是Bloom Filter的一种改进,它能较好地缓解分布式环境下集合元素动态增长导致的查找误称率增大问题.作为一种新的K分组合型Bloom Filter,通过与Bloom Filter和拆分型Bloom Filter比较分析的结果表明,该方法能够在误称率、向量空间和平均判定时间3个指标中得到较好的平衡.By using a bit vector and a set of hash functions to represent data set, bloom filter can query a given data effectively. Bloom filter can be used to determine whether an element belongs to data set or not. Split bloom filter is an amelioration to the bloom filter, which uses an s×N bit matrix to represent data set. In distributed systems, if the number of the elements increases continually, the increasing error rate of the bloom filter will make the representation nonsensical. Split bloom filter can only weaken this problem. In this paper, a new kind of bloom filter, named as K-divided bloom filter, is presented. Compared with the split bloom filter, it can reduce space and time spending and has a resembling or better performance. K-divided bloom filter gets better tradeoff among error rate, space and time.

关 键 词：BLOOM FILTER RANDOM FILTER 拆分型Bloom FILTER K分组合型Bloom FILTER 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]