多路平衡型矩阵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]；压缩Bloom Filter[9]减少了Bloom Filter在传输中所消耗的带宽；光谱Bloom Filter[10]、拆分Bloom Filter[11]以及动态Bloom Filter[12]解决了集合中元素增长的问题；SKIP Bloom Filter[13]解决了数据流的动态特性问题；Ternary Bloom Filter在计数Bloom Filter的基础上降低了误判率[14].

前述方法多面向网络应用，侧重于增强集合的可扩展性、控制误判率、控制带宽以及元素删除，而缺乏对检索存储系统中大容量可变数据集时高查询性能和减少内存开销等需求的考虑.对于大数据存储系统而言，为了能够更快地检索数据，减少系统开销，通常选择将索引表置于内存甚至cache中，虽然Bloom Filter由于其所占空间非常小而可以常驻内存，从而加快集合中数据的检索速度，但是随着数据量的增加，所需Bloom Filter个数也增加，最终会导致内存达到瓶颈.

针对以上问题，本文提出了多路平衡型矩阵Bloom Filter算法（M-BMBF）.所谓平衡，即能够均匀地使用每个Bloom Filter的存储空间，为了达到平衡，M-BMBF改变了Bloom Filter的判满条件，由原来的插入元素数量达到上限值时为满改为Bloom Filter的使用空间达到50%时即为满.当插入数据时，M-BMBF引入多路（个）定位哈希函数将矩阵Bloom Filter分为多组，同时采用“最长位匹配”填充算法快速定位元素应该具体插入的Bloom Filter，通过降低Bloom Filter空间的使用速度来提高Bloom Filter的利用率，从而可以存储更多的数据，提高数据的检索速度.

本文第一部分介绍相关工作，第二部分描述算法设计细节，第三部分给出实验评估结果，最后一部分进行总结.

1 相关工作

Bloom Filter是由Burton Bloom于1970年基于数据库应用程序而提出的，Bloom Filter的基本原理是通过一个长度为m的位向量来表示元素集合S={x1，x2，…，xn}，其中集合S包含有n个元素，向量中的每一位初始状态都为0，对于集合中的每一个元素，都使用k个哈希函数把它映射到向量中，将哈希值相应的位置置1，其他的位保持0不变.当要查询一个元素是否属于某个集合时，分别使用k个哈希函数对该元素进行计算，检查每一个哈希值在向量中对应的位置是否为1，只要某个哈希值在向量中的位置为0，那么就可以判定该元素不属于集合，否则以一定的误判率认为该元素属于集合.Bloom Filter的算法结构如图1所示.

Bloom Filter由于其简洁高效，最近在网络和存储领域上受到广泛关注[10，15-17]，使用Bloom Filter时主要考虑误判率、内存大小、需要管理的集合数目等性能参数.

