布鲁姆过滤器代数运算探讨

被引:8
作者
谢鲲 [1 ]
张大方 [2 ]
文吉刚 [1 ]
谢高岗 [3 ]
尤志强 [2 ]
机构
[1] 湖南大学计算机与通信学院
[2] 湖南大学软件学院
[3] 中国科学院计算技术研究所
关键词
计算机网络; 分布式计算; 分布式消息系统; 集合元素查询; 代数运算;
D O I
暂无
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
本文探讨布鲁姆过滤器的代数运算和集合查询的关系,定义布鲁姆过滤器的"并","交","异或","补","差"代数运算,从理论和实验两方面分析布鲁姆过滤器的代数运算和集合代数运算并集,交集,异或集,补集,差集的元素查询关系.理论分析和实验结果表明,布鲁姆过滤器的"并","交"运算能够支持集合并集交集的元素查询,这一结论可以简化利用布鲁姆过滤器进行的系统设计.
引用
收藏
页码:869 / 874
页数:6
相关论文
共 5 条
  • [1] 分档布鲁姆过滤器的查询算法
    谢鲲
    闵应骅
    张大方
    谢高岗
    文吉刚
    [J]. 计算机学报, 2007, (04) : 597 - 607
  • [2] 基于轨迹标签的无结构P2P副本一致性维护算法
    谢鲲
    张大方
    谢高岗
    文吉刚
    [J]. 软件学报, 2007, (01) : 105 - 116
  • [3] Flavio Bonomi,Michael Mitzenmacher,Rina Panigrah,Sushil Singh,George Varghese.Beyond bloom filters[J].ACM SIGCOMM Computer Communication Review,2006
  • [4] Michael Mitzenmacher.Compressed bloom filters[J].IEEE/ACM Transactions on Networking (TON),2002
  • [5] Burton H. Bloom.Space/time trade-offs in hash coding with allowable errors[J].Communications of the ACM,1970