面向大数据处理的高精度多维计数布鲁姆过滤器

分析了现有多维布鲁姆过滤器查询算法的工作原理和特点,针对大数据处理特点提出了一种基于双射函数的高精度多维计数布鲁姆过滤器(AMD-CBF)查询算法.AMD-CBF中元素表示和查找分两步进行,第1步将元素各属性哈希映射到各自对应的高精度计数布鲁姆过滤器(A-CBF)中;第2步将元素的所有属性通过双射函数转换为一个值来表示元素整体信息,然后将这个值哈希映射到联合计数布鲁姆过滤器中(C-CBF),完成元素整体的表示和查询确认.理论分析和仿真实验结果表明,AMD-CBF能够支持多维集合元素的高效表示和查询及删除,相比同类研究查询假阳性降低明显,查询精度大幅度提高.

基于计数布鲁姆过滤器的快速多维包分类算法

本文从数据包匹配规则的聚集特性出发,将计数布鲁姆过滤器和哈希表相结合,设计并实现了一种高效的多维包分类算法CBHT(Counting Bloom filter and Hash Table).基于包匹配规则的聚集特性,对于五维包分类问题,CBHT算法首先利用计数布鲁姆过滤器的过滤功能结合单域匹配获得与前两维匹配的小规模规则集,而后在此有限规则集中对后三维进行匹配.利用计数布鲁姆过滤器提高了包匹配速度并有效支持规则库的动态更新.实验结果表明CBHT算法比现有的B2PC算法节省60%的硬件资源,包匹配访问内存次数平均低于B2PC算法22.8%.

计数布鲁姆过滤器代数运算

文中探讨计数布鲁姆过滤器的代数运算和集合运算的一致性关系,研究使用计数布鲁姆过滤器代数运算进行集合成员查询的性能.理论分析和实验结果表明,计数布鲁姆过滤器的并、交、补、减、异或运算产生的新过滤器依然保持计数布鲁姆过滤器的特征,支持元素的删除操作,不会出现假阴性,能用于集合并集、交集、补集、差集及对称差的成员查询;当使用两个原始的计数布鲁姆过滤器查询补集、差集及对称差元素时,会存在部分本来属于补集、差集或对称差的元素被判为不属于补集、差集或对称差的问题,而使用计数布鲁姆过滤器代数运算后的过滤器进行补集、差集及对称差成员查询,则不存在上述问题,空间效率能提高一倍,时间效率亦能显著地得到改善.计数布鲁姆过滤器代数运算的使用有利于进一步扩展计数布鲁姆过滤器的应用范围.譬如计数布鲁姆过滤器减运算可用作一种新的集合调和方法,用于分布式系统中大型文件的分发.

基于计数布鲁姆过滤器的集合调和算法

提出了一种基于计数布鲁姆过滤器的集合调和方法,该方法将远程节点A和B上的数据集合SA和SB分别用计数布鲁姆过滤器表示,设为CBF(SA)和CBF(SB),节点A将CBF(SA)发送给节点B,节点B进行计数布鲁姆过滤器减运算,得到差过滤器CBF(SB)CBF(SA),然后利用CBF(SB)CBF(SA)查询并获得集合SB中的差集元素SB SA,并返回SB SA给节点A,最后节点A用差集SB SA和自身集合SA进行集合并运算,完成集合调和。由于计数布鲁姆过滤器支持集合元素的删除操作,因此,该方法非常适合应用于数据集合更新频繁的分布式系统。理论分析和仿真实验结果表明,该方法既具有精确集合调和,能得到全部SB SA元素的优点,也具有近似集合调和仅需单轮消息交换的优点。

矩阵型布鲁姆过滤器在病毒过滤防火墙中的研究

针对传统的基于特征码的病毒过滤算法在实际运行中存在的效率问题,提出了一种基于矩阵型布鲁姆过滤器(MBF)的病毒过滤算法。在分析该算法的空间效率、时间效率以及错误判断率的基础上,进一步研究了它的数学模型,并给出了该算法在高速病毒过滤引擎中的设计方案。最后,通过仿真实验验证该算法的有效性和实用性。

基于计数布鲁姆过滤器删除运算的高效远程集合调和算法

该文基于计数布鲁姆过滤器的删除运算构建了一种远程集合调和算法,理论分析和实验结果表明,基于计数布鲁姆过滤器删除运算的远程集合调和算法能够较好地完成远程集合高效求解集合并集的问题,仅有少量差集元素被遗漏,调和成功率较高,而且可通过参数的调整将调和成功率提高至100%。

基于计数型布隆过滤器的文本检索模型

