全站搜索
分布式环境下改进的Bloom Filter过滤技术
作者:管理员    发布于:2015-11-07 14:38:32    文字:【】【】【

  范俊梅王斌王国仁郭鹏(东北大学信息科学与工程学院,辽宁沈阳110004)的DivisionBloomFilter(DBF)技术,DBF技术采用了一组相互独立的哈希函数来计算数据对象的地址序列,然后使用这组地址序列将数据对象存储到一个分片的位向量中,所以DBF技术可以有效减少数据对象的存储空间。实验证明,DBF不仅可以解决BloomFilter在分布式环境下的动态更新问题,还可以有效减少BloomFilter的错误率以及改善其稳定性。后还使用数据压缩技术进一步减少在P2P系统中使用DBF技术的结点间通信代价。

  随着Internet的兴起,分布式数据管理的研究成为了一个热点,当然这和它所具有的巨大潜力也是分不开的。P2P技术则是实现分布式数据管理的一个有效的手段,P2P系统中的数据搜索模式可以有效减少网络阻塞的发生概率。在P2P系统中,每个结点都维护一个其内部资源的局部索引,当用户向其发出搜索请求的时候,首先自己处理该请求,然后再向目标结点发送搜索请求。目前用户的搜索大多是多关键字搜索/17,在一个由服务器Sa和服务器Sb组成的简单的网络中,用户的搜索请求为3Ka,Kb〉,服务器Sa中存储了一个文档集合A对应关键字Ka,服务器Sb存储了一个文档集合B对应关键字Kb,AHB就是所有包括关键字Ka和Kb的文档集合。Sa发送其文档ID集合A给Sb,Sb计算AHB然后将结果发送给用户。因为AHB远远小于A,很多A中的元素在Sb中被丢弃了,而造成网络带宽的浪费。使用BloomFilter技术可以减少和限制网络基金项:国家自然科学基金资助项目(60473074);教育部高等学校青年教师教学科研奖励计划资助项目。T994-2U1JChina华中科技大学学报(自然科学版)带宽浪费。

  1相关工作其应用很广泛,如Webcache和XML文档路径查询。

  一个使用了k个哈希函数的m位长的BloomFilter中装入n个兀素后位向量中某一位仍然为0的概率假通过率而式(7)是一个单调递减函数,所以位向量的个数s越大,分片BloomFilter的假通过率p越小,所以通过分片可以减小BloomFilter的假通过率。但是考虑到在分析分片BloomFilter的时候是假设"个数据对象是均匀分布在s个位向量中的,而实际中选取哈希函数时很难做到这一点。选取的s越大,让元素均匀分布在s个位向量中的难度就越大,如果分布不均匀就有可能在某个位向量中装入的元素数目超出了位向量的承受能力,而让分片BloomFilter的局部过滤能力即位向量的过滤能力下降,从而总体过滤能力下降。所以在实际应用中,应该根据数据集合的大小来选择适当的分片数s. BloomFilter算法表示动态数据集合的能力很差,计数型BloomFilter141可以弥补其不能删除元素的缺点,但是在BloomFilter中增加元素也不是无限制的。BloomFilter是一个静态的数据结构,其参数是在建立BloomFilter的时候就固定了的,如果不断的插入元素,BloomFflter的填充率就会不断增大,而填充率越大,假通过率越大,其极限情况就是填充率为100 时,其过滤能力就为0.但是想根据数据集合动态调整BloomFi-ter就要重建BloomFilter,需要将所有的元素重新运算,代价是巨大的。尤其在P2P环境下,一旦要改变BloomFilter的长度和哈希函数的个数,每个结点都得重新计算自己位向量,还得在结点间通知这种改变,这几乎是不可能的。

  动态增加的问题。分片BloomFilter局部的位向量是固定的,但是全局的位向量的个数是可变的。这就具备了动态调整的条件。可以预测目前的分片BloomFilter的大承受能力,当所装入的元素的个数超过其大承受能力的时候,就调整分片BloomFilter的大小。局部的位向量是不需要改变,所要调整的就是增加位向量的个数,即调整哈希函数h0就可以使得分片BloomFilter的装填能力增加,从而解决数据集合动态增加的问题。

  3性能测试在实际测试中,BloomFilter和分片BloomHlter使用了同样的数据对象集合和测试数据对象集合,在数据集合文件中存放了包含1000个数据对象的集合A,测试数据集合文件中存放了1000个待查询数据对象的集合B.为了测试的准确,这些数据对象均是随机产生的。

  ~从四个方面比较了BloomFilter(曲线1和分片BloomFilter(曲线2)的性能:a数据对象集合与假通过率即错误率("~P见),h存储空间与错误率(m~P见),e存储空间与时间(m~t见);d数据对象集合与时间(n~t见)。

  数据装填个数n和错误率P的关系1―BloomFiler,2―分片BloomFiler(下同)存储空间m和错误率/>的关系以上测得的实验结果表明:a在同样的存储空间和装填个数下,使用相似的哈希函数,使用分片BloomFilter的错误率小于使用BloomFflter的错误率。

  华中科技大学学报(自然科学版)存储空间m和时间t的关系装填个数n和时间t的关系b.在同样的存储空间和装填个数下,使用相似的哈希函数,分片BloomFilter的运算时间略多于BloomFilter的运算时间。

  c.分片BloomFilter算法的错误率稳定性和时间稳定性都高于BloomFilter算法。

  4压缩技术数据集合表示空间,而且可以降低其小假通过率。在分片BloomFilter的局部也是个BloomFilter,所以这一结论在分片BloomFilter中同样适用。改变哈希函数的个数k值,改变在位向量中0和1出现的概率,而达到二次压缩的目的。因为分片BloomFilter是可分的,在压缩的时候可以分片压缩,同样在解压的时候,只解压所需的位向量,从而减少了压缩和解压的计算量。

  位当成一个字符来处理,不够8位的补0,然后采用LZ77算法对其进行压缩。LZ77算法在某种意义上又可以称为“滑动窗口压缩”,这是由于该算法将一个虚拟的,可以跟随压缩进程滑动的窗口作为术语字典,要压缩的字符串如果在该窗口中出现,则输出其出现位置,长度以及后继字符的三元组。解压时,随着输入三元组,在窗口中找到对应的字符串再配上后继字符输出就可以还原出原始的位向量。

访问统计
51客服