(19)中华人民共和国国家知识产权局
(12)发明专利说明书 | ||
(10)申请公布号 CN 101082923 A (43)申请公布日 2007.12.05 | ||
(21)申请号 CN200710035385.5
(22)申请日 2007.07.18
(71)申请人 湖南大学
地址 410082 湖南省长沙市麓山南路2号
(72)发明人 谢鲲 闵应骅 张大方 文吉刚 谢高岗
(74)专利代理机构 长沙正奇专利事务所有限责任公司
代理人 马强
(51)Int.CI
G06F17/30
权利要求说明书 说明书 幅图 |
(54)发明名称
一种可扩展的布鲁姆过滤器查询方法及其元素插入方法 | |
(57)摘要
本发明提供一种可扩展布鲁姆过滤器(Scalable Bloom filter)查询方法，在数据集元素个数增长的情况下，通过添加长度成倍增长过滤器向量来保持很低的误判率，并给出了一种可扩展布鲁姆过滤器查询方法的元素插入方法。实验表明，可扩展布鲁姆过滤器的元素查询误判率永远小于动态布鲁姆过滤器，可以控制查询误判率在1％，在3.0GHz的CPU机器中，一次元素查询时间仅20μs，比DBF查询速度快很多倍。本发明在现有的布鲁姆过滤器应用领域都可以适应，由于支持集合的动态扩展，因此比现有的布鲁姆过滤器具有更加广泛的应用前景。 | |
法律状态
法律状态公告日 | 法律状态信息 | 法律状态 |
权 利 要 求 说 明 书
1、一种可扩展布鲁姆过滤器查询方法，其特征在于，该方法为：
1)布鲁姆过滤器的扩展：当可扩展布鲁姆过滤器SBF所表示的集合元素增长超过可扩展布鲁姆过滤器容量限制时，添加一个长度为前一个可扩展布鲁姆过滤器向量的2倍的向量，即添加了可扩展布鲁姆过滤器向量的向量长度m<sub>i</sub>＝2m<sub>i-1</sub>，此时添加了可扩展布鲁姆过滤器向量的向量容量限制也为前一个向量容量限制的2倍，即n<sub>i</sub>＝2n<sub>i-1</sub>；
2)可扩展布鲁姆过滤器元素查询步骤：
第一步：利用SBF查询元素x是否在集合S中，令j＝i；
第二步：通过k个哈希函数计算x在SBF<sub>j</sub>的k个映射位，检查所有位是否都为1；
第三步：所述结果为是时，元素x是SBF<sub>j</sub>表示的元素，x在集合S中，返回True；
第四步：所述结果为否时，元素x不是SBF<sub>j</sub>表示的元素，需要继续检查x是否为SBF<sub>j-1</sub>表示的元素，j←j-1，转到2持续检查x是否为当前向量SBF<sub>j</sub>直至j＝-1。
2、一种如权利要求1所述可扩展布鲁姆过滤器查询方法的元素插入方法，其特征在于，若c为SBF已经表示的元素个数，则所述可扩展布鲁姆过滤器SBF查询方法的元素插入流程为：
第一步，新元素x插入SBF时，首先检查<maths> <math>>>c</mi>>≥</mo>>>Σ</mi>>>j</mi>>=</mo>>0</mn>>>i</mi>> <msub>>n</mi>>j</mi>>>>s>
第二步，如果步骤1中式成立，创建新的过滤器向量SBF<sub>i+1</sub>，通过k个哈希函数计算x在SBF<sub>i+1</sub>的k个映射位，并置位，将x插入到SBF<sub>i+1</sub>中，c←
c+1，i←i+1；
第三步，如果步骤1中式不成立，通过k个哈希函数计算x在SBF<sub>i</sub>的k个映射位，并置位，将x插入到当前过滤器向量SBF<sub>i</sub>中，c←c+1。
说 明 书
技术领域
本发明是涉及分布式计算技术领域，特别是涉及分布式系统产生大量数据、需要进行交互查询的应用，具体是一种可扩展布鲁姆过滤器查询方法及其元素插入方法。
背景技术
随着计算技术和因特网的高速发展，数据量不断加大，网络的异构性和复杂性不断增加，日趋多样化和复杂化的计算机环境，需要在形式、规模、功能和性能等多个层次展开计算系统的可扩展性研究。存储系统的可扩展性是当前计算机研究的热点。布鲁姆过滤器对数据集合采用一个位串表示并能有效支持元素的哈希查，是一种能够表示集合、支持集合查询的简
洁数据结构。面对不断发展的计算机和网络环境，数据膨胀时，研究可扩展的布鲁姆过滤结构支持动态集合查询成为布鲁姆过滤器在分布式系统应用中迫切需要解决的问题。
布鲁姆过滤器(Bloom Filter)对数据集合采用一个位串表示并能有效支持集合元素的哈希查，是一种能够表示集合、支持集合查询的简洁数据结构，它能够有效的过滤掉不属于集合的元素，因其是由B.Bloom提出的而称为布鲁姆过滤器(Bloom Filter)。由于其哈希查的常数时间和存储空间开销较小，从而使它具有很好的实用价值。
布鲁姆过滤器自1970年提出以来，被广泛应用到各种计算机系统中，以提高庞大数据集的查效率。早期的应用主要集中在数据库操作和字典查询操作。最近，随着网络研究的发展以及新的覆盖网和P2P网络应用技术的涌现，布鲁姆过滤器已经越来越广泛的应用于网络中，例如：覆盖网和P2P网节点协作交互、资源路由、数据帧路由标签、网络测量管理、网络安全等。
目前布鲁姆过滤器查询算法主要有：标准的布鲁姆过滤器算法，计数器布鲁姆过滤器算法，压缩布鲁姆过滤器算法，Spectral布鲁姆过滤器算法，拆分型布鲁姆过滤器查询算法，动态布鲁姆过滤器算法和分档布鲁姆过滤器算法。
目前的布鲁姆过滤器算法大都忽略了布鲁姆过滤器可扩展性问题。现有的布鲁姆过滤器大多是用固定的过滤器设计参数来表示固定的静态集合，根据固定的集合元素规模和其在实际应用中所能容忍的最大误判概率，确定其运算时哈希函数个数和过滤器向量的长度。因此，当集合变大时，以往大多数布鲁姆过滤器的设计可能导致不能容忍的查询误判概率，误判率迅速增长到1。
布鲁姆过滤器可扩展性主要是当集合元素动态增长超出过滤器设计的容量时，如何调整布鲁姆过滤器参数，使得布鲁姆过滤器有较低的查询误判率，同时具有可接受的计算性能，保证过滤器的可用性。就目前的算法来说，拆分型布鲁姆过滤器(Split Bloom filter)和动态布鲁姆过滤器(Dynamic Bloomfilter，DBF)都企图通过将过滤器的位向量转换为由多个位向量组成的矩阵来解决可扩展性问题，这两种方法都是通过添加同样大小的布鲁姆过滤器向量来适应集合规模的增长。虽然这两种方法可以有效的缓解由于集合规模的增长而导致的标准布鲁姆过滤器误判率迅速攀升。但是，这种线性扩展向量的方法在实际使用时，随着元素个数增加，向量个数快速攀升，误判率增长速度快，缓解程度有限。同时，此类方法的查询时间复杂度较高，查询的时间复杂度仍有改进的空间。
发明内容
本发明要解决的技术问题是，针对现有技术存在的缺陷，提出一种可扩展的布鲁姆过滤器(Scalable Bloom filter，简称SBF)查询方法及其元素插入方法。当集合元素不断增长时，通过不断增加长度成倍增长的布鲁姆过滤器向量来调整查询误判率。并以此为基础，给出了新的可扩展布鲁姆过滤器的元素的插入、查询方法。本发明提出的可扩展布鲁姆过滤器支持集合规模的扩张，在现有的布鲁姆过滤器应用领域都可以适应，如分布式计算、计算机网络资源定位、数据库的交互查询、P2P网络资源交互、传感器网络信息交换、计算机网络监测、计算机缓存系统设计等产生大量数据、需要进行交互查询的应用领域。本发明尤其适用于集合动态膨胀的应用场合，具有十分广泛的应用前景。
本发明的解决方案是：一种可扩展布鲁姆过滤器(Scalable Bloom filter：以下简称SBF)查询方法，该方法为：
1)布鲁姆过滤器的扩展：当可扩展布鲁姆过滤器SBF所表示的集合元素增长超过可扩展布鲁姆过滤器容量限制时，添加一个长度为前一个可扩展布鲁姆过滤器向量的2倍的向量，即添加了可扩展布鲁姆过滤器向量的向量长度m<sub>i</sub>＝2m<sub>i-1</sub>，此时添加了可扩展布鲁姆过滤器向量的向量容量限制也为前一个向量容量限制的2倍，即n<sub>i</sub>＝2n<sub>i-1</sub>；
2)可扩展布鲁姆过滤器元素查询步骤：
第一步：利用SBF查询元素x是否在集合S中，令j＝i；
第二步：通过k个哈希函数计算x在SBF<sub>j</sub>的k个映射位，检查所有位是否都为1；
第三步：所述结果为是时，元素x是SBF<sub>j</sub>表示的元素，x在集合S中，返回True；
第四步：所述结果为否时，元素x不是SBF<sub>j</sub>表示的元素，需要继续检查x是否为SBF<sub>j-1</sub>表示的元素，j←j-1，转到2持续检查x是否为当前向量SBF<sub>j</sub>直至j＝-1。
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论