分布式文本检索系统难以兼顾高效率的数据检索和低成本的索引维护。为此,提出一种基于计数型布隆过滤器的文本检索模型CBFTRM。该模型将物理节点分为数据节点和索引节点,分别采用结构化P2P进行网络覆盖。每个数据节点负责存储文档数据并维护与之相应的倒排索引,同时通过倒排索引中的关键词集合计算出计数型布隆过滤器值,发送给相应的索引节点。每个索引节点建立一棵以部分数据节点的特征信息(包括过滤器值)为叶节点、以过滤器值运算结果为内部节点的搜索树,并在叶节点发生变化时对搜索树进行维护。仿真实验结果表明,该模型文档定位快,索引维护通信量小,而且具有较高的查准率。

一种基于计数型布隆过滤器的分子相似性算法研究

分子相似性是虚拟筛选技术的重要环节,在计算机辅助药物设计中有着关键作用。在2D Fingerprint相似性判别过程中,一些典型的分子相似性评估过程使用了Hash函数进行分子指纹映射,然而Hash函数固有的冲突问题极易降低分子指纹的映射精度。提出了一种基于计数型布隆过滤器的指纹映射方法,对相似性判别过程进行了有效改进,并采用DUD LIB VS 1.0数据集对改进方法进行了比较验证,将ROCE,AUC,awROCE,awAUC值作为评价标准。与其他原始分子相似性方法相比,所提方法有效地提高了相似性判断的准确性和骨架跃迁能力。

基于计数型布隆过滤器的可排序密文检索方法

云计算环境下密文检索困难,已有的可搜索加密方案存在时间效率低、文件检索索引不支持更新、检索结果不能实现按精确度排序等问题。首先基于计数型布隆过滤器构建文件检索索引,将文件集中的关键词哈希映射到计数型布隆过滤器索引向量,实现了按关键词进行密文检索,同时,支持密文检索索引的动态更新。其次,由于计数型布隆过滤器本身不具备语义功能,不能实现按相关度对检索结果排序,引入关键词频率矩阵和词频逆文本频率(TF-IDF)模型计算关键词的相关度分值,以实现按相关度分值对检索结果排序。最后,理论和实验性能分析证明了该方法的安全性、可更新能力、可排序能力和高效性。

基于计数型Bloom过滤器的网络数据流统计

现有的流统计信息主要侧重于流抽样而忽视全流统计。为此,提出一种使用优化设计的计数型Bloom过滤器流统计方法。针对计数型Bloom过滤器数据增长带来的计数器溢出和假阳性错误率增高的问题,分别设计动态统计和多个计数器协同统计的方案。概要化的存储结构可方便查询,而且其计数型Bloom过滤器简单的数据结构也易于硬件实现。实验结果表明,与传统哈希方法相比,计数型Bloom过滤器流统计方法的时间复杂度更低,可用于网络应用中的快速全流统计。

典型Bloom过滤器的研究及其数据流应用

Bloom过滤器是一种空间高效但有一定假阳性的数据表示方法。该文分析比较计数型Bloom过滤器、光谱Bloom过滤器和动态计数过滤器的异同点及适用场合,介绍Bloom过滤器在重复项检测及频繁项挖掘中的应用,总结Bloom过滤器给数据流带来的挑战,包括元素突发问题及数据流相异元素数目变化问题。

基于动态布鲁姆过滤器的DDoS攻击检测方法

基于传统的布鲁姆过滤器在异常流量检测方面存在的不足,提出了动态布鲁姆过滤器的异常流量检测的结构,在检测率和误码率上都有所提高,从而更有效的预防了DDOS攻击。

空间高效的计数器结构

针对高速数据流测量算法中对空间高效计数器的需求,重点分析了DISCO和BRICK两种空间高效的主动计数器,并对BRICK进行了改进,提出了一种面向高速骨干网流测量的DA-BRICK计数器。采用真实的网络流量,对DA-BRICK的性能进行了仿真验证。结果表明:DA-BRICK适用于高速测量的实时需要,同时不会增大错误概率,但和BRICK相比,在支持相同数目计数器的前提下,DA-BRICK所需的存储空间增加了30%。

高速网络流频繁项挖掘算法

在当前骨干网络链路速率呈几何倍数增长的情况下,实时准确地挖掘出网络流中的频繁项对于网络管理和网络安全具有重要的意义.在SS(space saving)计数算法的启发之下,针对网络流的实际特性,提出了一种剪枝操作受时间和流长双重约束的网络流频繁项挖掘算法(integrated weighted frequent items mining,IWFIM).IWFIM计数算法采用时间和流长组合赋权的方式为每个流项赋权,且算法每次剪枝操作时总是删除权值最小的流项.在IWFIM算法的基础上,依据网络流的重尾分布特性,又提出了一种能够结合散列方法和计数方法优点的网络流频繁项挖掘算法(counting Blooming filter and integrated weighted frequent items mining,CBF_IWFIM).CBF_IWFIM算法首先采用改进的计数型布鲁姆过滤器(counting Blooming filter,CBF)在不保存网络流信息的情况下过滤掉绝大部分的短流,然后采用IWFIM算法实现网络流频繁项挖掘.通过实际网络流量测试表明,CBF_IWFIM和IWFIM算法具有非常高的空间利用率和准确率,2种算法对于网络流频繁项的挖掘效果明显优于SS等3种算法,即使在使用其他算法1?3缓存的极端情况下,CBF_IWFIM和IWFIM 2种算法的频繁项识别效果仍然要优于SS等算法.

