多路平衡型矩阵Bloom Filter |
| |
引用本文: | 杨磊,黄建智.多路平衡型矩阵Bloom Filter[J].湖南大学学报(自然科学版),2018,45(2):133-140. |
| |
作者姓名: | 杨磊 黄建智 |
| |
作者单位: | (湖南大学 信息科学与工程学院,湖南 长沙410082) |
| |
摘 要: | 海量数据的高效表示和查找成为目前存储系统面临的重要挑战.针对存储系统中大规模动态数据集的表示和查找效率问题,提出一种多路平衡型矩阵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 |
M-Balance Matrix Bloom Filter |
| |
Institution: | (College of Information Science and Engineering, Hunan University, Changsha410082, China) |
| |
Abstract: | |
| |
Keywords: | mass data storage Bloom Filter split Bloom Filter M-balance matrix Bloom Filter |
本文献已被 CNKI 等数据库收录! |
| 点击此处可从《湖南大学学报(自然科学版)》浏览原始摘要信息 |
| 点击此处可从《湖南大学学报(自然科学版)》下载免费的PDF全文 |