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

谢 鲲; 张大方; 文吉刚; 谢高岗; 尤志强

您当前的位置：

首页 >

文章列表页 >

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

论文 | 更新时间：2025-07-16

- 布鲁姆过滤器代数运算探讨
- Algebraic Operations on Bloom Filters
- 电子学报 2008年36卷第5期页码：869-874
- 作者机构：
  
  1. 湖南大学计算机与通信学院,湖南,长沙,410082
  2. 香港理工大学电子计算学系,香港
  3. 湖南大学软件学院,湖南,长沙,410082
  4. 中国科学院计算技术研究所,北京,100080
  5. 湖南大学计算机与通信学院湖南长沙,410082
  6. 香港理工大学电子计算学系香港
  7. 湖南大学软件学院湖南长沙,410082
  8. 中国科学院计算技术研究所北京,100080
- 作者简介：
- 基金信息：
  
  国防基础科研"十一五"规划 (No.A1420060162)
- DOI：
  中图分类号： TP393
- 纸质出版：2008
- 稿件说明：
移动端阅览
谢鲲, 张大方, 文吉刚, 等. 布鲁姆过滤器代数运算探讨[J]. 电子学报, 2008,36(5):869-874.

XIE Kun, ZHANG Da-fang, WEN Ji-gang, et al. Algebraic Operations on Bloom Filters[J]. Acta Electronica Sinica, 2008, 36(5): 869-874.
谢鲲, 张大方, 文吉刚, 等. 布鲁姆过滤器代数运算探讨[J]. 电子学报, 2008,36(5):869-874. DOI：

XIE Kun, ZHANG Da-fang, WEN Ji-gang, et al. Algebraic Operations on Bloom Filters[J]. Acta Electronica Sinica, 2008, 36(5): 869-874. DOI：

摘要

本文探讨布鲁姆过滤器的代数运算和集合查询的关系

定义布鲁姆过滤器的"并"

"交"

"异或"

"补"

"差"代数运算

从理论和实验两方面分析布鲁姆过滤器的代数运算和集合代数运算并集

交集

异或集

补集

差集的元素查询关系.理论分析和实验结果表明

布鲁姆过滤器的"并"

"交"运算能够支持集合并集交集的元素查询

这一结论可以简化利用布鲁姆过滤器进行的系统设计.

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 trick to real application.

关键词

Keywords

references

浏览量

972

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

分布式服务质量路由预计算算法

分布式系统中多用户网络应用的概率型调度算法研究

分布式传感器调度模型与自适应概率粒子群优化算法