Algebraic Operations on Bloom Filters

XIE Kun; ZHANG Da-fang; WEN Ji-gang; XIE Gao-gang; YOU Zhi-Qiang

您当前的位置：

首页 >

文章列表页 >

Algebraic Operations on Bloom Filters

更新时间：2025-07-16

- Algebraic Operations on Bloom Filters
- Acta Electronica Sinica Vol. 36, Issue 5, Pages: 869-874(2008)
- 作者机构：
  
  1. 湖南大学计算机与通信学院,湖南,长沙,410082
  2. 香港理工大学电子计算学系,香港
  3. 湖南大学软件学院,湖南,长沙,410082
  4. 中国科学院计算技术研究所,北京,100080
  5. 湖南大学计算机与通信学院湖南长沙,410082
  6. 香港理工大学电子计算学系香港
  7. 湖南大学软件学院湖南长沙,410082
  8. 中国科学院计算技术研究所北京,100080
- 作者简介：
- 基金信息：
- DOI：
  CLC： TP393
- Published：2008
- 稿件说明：
移动端阅览
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：

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

Views

972

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Distributed Precomputation for QoS Routing

A Queueing Model and Probabilistic Scheduling for Multi-user Network Applications

A Model of Distributed Sensors' Scheduling and Self-Adaptive Probability Particle Swarm Optimization Algorithm

Related Author

WU Jian-ping

CUI Yong

ZHU Jiang

WU Jian-ping

BI Jun

LI Ken-li

XIAO Zheng

TONG Zhao

Related Institution

Department of Computer Science,Tsinghua University

Department of Computer Science, Tsinghua University

College of Information Science and Engineering Hunan University Changsha Hunan China

College of Mathematics and Computer Science Hunan Normal University Changsha Hunan China

College of Information Science and Engineering, Hunan University

⁰