多路平衡型矩阵Bloom Filter

• 作者: 杨磊 黄建智
• 来源期刊: 湖南大学学报（自然科学版）
• 关键词: 海量数据存储 BloomFilter 拆分BloomFilter 多路平衡型矩阵BloomFilter
• 年，卷（期）: 2018,（2）
• 所属期刊栏目: 计算机科学
• 页码范围: 133-140
• 页数: 8页
• 分类号: TP301.6
• 语种: 中文
• DOI: 10.16339/j.cnki.hdxbzkb.2018.02.17

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	杨磊	湖南大学信息科学与工程学院	29	97	5.0	7.0
2	黄建智	湖南大学信息科学与工程学院	1	1	1.0	1.0