双布鲁姆过滤器法查询集合成员

计算机工程与应用 ›› 2012, Vol. 48 ›› Issue (28): 10-15.

双布鲁姆过滤器法查询集合成员

田小梅1，2，张大方1，史长琼1，杨晓波1

1.湖南大学信息科学与工程学院，长沙 410082
2.湖南环境生物职业技术学院信息技术系，湖南衡阳 421005

出版日期:2012-10-01 发布日期:2012-09-29

Membership queries using double bloom filters

TIAN Xiaomei1，2, ZHANG Dafang1, SHI Changqiong1, YANG Xiaobo1

1.School of Information Science and Engineering, Hunan University, Changsha 410082, China
2.Department of Information Technology, Hunan Environment-Biological Polytechnic, Hengyang, Hunan 421005, China

Online:2012-10-01 Published:2012-09-29

摘要/Abstract

摘要： 探讨双布鲁姆过滤器查询法查询集合并集、交集、补集、差集或对称差成员的性能问题。理论分析和实验结果表明，双布鲁姆过滤器查询法能够较好地支持集合并集、交集、补集、差集及对称差的成员查询问题，其中双布鲁姆过滤器并集及交集查询不会产生假阴性，仅有少量假阳性的存在，而双布鲁姆过滤器补集、差集及对称差查询则除存在少量假阳性外，还存在少量假阴性。

关键词: 布鲁姆过滤器, 数据同步, 多关键字检索, 集合调和

Abstract: This paper examines the problem of membership queries for set union, intersection, complementary set, sets difference or symmetric difference between sets by using double Bloom filters. The theoretical analysis and experimental results show that the double-Bloom-filter query method can support membership queries for set union, intersection, complementary set, sets difference or symmetric difference between sets, of which membership queries for set union or intersection have no false negatives, only a few false positives, while membership queries for complementary set, sets difference or symmetric difference have a small number of false negatives in addition to small amounts of false positives.

Key words: Bloom filter, data synchronization, multi-keyword search, set reconciliation

田小梅1，2，张大方1，史长琼1，杨晓波1. 双布鲁姆过滤器法查询集合成员[J]. 计算机工程与应用, 2012, 48(28): 10-15.

TIAN Xiaomei1，2, ZHANG Dafang1, SHI Changqiong1, YANG Xiaobo1. Membership queries using double bloom filters[J]. Computer Engineering and Applications, 2012, 48(28): 10-15.

[1]	杨海涛1，张传斌2，阮镇江1，徐飞1 . 大规模云同步归集数据系统的异步并行优化[J]. 计算机工程与应用, 2017, 53(2): 88-97.
[2]	史长琼，吴丹，肖瑞强. 能抵抗拒绝服务攻击且高效的RFID安全认证协议[J]. 计算机工程与应用, 2016, 52(2): 105-111.
[3]	孟金凤，高仲合. 基于DCBF的流抽样测量算法[J]. 计算机工程与应用, 2015, 51(17): 92-95.
[4]	王春龙，刘渊，郑哲渊. 基于LRU和扩展CBF的网络大流检测[J]. 计算机工程与应用, 2015, 51(13): 66-71.
[5]	席晔文，杨金民. 基于双布鲁姆过滤器的数据排重技术[J]. 计算机工程与应用, 2014, 50(23): 198-202.
[6]	郑扬飞1，金辉1，张勇1，裴东良2. 消防一体化环境下的信息交换平台关键技术研究[J]. 计算机工程与应用, 2012, 48(7): 219-223.
[7]	詹求翔¹，王春露¹，生拥宏²，鞠大鹏²，汪东升². 一种基于数据差异的逻辑卷快速同步方法[J]. 计算机工程与应用, 2010, 46(1): 61-63.
[8]	杨志和胡虚怀. 移动环境下的数据同步模型研究[J]. 计算机工程与应用, 2007, 43(13): 191-193.