多路平衡型矩阵Bloom Filter

作     者：杨磊 黄建智 YANG Lei;HUANG Jianzhi

作者机构：湖南大学信息科学与工程学院湖南长沙410082 

基　　金：国家重点研发计划"高性能计算"专项资助项目(2017YFB0202901) 湖南省自然科学基金资助项目(2015JJ2035) 中央高校基本科研业务费资助项目~~ 

出 版 物：《湖南大学学报（自然科学版）》 (Journal of Hunan University:Natural Sciences)

年 卷 期：2018年第45卷第2期

页      码：133-140页

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

主 题 词：海量数据存储 Bloom Filter 拆分Bloom Filter 多路平衡型矩阵Bloom Filter 

学科分类：08[工学] 081202[081202] 0812[工学-测绘类] 

核心收录：

D　O　I：10.16339/j.cnki.hdxbzkb.2018.02.17

馆 藏 号：203283354...