虽然Bloom Filter是一种高效的检索数据结构，但它还不能较好地解决诸如集合元素的动态增长和改变等问题.随着集合中元素的增加，单个Bloom Filter的误判率会增大，最终将导致Bloom Filter失效.近年来，针对动态集合的问题，对Bloom Filter作出了一些实质的改进，产生了拆分Bloom Filter算法[10]和动态Bloom Filter算法[11]以及基于这两种算法的改进算法.拆分Bloom Filter和动态Bloom Filter的区别在于 ：拆分Bloom Filter的基本思想是使用r个位向量来表示数据集合，当集合中的元素个数增大到一定程度，影响到最初设计的误判率指标时，重新生成一个r×m的二维位向量，如果增加的元素并未达到预先给定的集合个数最大值，则随机选择一个位向量表示该元素.而动态Bloom Filter是根据元素的增长而动态地增加Bloom Filter，预先设计好Bloom Filter所能存储的元素个数，初始化Bloom Filter个数为1，动态Bloom Filter只能在最后一个Bloom Filter进行元素的插入（前提是其未满，否则动态增加Bloom Filter）.虽然拆分Bloom Filter和动态Bloom Filter解决了元素动态增长的问题，但它们并没有有效解决单个Bloom Filter空间利用率的问题.同时，这些算法又带来了新的问题，在元素的查询性能方面，它们与Bloom Filter时间复杂度为常数相违背.标准Bloom Filter的时间复杂度为O（k），而拆分Bloom Filter和动态Bloom Filter由于在插入和查询数据时需要顺序查找每个Bloom Filter，所以其时间复杂度与Bloom Filter个数有关，即O（kr），其中r为Bloom Filter个数.当Bloom Filter的数量很大时，查询性能较差.矩阵Bloom Filter[15]基于拆分Bloom Filter的查詢性能作了改进，通过一个特殊的哈希函数快速定位到某个Bloom Filter，并在这个Bloom Filter中对元素进行查找或插入操作.Yi等提出了Par-BF[16]，通过并行处理的方式快速匹配元素.魏建生等人提出了动态布隆过滤器阵列（DBA）[17]，DBA由可创建的动态布隆过滤器组构成，以按需调整索引容量，通过并行计算的方式处理集合中的元素，在提高元素查询性能的同时也提高了内存空间效率.这三种算法虽然使用不同的方法提高了元素查询效率，但是它们并未改善Bloom Filter的空间利用率.为了解决Bloom Filter空间利用率的问题，王勇等人[18]提出了支持属性删减的布鲁姆过滤器矩阵多维元素查询算法CBFM，具有较高的内存利用率；孙智超等人针对动态Bloom Filter提出了二路平衡动态Bloom Filter （2BDBF）[19]，该算法不再使用插入元素计数作为Bloom Filter的判满条件，而是引进了饱和度的概念，使用饱和度作为Bloom Filter的判满条件，并且通过向量组的方式动态增长Bloom Filter，选择向量组中空间使用最少的Bloom Filter作为元素插入位置以达到插入更多元素的效果.虽然2BDBF能够表示更多的元素，但其查询性能并未得到改善.

2 多路平衡型矩阵Bloom Filter

2.1 算法设计思想

如前文所述，本文工作主要基于使用Bloom Filter表示动态数据集时的插入查询效率和空间使用效率展开，设计了一种多路平衡型矩阵Bloom Filter过滤器（M-BMBF），其算法设计结构如图2所示.

为解决动态数据集的插入和查询效率问题，M-BMBF引入了多个定位哈希函数概念.M-BMBF的基本设计思想是将动态集合表示成一个r×m的位矩阵.该矩阵的行为r，表示有r个Bloom Filter；列为m，表示每个Bloom Filter的向量长度为m比特.在这里行为r是一个常量，必须按照对集合尺寸的最大值估计而预先确定.为了提高元素的查找性能，本文设计s个定位哈希函数h0，h1，…，hs-1，这s个哈希函数是经过特殊定义的并且不同于其他k个独立的哈希函数.为了降低s个哈希函数出现冲突的概率，将r个Bloom Filter划分成s组，其中每组有r/s个Bloom Filter，而每个定位哈希函数映射一组Bloom Filter.在元素添加之前，需要确定该元素应该被添加在哪一个Bloom Filter中，这时就可以使用这s个哈希函数进行定位计算，选出该元素在每一组中所对应的Bloom Filter作为候选插入位置.

由推论1，我们可以将Bloom Filter在最低误判率下的最大插入元素个数转化为其位空间的使用状况，据此我们使用了“最长位匹配”填充算法以提高Bloom Filter的空间利用效率.“最长位匹配”填充算法的主要设计思想是如果在插入元素时，能把元素的哈希函数值尽量多地映射到Bloom Filter向量中已为1的位置上，则可能在保持p不变的前提下插入比n更多的元素.

