i-DBF: an Improved Bloom Filter Representation Method on Dynamic Set12
Bloom Filter is a simple space-efficient randomized data structure for representing a set in order to support membership queries, which uses an m-bit array to represent a data set. Dynamic bloom filter (DBF) can support concisely representation and approximate membership queries of dynamic set instead of static set. It has been proved that DBF not only possess the advantage of standard bloom filter,but also has better features when dealing with dynamic set.But DBF also has a disadvantage: the addition operation which mapped element x into bloom filter s will become no sense, if some of the first s-1 bloom filters have already responded that element x is in set A with some false positive probability. We point out this shortcoming and improve the addition operation with a new algorithm. We call this improved dynamic bloom filter i-DBF. Finally, we prove that this i-DBF has better performance both in the storage space and in the false positive probability.
Jiacong Wang Mingzhong Xiao Jing Jiang Bonan Min
Computer Networks and Distributed Systems Laboratory Peking University, China
国际会议
第五届网格与协同计算国际会议(The Fifth International Conference on Grid and Cooperative Computing GCC 2006)
长沙
英文
156-162
2006-10-21（万方平台首次上网日期，不代表论文的发表时间）