Bloofi: A Hierarchical Bloom Filter Index with Applications_~shallot~的博客-程序员宝宝

一、Bloom-Filter简介

Bloom-Filter，即布隆过滤器，1970年由Bloom中提出。它实际上是由一个很长的二进制向量和一系列随机映射函数组成，布隆过滤器可以用于检索一个元素是否在一个集合中。

BLoomFilter example
优点：
1.时空优势
1）采用hash函数判断一个元素是否存在，快速！
2）用一个二进制数组来表示元素是否存在，不存放真实数据，大大节省空间。
缺点：
1.误算率（False Positive）
2.不能直接删除元素
Bloom Filter 用例
Google Chrome浏览器使用了布隆过滤器加速安全浏览服务
垃圾邮件过滤
P2P网络中资源查找

二、思考？

假设有在某分布式环境下，N个用于存储数据的分支节点分布在不同的物理点。
问题一：查询一个元素是存在？
问题二：如果存在，那么又具体存放在哪个分支节点？

解决方案一：每个分支节点维护一个Bloom Filter，该分支节点上存储的数据都可以通过这个BloomFilter查找，但是如果不在本节点时，则需要查找其他的节点，这样就造成了大量的节点之间的通信，且需要挨个在每个分支节点中查找。

解决方案二：每个分支节点维护一个Bloom Filter，并将自己的Bloom Filter 分享给一个中心节点，这个中心节点可以与所有的分支节点通信。
1.构建一个类似于B+ tree的树形结构，叶子节点是各个分支节点BloomFilter.

2.多个分支节点BloomFilter按位进行OR运算得到一个中间Node,具体多少个分支节点一起进行OR操作？或者说每个中间Node有多少个分支？这里我们定义一个d,类似于二叉树的分支只能有2个分支，我们这个结构有d~2d个分支。（下面的实例我们令d=2）

3.中间节点再依次按照2中的规则向上进行OR操作，最终的到一个根结点。同样是一个BloomFilter，这里保存了所有分支节点BloomFilter进行OR操作的结果。
如下图所示：
Bloofi树形索引结构
我们把这样一个结构叫做Bloofi（Bloom Filter Index），也就是给各个分支节点上的Bloofi加上索引结构，并且构建一个类似于B+tree的平衡树形结构，且满足上面三个条件。

三、Bloofi增删改查

1.查询操作

查询一个hash值为4 的元素是否在集合中，并且找到具体地理位置。
1）查找根结点Id:9中对应第5位（BloomFilter下标从0开始）是否为1，如果是则继续查询左右子树Id:7he Id:8，否则停止。
2)查找左右子树，发现Id:7对应位上为0，对应Id:7下面的子树都不许要查找，而Id:8中对应第5位为1，则继续往下查找。
3）找到对应的元素，存在于Id:5中

2.插入操作

插入操作涉及到三个问题：
1）这里我们所说的插入并不是插入一个元素，而是插入一个新的BloomFilter
2）尽量将两个相似度最高的BloomFilter 放在同一子树下面，一提高查询速度，减少查询次数。（计算BloomFilter 我们可以采用Hamming distance，直接将两个BloomFilter进行XOR ）
3）前面我们规定这种树形结构的非叶子节点的分支数为[d,2d],所以当某个节点的所有分支数大于这个数时，则需要生成一个新的中间节点，并将要插入的新节点作为该中间节点的分支。
4）个分支节点从新进行OR操作。
实例：（插入的BloomFilter为00100100）
insert

这里在计算新插入的BloomFilter与Id:7和Id:8相似度时，发现相似度都为4，这个时候我们采用一种默认的方式，即从左边开始。

3.删除操作

可能出现的问题：
1）下溢。前面我们规定，每个非叶子节点的分支数不得少于d。所以当删除一个BloomFilter时，可能导致不满足这个条件，这个时候就涉及到其他分支节点的分裂问题。
2）删除后个分支再进行OR操作

实例（删除Id:5）
Delete

4.更新操作

1）这里的更新，指的是对单个BloomFilter的更新，即对具体的元素的更新。
2）更新后依然要进行OR操作

实例（将Id:6更新为00000011，即插入一个元素）
Update

5.时空复杂度分析

1）时间复杂度：Search、Delete、Insert的时间复杂度都为这里写图片描述实际上Delete和Insert都是一个Search的过程。
Update的时间复杂度为：
2）空间复杂度：比单独存储各个BloomFilter消耗的空间要多些，这主要是因为需要生成一些中间节点和一个根节点，但是对于节省通信开销来说，这些都是值得的。

