Algebra Operations on Counting Bloom Filters
Tian Xiao · Chinese Journal of Computers · 2012
This paper examines the consistence between algebra operations on counting Bloom filters and algebra operations on data sets,and studies the membership query performances of algebra operations on counting Bloom filters.Theoretical analyses and simulations show that the counting Bloom filter which is ORed(ANDed,COMPLEMENTed,SUBTRACTed,XORed) from the original counting Bloom filters can support membership query on data set ORed(ANDed,COMPLEMENTed,SUBTRACTed,XORed) from the original data sets.When using the two original counting Bloom filter to query elements belonged to complementary set,differences or symmetric differences of the two sets,some complementary set elements,differences or symmetric differences of the sets will be misjudged,while the query method using algebra operations on counting Bloom filters has no false negatives and gain a remarkable improvement in space complexity and time complexity over the method using double independent counting Bloom filters,hence it can be applied to various network fields.For example,SUB operation can be used in complete set reconciliation,which is a new set reconciliation,for distributed database and file systems.