二路平衡动态布隆过滤器  

2-Balance Dynamic Bloom Filter

作　　者：孙智超[1] 徐蕾[1] 

机构地区：[1]沈阳航空航天大学计算机学院,辽宁沈阳110136

出　　处：《数学的实践与认识》2014年第5期199-205,共7页Mathematics in Practice and Theory

摘　　要：针对动态布隆过滤器所表示的集合中由于元素的增加而导致的存储空间增加问题,提出了二路平衡动态布隆过滤器结构及相应的集合元素插入算法.新过滤器按向量组的方式扩充存储空间,新元素的插入是在向量组中查找插入位置,使得组向量中新置为1的位置增加最少.实验结果表明,当向量组中的向量数为2时,新方法比动态布隆过滤器节省5%的存储空间.This paper propose the 2-Balance Dynamic Bloom Filter data structure and it＇s insert algorithm to relieve the increase of space of the Dynamic Bloom Filter. This new Bloom Filter increase the storage space based on vector team patten and insert the element to the corresponding Bloom Filter to make the 1-value bit increase slower.The experiment result show this scheme can save 5% space at nearly no waste of time than Dynamic Bloom Filter.

关 键 词：集合的表示与查找 布隆过滤器 动态布隆过滤器 哈希查找 

分 类 号：O212[理学—概率论与数理统计]