MBF: A real matrix bloom filter representation method on dynamic set

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. In order to support representing dynamic set, dynamic bloom filter (DBF) and split bloom filter (SBF) have been developed. Both DBF and SBF can support concisely representation and approximate membership queries of dynamic set instead of static set. SBF declares that it uses an s Xm bit matrix that consists of s bloom filters to represent a dynamic set, so DBF dose. But in fact, both the two bloom filters are not matrix representation method at all. They are just a set of s bloom filters whose length is m, and they have got a departure from the original idea of bloom filter: the constant query time cost. This paper points out the fact, and then introduce a truly matrix representation method of bloom filter to represent a dynamic set. We call it the Matrix Bloom Filter (MBF). Then, we will analysis the algorithm of MBF and study the average time complexity and the false positive probability. ? 2007 IEEE.EI