具体来说，插入时，利用k个哈希函数计算元素x的k个哈希函数值后，将它们与候选Bloom Filter的对应地址位置进行比较，如果发现有其中一个Bloom Filter所对应的k个哈希函数的地址都为1，则认为该元素已存在，不需要作插入处理；否则选择这s个候选Bloom Filter中对应地址值为1的位置与x的k个哈希地址重合最多的作为其插入位置.在M-BMBF中，每个定位哈希函数的哈希范围为{0，1，2，…，r/s}，而其他k个哈希函数的范围为{0，1，…，m-1}.因此，在构建M-BMBF之前，哈希函数的个数k并不是真正用在算法中的个数，实际上，将要使用k+s个哈希函数.假设定位哈希函数是完美随机的，这样每一组中所能容纳的元素个数应该是相同的，为n/r.M-BMBF的算法结构如图2所示.

2.2 算法实现

如算法1所示，为了表示和查找动态集合中元素，首先要根据对集合尺寸最大值的估计而预先建立好一个r×m的矩阵Bloom Filter，并将所有的位初始化为0（参见伪代码中的第1行）.定义s个定位哈希函数，然后根据上一节所描述的算法思想，将r个Bloom Filter划分成s组，每组有r/s个Bloom Filter，每个定位哈希函数通过对第一组哈希函数的映射再偏移的方式对应映射到相应的组Bloom Filter中（参见伪代码中的第5行）.

对于元素的插入过程，首先计算s个哈希函数，找出每一组中具体映射到的Bloom Filter作为备选插入位置，然后对该元素进行k个相互独立的哈希函数计算（参见伪代码中的第6行），将该元素的k个哈希函数地址与备选的Bloom Filter的对应地址位置进行比较，找出k个哈希函数的计算中与向量中已经为1的位置重合最多的Bloom Filter，将该元素插入到此Bloom Filter中（参见伪代码8-11行），并将该Bloom Filter的k个哈希函数映射中剩余的未被置1的位置置为1即可（参见伪代码12-13行）.

当要查询一个元素时，其过程如算法2所示.

2.3 性能分析

2.3.1 时间复杂度（元素检索时间）

当要查询一个元素是否属于某个集合时，拆分Bloom Filter和2BDBF是对每个Bloom Filter按顺序依次查询，直至查到为止，而对每一个Bloom Filter的查询时间为O（k），其中k为哈希函数个数，那么拆分Bloom Filter和2BDBF最坏情况下的平均查询时间为O（kr）.本文算法（如算法2）首先用s个定位哈希函数定位到相对应的Bloom Filter组中的某一个Bloom Filter，其时间复杂度为O（s），然后在这s个Bloom Filter中进行k个哈希函数的映射，其时间复杂度为O（k），因此，本文算法总的查询时间复杂度为O（ks）.由于s一般远小于r，本文算法能够有效解决查询效率的问题.

2.3.2 误判率分析

就Bloom Filter而言，在查询某个元素时，如果该元素本不属于动态集合，但在查询过程中却返回true，便發生误判.由文献[10]可知，拆分Bloom Filter的误判率为：

而对于本文所提算法，当0≤d≤s-1，假设第d个定位哈希函数对应的Bloom Filter发生误判的概率为fd，那么在算法的所有定位行中都不发生误判的概率为（1-fd）s.因此，至少有一个Bloom Filter发生误判的概率为1-（1-fd）s，故可得M-BMBF的误判率为：

相较拆分Bloom Filter，M-BMBF的误判率与定位哈希函数个数s有关，在插入元素相同的情况下，由于s≤r，故FM-BMBF≤F.

2.3.3 空间性能

Bloom Filter本身是一种具有高效空间表现的数据结构，它利用位数组很简洁地表示一个集合，相比B树和哈希表等其他与数据大小相关的数据结构而言，所占存储空间非常小，故可以常驻内存.本文在多个候选Bloom Filter中选择元素插入位置时采用“最长位匹配”填充算法，在Bloom Filter的位空间使用率达到50%之前可以插入更多的元素，从而节省Bloom Filter的存储空间.同时，从公式（1）和公式（2）的分析可知，在变量参数m、k和r相同时，如果误判率也控制在相等的情况下，由于s≤r，故M-BMBF插入的元素多于拆分Bloom Filter，从而可以达到节省空间的效果.

3 实验结果与分析

如前文所述，拆分Bloom Filter算法为动态经典算法，2BDBF与本文算法部分思路相近，下面通过实验对比M-BMBF算法、2BDBF算法以及拆分Bloom Filter三种算法性能.本实验各算法使用Java语言编写，在eclipse的编译工具下编译运行，使用的运行环境是Intel（R） Core（TM） Duo CPU，2.00 GB内存和32位的Windows7操作系统.为了进行实验测试，搜集30万个文本文件，并对这些文件进行去重处理，取出其中的20万个文件作为数据集进行实验.在整个实验过程中Bloom Filter的长度m和哈希函数的个数k是固定的，其中m=131 072，k=10，由于插入元素个数n和Bloom Filter个数r以及定位哈希函数个数s是用户可以自定义的三个参数，本文首先充分利用计算机多核CPU的计算资源，并行执行s个定位哈希函数的计算并通过实验比较和分析了三种算法在元素插入个数，算法消耗时间以及误判率三个典型指标上的性能.

本文首先测试了取不同定位哈希函数个数s时对M-BMBF的性能影响，主要从三个方面进行分析.如表1所示，在并行执行多个定位哈希函数的计算时，当定位哈希函数s发生变化，对插入元素个数以及算法的消耗时间并没有明显影响.之所以对算法消耗时间没有产生影响，是因为，在多核环境下，只要CPU的核数足以支撑每个定位哈希函数的独立计算，那么元素的多个定位哈希函数计算就可以并行执行.从表中我们还可以知道，当定位哈希函数的个数增加时，误判率也会随着增加，这是因为随着定位哈希函数的增加，元素的查找范围也会增大，这就会导致误判的概率增大.综合考虑，本文后续实验均取s=2.

为了进一步验证M-BMBF算法的其它性能，取定位哈希函数个数固定为s=2，在整个实验过程中分别改变元素插入个数n和Bloom Filter个数r，在相同的条件下与拆分Bloom Filter、2BDBF作比较，分析三种算法的元素插入数量、算法消耗时间以及误判率如下.

图3给出了三种算法在存储空间相同的情况下分别取不同的Bloom Filter个数时所能插入的元素个数情况.由图可知，随着Bloom Filter个数r的增加，当Bloom Filter的空间使用达到饱和度时，拆分Bloom Filter、2BDBF和M-BMBF的元素插入个数均呈稳定增长.从图中同时可以看出，相较拆分Bloom Filter和 2BDBF，由于M-BMBF算法每次都选择新置为1的个数增加最少的Bloom Filter作为元素的插入位置，减缓了达到饱和度的速度，因此在Bloom Filter個数相同的情况下，M-BMBF能够插入的元素更多，这种增加趋势在Bloom Filter越多时则越显著.

图4、图5给出了分别改变Bloom Filter个数和元素插入个数时三种算法的消耗时间情况.图4为取n=10 000时不同 Bloom Filter个数所带来的算法消耗时间结果.由图可知，当Bloom Filter个数较少时，执行M-BMBF算法所消耗的时间比拆分Bloom Filter和2BDBF多，这是由于当要查询一个元素时，M-BMBF需要计算2个额外的哈希函数，随着Bloom Filter个数r的增加，M-BMBF算法所消耗的时间仍然趋于稳定，而拆分Bloom Filter和2BDBF所消耗的时间却随之增加并超过M-BMBF，而且这种趋势会随着Bloom Filter个数的增多越来越大.这是因为拆分Bloom Filter和2BDBF的元素查找过程是逐个Bloom Filter顺序查找，而采用定位哈希函数的M-BMBF却只需要映射到相对应的2个Bloom Filter，并对这两个Bloom Filter进行查找即可.图5为固定取Bloom Filter个数r=8时三种算法随着插入元素个数增加时的算法消耗时间结果.在Bloom Filter大小m和哈希函数个数k固定的情况下，随着集合元素个数的增加，算法消耗的时间也逐渐增多，使用拆分Bloom Filter算法所消耗的时间与2BDBF一致，比M-BMBF算法所消耗的时间多，并且趋势越来越大.这是因为查询一个元素时，使用M-BMBF的时间复杂度为O（2 k），而使用拆分Bloom Filter和2BDBF时最坏情况下的时间复杂度为O（kr），并且随着集合中元素个数的增加，前两种算法与本文所提算法之间的时间消耗差必然也会越来越大.

综合图4和图5的结果和分析可知，M-BMBF的算法消耗时间优于拆分Bloom Filter和2BDBF的算法消耗时间.

误判率是Bloom Filter的一个重要衡量指标，图6给出了取Bloom Filter个数r为8时（2BDBF的组基为8）随着插入元素的增加使用三种算法时误判率的变化情况.如图6所示，随着插入元素的增加，三种算法的误判率均随之增加，但M-BMBF的误判率在三种算法中是最小的，而拆分Bloom Filter是最大的，这是因为将三种算法的误判率控制在相同的情况下，使用M-BMBF和2BDBF算法能够插入更多的元素，反过来说，当插入元素相同的情况下，M-BMBF和2BDBF的误判率低于拆分Bloom Filter的误判率.同时，M-BMBF缩小了元素的查找范围，故M-BMBF的误判率低于2BDBF.

4 结 论

本文改变了传统Bloom Filter的判满条件，由原来的统计插入元素个数改变为统计Bloom Filter中已置1的位置是否达到饱和（即比例占50%），从而能够使判满条件更加适应过滤器长度的变化.本文提出的M-BMBF算法在改变Bloom Filter的判满条件的同时利用多个定位哈希函数进行集合元素的插入和查找操作.为了减少哈希映射的冲突，将Bloom Filter进行分组，每个定位哈希函数映射到一组Bloom Filter.理论分析和实验结果表明，在存储空间有限的情况下，M-BMBF既能够减缓空间的利用率，又能够节省算法的消耗时间，同时能够保持较低的误判率.随着存储元素的不断增加，当M-BMBF设定空间无法满足元素的表示时，需要动态地增加Bloom Filter，如果动态地增加一个M-BMBF，当需要表示的元素数量很少时，会较大地浪费M-BMBF的存储空间，如果在原有的M-BMBF基础上增加一组Bloom Filter，为保证负载均衡，需要重新计算s，从而增加了计算的时间复杂性，因此，如何动态增加M-BMBF的存储空间是下一步需要研究的问题.M-BMBF的设计同时可以保证在并行环境中的高效运行，由于高效的检索技术对于大数据环境下的重复数据删除是必不可少的，故接下来的工作是将所提算法应用于典型集群文件系统中以实现重复数据检测.

参考文献

[1] BLOOM B H. Space/time trade-offs in hash coding with allowable errors[J]. Communication of the ACM， 1970，13（7）：422-426.

[2] MULLIN J K. Optional semijoins for distributed data system[J].IEEE Trans Software Eng，1990，16（5）：558-560.

[3] 朱桂明，郭得科，金士尧.ODBF：基于操作型衰落Bloom Filter 的P2P网络弱状态路由算法[J].计算机学报，2012，35（5）：911-917.

ZHU G K， GUO D K， JIN S R. ODBF：A P2P weak state routing scheme based on operative decaying Bloom filter[J].Chinese Journal of Computers，2012，35（5）：911-917.（In Chinese）

[4] LI J， TAYLOR J， SERBAN L， et al. Self-organization in peer-to-peer system[C]// Proceedings of the 10th Workshop on ACM SIGOPS European Workshop. New York： ACM， 2002：125-132.

[5] CUENA-ACUNA F M， PEERY C， MARTIN R P， et al. PlantP： using gossiping to build content addressable peer to peer information sharing communities[C]//Proc 12th IEEE International Symposium on High performance Distributed Computing. Washington： IEEE， 2003：236-249.

[6] RHEA S C， KUBIATOWICZ J. Probabilistic location and routing[C]//Proceedings of INFOCOM 2002. New York： IEEE Computer Society， 2002：1248-1257.

[7] FAN L， CAO P， J ALMEIDA J， et al. Summary cache： a scalable wide-area web cache sharing protocol[J]. IEEE/ACM Trans on Networking， 2000，8（3）：281-293.

[8] 李緯，张大方，黄昆，等. 面向大数据处理的高精度多维计数布鲁姆过滤器[J]. 电子学报，2015，43（4）：652-657.

LI W， ZHANG D F， HUANG K， et al. Accurate multi-dimension counting Bloom filter for big data processing[J]. Acta Electronica Sinica， 2015，43（4）：652-657. （In Chinese）

[9] MITZENMAEHER M. Compressed Bloom filters[J]. IEEE/ACM Trans on Networking， 2002，10（5）：604-612.

[10]SAAR C， YOSSI M. Spectral Bloom filters[C]// Proceedings of ACM SIGMOD International Conference on Management of Data. San Diego： ACM Press， 2003：241-245.

[11]肖明忠，代亚菲，李晓明.拆分型Bloom Filter[J].电子学报，2004，32（2）：241-245.

XIAO M Z， DAI Y F， LI X M. Split Bloom filter[J]. Acta Electronica Sinica， 2004，32（2）：241-245. （In Chinese）

[12]GUO D， WU J， CHEN H， et al. Theory and network applications of dynamic Bloom filters[C]//Proceedings of 25th IEEE International Conference on Computer Communications. Barcelona， Catalunya： Joint Conference of the IEEE Computer and Communications Societies， 2006：23-29.

[13]唐海娜，林小拉，韩春静. 基于移动指针的数据流冗余消除算法[J].通信学报，2012，33（2）：7-14.

TANG H N， LIN X L， HAN C J. Duplicate elimination algorithm for data streams with SKIP Bloom filter[J]. Journal on Communications， 2012，33（2）：7-14. （In Chinese）

[14]LIM H， LEE J， BYUN H， et al. Ternary Bloom filter replacing counting Bloom filter[J]. IEEE Communications Letters， 2017，21（2）：278-281.

[15]肖明忠，王佳聪，闵博楠.针对动态集的矩阵型Bloom Filter表示与查找[J].计算机应用研究，2008，25（7）：2001-2022.

XIAO M Z， WANG J C， MIN B N. Matrix Bloom filter on dynamic set[J]. Application Research of Computers，2008，25（7）： 2001-2022.（In Chinese）

[16]LIU Y， GE X Z， DU D H C， et al. Par-BF： a parallel partitioned Bloom filter for dynamic data sets[C]//Proceedings of 2014 International Workshop on Data Intensive Scalable Computing Systems. New Orleans，Piscataway， NJ： IEEE， 2014：1-8.

[17]WEI J， HONG J， ZHOU K， et al. Efficiently representing membership for variable large data sets [J]. IEEE Transactions on Parallel and Distributed Systems， 2014， 25（4）： 960-970.

[18]王勇，云晓春，王树鹏，等. CBFM：支持属性删减的布鲁姆过滤器矩阵多维元素查询算法[J]. 通信学报， 2016，37（3）：139-147.

WANG Y， YUN X C， WANG S P， et al. CBFM： cutted Bloom filter matrix for multi-dimensional membership query[J]. Journal on Communications， 2016，37（3）：139-147. （In Chinese）

[19]孙智超，徐蕾.二路平衡动态布隆过滤器[J].数学的实践与认识，2014，44（5）：199-205.

SUN Z C， XU L. 2-balance dynamic Bloom filter[J].Mathematics in Practice and Theory， 2014，44（5）： 199-205.（In Chinese）