|
|||||
|
|
| 布鲁姆过滤器代数运算探讨 | |
| 引用本文： | 谢鲲,张大方,文吉刚,谢高岗,尤志强.布鲁姆过滤器代数运算探讨[J].电子学报,2008,36(5):869-874. |
| 作者姓名： | 谢鲲 张大方 文吉刚 谢高岗 尤志强 |
| 作者单位： | 1. 湖南大学计算机与通信学院,湖南长沙,410082;香港理工大学电子计算学系,香港 2. 湖南大学软件学院,湖南长沙,410082 3. 湖南大学计算机与通信学院,湖南长沙,410082 4. 中国科学院计算技术研究所,北京,100080 |
| 摘 要： | 本文探讨布鲁姆过滤器的代数运算和集合查询的关系,定义布鲁姆过滤器的"并","交","异或","补","差"代数运算,从理论和实验两方面分析布鲁姆过滤器的代数运算和集合代数运算并集,交集,异或集,补集,差集的元素查询关系.理论分析和实验结果表明,布鲁姆过滤器的"并","交"运算能够支持集合并集交集的元素查询,这一结论可以简化利用布鲁姆过滤器进行的系统设计. |
| 关 键 词： | 计算机网络 分布式计算 分布式消息系统 集合元素查询 代数运算 |
| 文章编号： | 0372-2112(2008)05-0869-06 |
| 收稿时间： | 2007-10-22 |
| 修稿时间： | 2007年10月22 |
Algebraic Operations on Bloom Filters |
|
| XIE Kun,ZHANG Da-fang,WEN Ji-gang,XIE Gao-gang,YOU Zhi-Qiang.Algebraic Operations on Bloom Filters[J].Acta Electronica Sinica,2008,36(5):869-874. | |
| Authors: | XIE Kun ZHANG Da-fang WEN Ji-gang XIE Gao-gang YOU Zhi-Qiang |
| Affiliation: | XIE Kun1,2,ZHANG Da-fang3,WEN Ji-gang1,XIE Gao-gang4,YOU Zhi-Qiang3(1.School of Computer , Communication,Hunan University,Changsha,Hunan 410082,China,2.Department of Computing,The Hong Kong Polytechnic University,Hong Kong,3.School of Software,4.Institute of Computing Technology,Chinese Academy of Sciences,Beijing,100080,China) |
| Abstract: | 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 tr... |
| Keywords: | computer networks distributed computing distributed information system set membership query algebraic operations |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ | |
| 点击此处可从《电子学报》浏览原始摘要信息 | |
| 点击此处可从《电子学报》下载全文 | |
