布鲁姆过滤器：高效随机数据结构及应用分析
需积分: 0 127 浏览量
更新于2023-11-23
收藏 939KB PDF 举报
Bloom Filter 是一种空间效率很高的随机数据结构，利用位数组表示一个集合，并能判断一个元素是否属于这个集合。本报告介绍了 Bloom Filter 的基本思想和数据结构设计。在《大数据存储与管理》课程中，我们将深入探讨 Bloom Filter 的背景和意义，并详细讨论其总体设计。 Bloom Filter 的应用能够在大数据存储与管理中发挥重要作用，对于提高查询效率和减少存储空间有着积极的意义。
2
二、选题背景与意义
Bloom filter（布隆过滤器）是 Howard Bloom 在 1970 年提出的二进制向
量 数据结构，具有良好的空间和时间效率，用于检测某元素是否为集合的成
员。
Bloom Filter 是一种空间效率很高的随机数据结构，它利用位数组很简洁地
表示一个集合，并能判断一个元素是否属于这个集合。它是一个判断元素是否存
在集合的快速的概率算法。Bloom Filter 有可能会出现错误判断，但不会漏掉
判断。也就是 Bloom Filter 判断元素不在集合，那肯定不在。如果判断元素存
在集合中，有一定的概率判断错误。因此，Bloom Filter 不适合那些“零错误
的应用场合”。而在能容忍低错误率的应用场合下，Bloom Filter 比其他常见的
算法（如 hash 折半查找）极大节省了空间。
它的优点是空间效率和查询时间都远远超过一般的算法，通过极少的错误换取
了存储空间的极大节省，而缺点是有一定的误识别率和删除困难。尤其当要存储的
信息为多维时，靠简单的多维 bloom filter 的叠加会让 false positive 的概率
大大提升。
通过本课题的研究，分析一个可以减少 false positive 的概率的结构设计。
三、总体设计
3.1 Bloom Filter 基本思想
3.1.1 BloomFilter 原理：
当一 个元 素被 加入 集 合 时 ，通 过 k 个散 列 函 数 将 这 个 元 素 映 像 成一 个
位数 组中 的 k 个点 ，把它们 置 为 1。检 索 时，我 们 只 要 看 看 这 些 点 是 不 是
都是 1 就 （ 大 约 ） 知道 集合 中有 没有 它 了 ,如 果这 些点 有任 何一 个 0，则
被检 元素 一定 不在 ； 如 果 都 是 1， 则 被 检 元 素 很 可 能 在 。
图 3-1 BloomFliter 原理图
如上 图所 示， 我们 定 义 了 一 个 16 位 的 二 进 制 向 量 ， 3 个 hash 函数 ，
这个 3 个函 数 hash 的 结 果 为 0 或者 1， 该结 果存 放的 位置 为 0~15 之
间， 将 hash 的结 果 的 位 置 映 像 到 二 进 制 向量 的 index， 并 保 存 结 果 .
对于 输入 数据 input1， 得 到 的 的 结 果 存 在 于 0，8， 14，结 果 全 部 为
1， 那 么 说 明 input1 可 能 存 在 于 指 定 的 集 合 。
对于 input2， 得 到 的 结 果 存 在 于 0，4， 10，有 一 个 是 0， 那 么 说 明
input2 一 定不 存在 于指 定的 集合 。
剩余16页未读，继续阅读
点击了解资源详情
2022-08-03 上传
奔跑的楠子
- 粉丝: 32
- 资源: 299
我的内容管理
展开
