Membership queries using double bloom filters

Computer Engineering and Applications ›› 2012, Vol. 48 ›› Issue (28): 10-15.

Previous Articles Next Articles

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

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

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

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

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

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

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

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

[1]	GUO Rui, ZHANG Xuefeng. Combination fingerprint template protection algorithm based on Bloom filter and block [J]. Computer Engineering and Applications, 2018, 54(6): 75-80.
[2]	ZHANG Man1, XIAN Hequn1，2, ZHANG Shuguang1. Fast keyword query technique in encrypted databases [J]. Computer Engineering and Applications, 2018, 54(13): 78-83.
[3]	YIN Qinqin. Secure deduplication approach based on Bloom Filter in hybrid cloud storage environments [J]. Computer Engineering and Applications, 2018, 54(10): 73-80.
[4]	LI Juanjuan1, GONG Xiangyang2. Fast cloned tags detection algorithm in large-scale RFID systems [J]. Computer Engineering and Applications, 2017, 53(8): 106-112.
[5]	DAI Zhen1，2, CHENG Guang1，2. Advanced persistent threat detection based on characteristics of communications [J]. Computer Engineering and Applications, 2017, 53(18): 77-83.
[6]	SHI Changqiong, WU Dan, XIAO Ruiqiang. Resistance to denial of service attacks and efficient RFID security authentication protocol [J]. Computer Engineering and Applications, 2016, 52(2): 105-111.
[7]	MENG Jinfeng, GAO Zhonghe. Flow sampling measurement algorithm based on dynamic counting bloom filter [J]. Computer Engineering and Applications, 2015, 51(17): 92-95.
[8]	WANG Chunlong, LIU Yuan, ZHENG Zheyuan. Network flow measurement based on LRU structure and improved Count Bloom Filter [J]. Computer Engineering and Applications, 2015, 51(13): 66-71.
[9]	XI Yewen, YANG Jinmin. Duplicate data delete technology based on double bloom filter [J]. Computer Engineering and Applications, 2014, 50(23): 198-202.
[10]	WANG Maohua1, HAO Yunli2, CHU Yawei2. Data encryption method based on privacy preserving [J]. Computer Engineering and Applications, 2014, 50(23): 87-90.
[11]	WANG Wenshuai1，2, DU Ran1，2, CHENG Yaodong1, CHEN Gang1. Topic mining method on massive microblog data [J]. Computer Engineering and Applications, 2014, 50(22): 32-37.
[12]	GAO Xiang1, LI Bing2. Research on method to detect reduplicative Chinese short texts [J]. Computer Engineering and Applications, 2014, 50(16): 192-197.
[13]	HU Beibei1, PENG Yanbing2, CHENG Guang3. DNS anomaly detection based on Counting Bloom Filter [J]. Computer Engineering and Applications, 2014, 50(15): 82-86.
[14]	ZHAO Qian，CUI Yi-min，ZOU Tao. Research of Bloom filter application in network forensics [J]. Computer Engineering and Applications, 2010, 46(14): 91-94.
[15]	LI Jing. Mechanism of long-distance service discovery in Grid [J]. Computer Engineering and Applications, 2009, 45(29): 223-225.

Membership queries using double bloom filters

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

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics