摘要
本文探讨布鲁姆过滤器的代数运算和集合查询的关系,定义布鲁姆过滤器的"并","交","异或","补","差"代数运算,从理论和实验两方面分析布鲁姆过滤器的代数运算和集合代数运算并集,交集,异或集,补集,差集的元素查询关系.理论分析和实验结果表明,布鲁姆过滤器的"并","交"运算能够支持集合并集交集的元素查询,这一结论可以简化利用布鲁姆过滤器进行的系统设计.
This paper discusses the relationship between algebraic operations on Bloom filters and algebraic operations on data sets. This paper completely define algebraic operations including OR, AND, XOR, NOT, MINUS on Bloom filter, and study the membership query performance on Bloom filter and data set. Theoretical analyses and simulation results show that the Bloom filter ORed （ANDed） from the original Bloom filters can support element membership query on data set ORed （ANDed） from the original data sets, which can be a nick to real application.
出处
《电子学报》
EI
CAS
CSCD
北大核心
2008年第5期869-874,共6页
Acta Electronica Sinica
基金
国防基础科研“十一五”规划(No.A1420060162)
关键词
计算机网络
分布式计算
分布式消息系统
集合元素查询
代数运算
computer networks
distributed computing
distributed information system
set membership query
algebraic operations
