+高级检索
多路平衡型矩阵Bloom Filter
DOI:
作者:
作者单位:

作者简介:

通讯作者:

基金项目:


M-Balance Matrix Bloom Filter
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
    摘要:

    海量数据的高效表示和查找成为目前存储系统面临的重要挑战.针对存储系统中大规模动态数据集的表示和查找效率问题,提出一种多路平衡型矩阵Bloom Filter结构(M-BMBF)及其插入和查询算法.M-BMBF根据数据集合大小建立一个r×m矩阵型Bloom Filter,设计多个定位哈希函数将该矩阵Bloom Filter分为多组(多路)以实现平衡插入和高效查询操作.为减缓Bloom Filter中比特的消耗速度,使用一种“最长位匹配”填充算法,新元素的插入将从多路备选Bloom Filter中选择新置为1比特个数最少的Bloom Filter中进行.实验结果表明,相较典型拆分Bloom Filter,M-BMBF能在维持算法消耗时间为常量的基础上,有效节省存储空间,降低误判率.

    Abstract:

    Aiming at solving the representation and query efficiency in massive and dynamic dataset on storage system, a Multi-group Balance Matrix Bloom Filter (M-BMBF) and the algorithms on insertion and searching of data element were proposed. M-BMBF initiates a r×m matrix Bloom filter according to the size of dataset, and it introduces multiple located hash functions which can be used to divide the matrix Bloom filter into multi-group to achieve balanced insertion and efficient query operations. In order to slow down the bits consumption rate in Bloom filter when a new element is inserted, a longest-bit match filling algorithm was proposed, which selects a Bloom filter as the destination position for insertion from the candidate Bloom filters according to the rule that fewest bits will be changed due to this insertion operation. Experiment results show that compared with the classical Split Bloom Filter, M-BMBF can efficiently save storage space and decrease the misjudgment rate, while its time consume is constant.

    参考文献
    相似文献
    引证文献
文章指标
  • PDF下载次数:
  • HTML阅读次数:
  • 摘要点击次数:
  • 引用次数:
引用本文

杨磊,黄建智.多路平衡型矩阵Bloom Filter[J].湖南大学学报:自然科学版,2018,45(2):133~140

复制
历史
  • 收稿日期:
  • 最后修改日期:
  • 录用日期:
  • 在线发布日期: 2018-02-26
  • 出版日期:
作者稿件一经被我刊录用,如无特别声明,即视作同意授予我刊论文整体的全部复制传播的权利,包括但不限于复制权、发行权、信息网络传播权、广播权、表演权、翻译权、汇编权、改编权等著作使用权转让给我刊,我刊有权根据工作需要,允许合作的数据库、新媒体平台及其他数字平台进行数字传播和国际传播等。特此声明。
关闭