计数布鲁姆过滤器代数运算

摘要

文中探讨计数布鲁姆过滤器的代数运算和集合运算的一致性关系,研究使用计数布鲁姆过滤器代数运算进行集合成员查询的性能.理论分析和实验结果表明,计数布鲁姆过滤器的并、交、补、减、异或运算产生的新过滤器依然保持计数布鲁姆过滤器的特征,支持元素的删除操作,不会出现假阴性,能用于集合并集、交集、补集、差集及对称差的成员查询；当使用两个原始的计数布鲁姆过滤器查询补集、差集及对称差元素时,会存在部分本来属于补集、差集或对称差的元素被判为不属于补集、差集或对称差的问题,而使用计数布鲁姆过滤器代数运算后的过滤器进行补集、差集及对称差成员查询,则不存在上述问题,空间效率能提高一倍,时间效率亦能显著地得到改善.计数布鲁姆过滤器代数运算的使用有利于进一步扩展计数布鲁姆过滤器的应用范围.譬如计数布鲁姆过滤器减运算可用作一种新的集合调和方法,用于分布式系统中大型文件的分发.%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.