本文链接：https://blog.csdn.net/dylanzr/article/details/45620523

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

mysql中 s命令_MySql常用命令总结_善缘斋的博客-程序员宝宝

1:使用SHOW语句找出在服务器上当前存在什么数据库：mysql> SHOW DATABASES;2:2、创建一个数据库MYSQLDATAmysql> CREATE DATABASE MYSQLDATA;3:选择你所创建的数据库mysql> USE MYSQLDATA; (按回车键出现Database changed 时说明操作成功！)4:查看现在的数据库中存在什么表mysql&...

Imagic应用_shark0001的博客-程序员宝宝

这个宝贝真强大，今天用到了其两条命令，一个是拆分，一个是合并：拆分：convert -crop 64x64 -geometry 64x64 paotao4-hd.png按64x64顺序切图，单个图片的大小也是64x64，即把每块单独存放，合并：montage -geometr

jersey实现web service接口+客户端调用_凌晨1点21分的博客-程序员宝宝

jersey实现web service接口+客户端调用jersey百度百科： Jersey是一个RESTFUL请求服务JAVA框架，与常规的JAVA编程使用的struts框架类似，它主要用于处理业务逻辑层。与Struts类似，它同样可以和hibernate,spring框架整合。由于Struts2+hibernate+spring整合在市场的占有率太高，所以很少一部分人

Activiti 基础概念笔记_衣舞晨风的博客-程序员宝宝

1、ProcessInstance 与ProcessDefinition流程实例（ProcessInstance）和流程定义（ProcessDefinition）的关系，与类和实例对象的关系有点像，ProcessDefinition是整个流程步骤的说明而ProcessInstance就是指流程定义从开始到结束的那个最大的执行路线。2、ExecutionExecution是按照ProcessDefin

“Xilinx ZYNQ+TCP通信+Python上位机”实现实时视频传输系统_tcp_snd_buf_求学者羽光的博客-程序员宝宝

本文是笔者的公众号 IC设计者笔记文章的节选。很多优质原创内容都会第一时间发布在公众号，欢迎关注公众号，一起交流学习。笔者在CSDN的第一篇万字长文，请多多支持。前言前段时间接到老板匆忙打电话，大概内容是：之前师兄流片的CMOS图像传感器马上要提交结题报告，需要帮忙用ZYNQ系列FPGA将图像传感器的数据实时传输到PC，并且通过上位机拍照。由于时间紧急，要求两三天内完成。当时自己心想：“FPGA开发+ARM程序编写+PC端上位机开发” 两三天完成，还包括调试。。。Are you kiding

UVa 11462 年龄排序 (计数排序及IO优化)_PK0071的博客-程序员宝宝

题意：给定若干个居民的年龄（都是1-100之间的整数），把它们按照从i型奥到大的顺序输出。输入第一行为整数n（0思路：数据太大，内存限制太紧，连把数据全读进内存都不行，所以什么快排之类的排序报废了，但是注意到这里整数范围很小，可以用计数排序。#include#includeint main(){ int n,x,c[101],i,j; while(scanf("%d",&

随便推点

Unity图集的使创建以及简单的使用（下）_波波斯维奇的博客-程序员宝宝

前言：在上次的博客中写了怎么创建图集，今天在这篇博客中记录下图集是怎么调用的。（1）、在场景中创建一个UGUI的Image组件，如图所示：（2）、创建一个调用图集的脚本，代码如下：using System.Collections;using System.Collections.Generic;using UnityEditor;using UnityEngine;using Un...

基于android的家教一点通（家教帮）app_qq_1262330535的博客-程序员宝宝

许多大学生都利用做兼职来充实课外生活或者补贴家用，还有一些老师利用课余时间或者假期时间做家教来赚一些外快，所以家教行业当下很流行，而许多家长在寻找家教时往往像大海捞针而且信息渠道不足，而许多大学生或者老师想要做家教时也是张贴各种广告，诸多不方便之处，造成学员与家教之间的交流不是很及时，因此便有了设计家教一点通这款软件的想法，为学员和教员之间搭建一个交流的平台。通过这款软件，家长可以了解离自己最近的家教信息，可以对各个老师的信息进行比较，从而选择最适合自己孩子情况的家教。而各个想做家教的老师也可以发布自己的