IMS网络中的SIP洪泛攻击检测

为了检测针对3G核心网中IP多媒体子系统的SIP(session initiation protocol)洪泛攻击,提出了一种双抽样多点检测方法.该方法在使用计数式布鲁姆过滤器统计检测特征信息的基础上,将检测空间划分为5个范围,即正常范围、关注范围、检测范围、精检测范围和攻击范围,然后对落在不同范围内的统计信息给予相应的检测.仿真实验结果表明,该方法具有较好的检测性能.

基于CBF-SS策略的大流识别算法

在分析大流识别算法中的散列方法和计数方法的优缺点的基础上,针对网络流的重尾分布特性,提出一种能够有效结合散列方法和计数方法优点的大流识别算法CBF-SS(counting Bloom filter&space saving).该算法首先采用改进的计数型布鲁姆过滤器(counting Bloom filter,CBF)过滤掉大部分的小流,然后通过SS(space saving)计数算法识别出网络中的大流.理论分析和实验结果表明,CBF-SS算法具有较低的时间复杂度和空间复杂度,在大流识别效果上远优于SS等算法.

一种基于响应追踪的非结构化P2P资源查找机制

为了提高非结构化P2P中资源查找的效率,针对查找请求的关键字重复出现以及资源共享不平均的现象,提出了基于响应追踪的资源查找机制RTRSM(Response Tracing based Resource Searching Mechanism),对请求响应的内容以及响应的来源进行追踪,并记录历史信息,以此构建提示型资源查找。在查找请求转发阶段,依据查找请求与历史记录的相关程度,自适应地调整转发策略,在保证较高查找成功率的同时,降低查找代价,提高查找效率。仿真实验表明,基于响应追踪的资源查找机制RTRSM可扩展性较好,能以较小的开销扩展到较大规模的系统中去。仿真实验还表明,RTRSM能保证90%以上的查找成功率。与洪泛法相比,RTRSM能减少54.2%的平均消息数,减少56.4%的平均跳数;与SQR(Scalble Query Routing)相比能减少28.9%的平均消息数,减少6.4%的平均跳数。

一种抗恶意攻击的OpenFlow虚拟流表高性能查找方法

针对恶意攻击给OpenFlow虚拟流表查找带来的破坏性影响,构建了一种抗恶意攻击的OpenFlow虚拟流表高性能查找方法。该方法基于近似成员关系查询理论,采用布鲁姆过滤器预测元组查找失败结果,以绕过绝大多数元组失败查找操作,提高OpenFlow虚拟流表查找效率;进一步,设计了一种可扩展计数型布鲁姆过滤器,根据元组规模的动态变化进行适应性伸缩,从而始终以高准确率判定元组查找失败结果;最后,采用实际网络流量样本和模拟恶意攻击方式,评估所提OpenFlow虚拟流表查找方法的性能。实验结果表明:当攻击包与正常包分别按1:2和2:1比例混合时,所提方法的假阳性错误率始终保持在6%以下,比计数型布鲁姆过滤器降低了93%,而平均查找长度降低了90%。

一种基于FEFS与CBF的网络大流识别算法

在网络大流识别中,突发的大量小流会影响大流识别准确度。为此,结合基于频率和大小的流提取(FEFS)算法与基于计数型布鲁姆过滤器(CBF)算法,提出一种新的大流识别算法,即FEFS-CBF算法。该算法采用三级存储结构,运用CBF结构存储小流,将达到过滤阈值的流移至筛选区(LRU)中,当LRU满载时,使用FEFS机制选择一个符合条件的流淘汰,并及时隔离大流。仿真结果表明,该算法的误报率和漏报率均较低,存储开销较小,可以运用于高速网络链路的大流识别中。

基于Counting Bloom Filter的流抽样算法研究

为适应高速网络环境并实现对网络流量的准确测量,提出一种将计数型布隆过滤器结构与基于报文的流抽样技术相结合的网络流等概率抽样算法。利用4 bit的Counter向量识别是否有新流出现,通过实时调整抽样频率弥补新流判定中的错误率,从而对网络流进行等概率抽样并获取较真实的网络流分布情况。实验结果表明,该算法的测量结果与网络流真实值较接近,且具有可扩展性,可以满足当前复杂多变的高速网络环境下的流量测量需求。