多路平衡型矩阵Bloom Filter

杨磊 黄建智

摘 要：海量数据的高效表示和查找成为目前存储系统面临的重要挑战.针对存储系统中大规模动态数据集的表示和查找效率问题，提出一种多路平衡型矩阵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

中图分类号：TP301.6 文献标志码：A

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.

Key words：mass data storage； Bloom Filter；split Bloom Filter ；M-balance matrix Bloom Filter

隨着企业和个人数据的迅速增长，对于数据中心的存储能力及管理要求也越来越高，如今，在计算机应用中的许多基本问题都涉及到信息的表示和查询.检测一个元素是否属于某个集合是最困难的任务之一，尤其是当要被处理的数据量很大时.

Bloom Filter[1]是一种能够表示集合并且支持集合快速查询的简单数据结构，它能够在容忍很小误判的情况下极大地节省查询集合的存储空间.Bloom Filter已经广泛应用于各个领域，如数据库应用[2] 、P2P网络节点交互[3-5] 、资源路由[6]等.此外，Bloom Filter在利用较少的空间表示集合方面还有很大的应用潜力.

近些年来，针对不同的应用需求，对Bloom Filter做出了许多实质性的改进.计数Bloom Filter解决了集合中元素的删除 [7] 以及多维集合元素的高效表示和查询问题[8]；……