一种基于Bloom过滤器的服务模糊匹配算法

针对基于内容的发布/订阅系统中常用的查找匹配算法要求严格、不能很好地支持服务模糊匹配的问题,提 出了一种支持模糊匹配的服务匹配算法。该算法的基本思想是首先将服务与需求分别用两个Bloom过滤器来表示, 然后通过比较两个Bloom过滤器比特向量的相似程度,估算需求与服务之间的匹配程度。理论分析及仿真结果表 明,此算法可通过简单的Bloom过滤器运算实现基于内容的服务模糊匹配,准确度在95%以上。     

基于平衡二叉树和Bloom过滤器的可变长地址路由查找算法

可变长地址是未来网络领域的重要研究内容之一。针对传统路由查找算法在面向可变长地址时查找效率低的问题，提出一种基于平衡二叉树AVL(Adelson-Velskii and Landis)树和Bloom过滤器的适用于可变长地址的高效路由查找算法，简称为AVL-Bloom算法。首先，针对可变长地址灵活可变且无界的特点，利用多个片外哈希表分别存储前缀比特位数相同的路由条目及其下一跳信息，同时应用片上Bloom过滤器加速搜索可能匹配的路由前缀；其次，为了解决基于哈希技术的路由查找算法在查找最长前缀路由时需多次哈希对比的问题，引入AVL树技术，即通过AVL树组织每组路由前缀集合的Bloom过滤器及其哈希表，优化路由前缀长度的查询顺序，并减少哈希计算次数进而降低查询时间；最后，在3种不同的可变长地址数据集上将所提算法与METrie(Multi-Entrance-Trie)和COBF(Controlled prefix and One-hashing Bloom Filter)这两种传统路由查找算法进行对比实验。实验结果表明，AVL-Bloom算法的查询时间明显少于METrie和COBF算法，分别减少...     

基于并行Bloom过滤器组的深度数据包检测算法

针对基于软件、硬件的深度数据包检测存在处理速度慢或规则集更新困难等方面的局限性,提出一种在多核平台上基于并行Bloom过滤器组的深度数据包检测算法。算法中首先将规则集按规则的长度分组,构造一个并行Bloom过滤器组,组中每个计数式 Bloom过滤器表示特定规则长度的规则集。为了减少执行过程中的冲突概率和计算量,构造了高性能的哈希函数,然后基于多核平台的并行处理能力使用并行编程实现了该算法。理论分析和实验结果表明该算法是一种时空高效的算法。     

一种面向深度数据包检测的索引拆分Bloom过滤器

高速数据包处理迫切需要时空高效的深度数据包检测(DPI),满足其线速处理和低存储空间需求.Trie位图内容分析器(TriBiCa)采用片上位图Trie树来实现元素的最小完美Hash;但是,TriBiCa存在更新开销高和假阳性访问次数多等问题.共享节点快速Hash表(SFHT)采用片上计数Bloom过滤器(CBF)来实现硬件Hash表的快速查找;但是,SFHT存在更新开销高和存储空间需求大等问题.文中提出了一种索引拆分Bloom过滤器(ISBF).ISBF是由片上多组并行CBF和片外元素集构成,其核心思想是:元素的片外索引值被拆分成多组比特,每组比特采用多个片上并行CBF表示元素集;当查询元素时,每组并行CBF产生多个比特值,并合成候选元素的片外索引值.为了降低ISBF的更新开销,文中又提出了懒惰删除(lazyd eletion)算法和空缺插入(vacant insertion)算法,即采用一个片上删除位图,仅在片上并行CBF中删除或插入元素,而不需要调整其他元素的片外索引值.ISBF是一种时空高效的数据结构,其插入、删除和查询操作的平均片外存储器访问次数均为O(1);与TriBiCa和SFHT相比,ISBF在...     

基于DCBF的流抽样测量算法

为了提高系统的处理效率,减少系统的测量误差,提出了一种基于动态计数型布鲁姆过滤器（Dynamic Counting Bloom Filter,DCBF）的流抽样测量算法。该算法使用基于报文级别的抽样,并通过DCBF进行流查找和统计,且在CBF计数器溢出时动态增加新的CBF。经理论分析和实验表明,该算法不仅提高了系统的运行效率,减少了存储空间的消耗,同时具有准确性和可扩展性,能很好地适用于高速链路的流量测量中。     

K分组合型Bloom Filter方法的设计

Bloom Filter是一种采用位向量表示数据集合并利用Hash函数支持有效数据查找的方法.它能够很好地判定某个元素是否属于给定的集合.拆分型Bloom Filter是Bloom Filter的一种改进,它能较好地缓解分布式环境下集合元素动态增长导致的查找误称率增大问题.作为一种新的K分组合型Bloom Filter,通过与Bloom Filter和拆分型Bloom Filter比较分析的结果表明,该方法能够在误称率、向量空间和平均判定时间3个指标中得到较好的平衡.     

Hash算法在网络处理器中的实现

提出一种应用于网络处理器的Hash算法,通过建立新型查找表的结构和构造两级Hash函数,能够有效地解决Hash冲突的问题。描述Hash表的软件建立流程和硬件查找过程,在Hash查找的基础上,给出硬件表项的学习过程和老化方法,简化表项的更新操作。针对不同的应用,建立不同类型的Hash表,合理地利用内外部存储资源,兼顾了存储资源和处理速度的平衡。实验结果表明,该算法对各种查找表中不同的表项数目和关键词长度均具有较好的兼容性,成功查找的平均长度为2,减少了存储器的访存次数,其单个微引擎的查找速度高达25Mb/s,能够满足网络处理器接口处理带宽20Gb/s的要求。     

基于布鲁姆过滤器距离的集合变动定量评估算法

布鲁姆过滤器(Bloom filter)对数据集合采用一个位串表示并能有效支持元素的哈希查找,是一种精简的信息表示方案,广泛应用于数据库、网络和分布式系统中.本文研究布鲁姆过滤器的序列分析方法,通过定义布鲁姆过滤器距离,用概率统计方法分析动态数据集合元素增加和删除的变化对布鲁姆过滤器的影响,提出了基于计数式布鲁姆过滤器距离的集合变动定量评估算法.理论分析和仿真实验表明,该评估算法评估准确率高达90%以上.     

B-树和Bloom filter相结合的IPv6路由查找算法

为了提高IPv6的路由查找效率,针对IPv6路由前缀分布不均匀的问题,提出了一种基于B-树和Bloom filter相结合的IPv6路由查找算法（BTBF）。BTBF分为B-树和Bloom filter查找两部分,利用B-树查找路由前缀的前16 bit值,然后通过B-树节点中位向量的映射,将下一步链接到Bloom filter,再利用Bloom filter位数组的值映射提取下一跳。实验结果表明,BTBF算法与其他树型和Bloom filter类算法相比有效减少了空间和时间占用,在路由表项数变化较大的情况下也能维持稳定的查找性能。     

针对动态集的矩阵型Bloom filter表示与查找*

提出一种针对动态集合的矩阵型Bloom filter表示与查找法（matrix Bloom filter,MBF）,它使用一个s×m位矩阵对数据集合进行哈希表示与查找,较同类算法SBF和DBF,能继承Bloom filter算法常数查找开销的基本精髓。     

基于FPGA的3G数据包过滤算法设计及实现

本文以FPGA为平台,设计了在TD-SCDMA分组域中实现数据包截获和过滤的系统框架以及基本功能模块,结合Bloom Filter等算法的特点提出了Hash算法实现数据包过滤,并用Verilog语言实现,程序下载至FPGA开发板进行了实测。结果表明,在大规模用户群中均匀抽取部分用户进行监管时,过滤设备可以线速地处理GTP数据包并完成设定用户的过滤。     

快速检测RFID复制标签的算法研究

针对大型的RFID系统中使用标签ID无法识别具体复制标签的问题,提出了一种快速检测复制标签的CTDA算法。首先,标签内存储[k]个哈希函数,标签在接收到阅读器的查询帧后多次回复阅读器构造虚拟克鲁姆过滤器,找到阅读器通信区域内的标签集合[M];然后,[M]中标签通过多轮哈希运算使得阅读器构建时隙状态向量,目的是给每个标签分配单一时隙;最后,标签向阅读器回复10 bit信息,阅读器通过检测各个时隙是否由单一时隙变成冲突时隙来判断标签是否受到复制。经过仿真分析,证明该算法在执行时间上优于Bu K提出的GREAT算法和Qiao Yan提出的轮询协议RIP算法。     

流媒体系统的资源知名度生成与分发算法

为提高流媒体系统中混合搜索算法搜索决策的准确性,减少传统资源知名度分发过程中消息报文的开销,提出一种流媒体系统的资源知名度生成与分发算法.生成算法基于全局变化率,采用心跳检测机制检测节点的被动离开;一致性分发算法利用Bloom滤波器进行资源知名度的分发.与传统资源知名度生成与分发算法相比,该算法能更真实地反映资源的动态...     

基于Bloom Filter和概率分发队列的P2P网络快速查找算法

无结构化P2P网络资源定位过程中的响应时间、查准率及覆盖率难以同时被优化。提出一种面向有向无环随机网络的基于Bloom Filter和概率分发队列的快速查找算法BFPDQ(Bloom Filter and Probabilistic Distribution Queue),它用Bloom Filter表达和传递节点命中资源信息及查找请求信息,计算新查询消息与历史查询消息Bloom Filter语义向量相似度,并应用底层网络路径性能信息指导上层转发决策。概率分发队列(Probabilistic Distribution Queue,PDQ)把传统walkers表示成为查找消息分发队列,查找请求者协调各分发队列的查找方向和深度,并融合各队列查找过程中得到的定位消息。仿真实验表明,BFPDQ算法在保持较少冗余信息的同时有效缩短了响应时间。     

基于值域二次哈希方法的布鲁姆过滤器

本文针对扩展式布鲁姆过滤器(EBF)内存消耗过大,提出一种基于值域哈希二次过滤的布鲁姆过滤器数据结构(VHBF)和相关算法,VHBF通过在布鲁姆过滤器中对集合中的每个特征进行k次哈希,并将此k次哈希值转化为相应特征的镜像特征。然后对此镜像进行二次过滤运算,运算后的结果保存在另一布鲁姆过滤器中。在对特征进行检索时,由于无需保存特征本身,因而空间效率比EBF更高。实验表明,VHBF的假阳性误判率的比扩展型布鲁姆过滤器(EBF)低,而VHBF内存消耗也低于EBF。     

用哈希算法和二分法实现中文词典的快速查找

分词词典是汉语自动分词系统中的一个基本组成部分,其查询速度直接影响到分词系统的处理速度。文章提出并实现了一种用哈希算法和二分查找算法相结合的中文单词查找算法,实验显示,该算法可以实现对字符串的快速查找。     

基于多哈希算法的大规模图像快速检索方法

哈希技术被视为最有潜力的相似性搜索方法,其可以用于大规模多媒体数据搜索场合。为了解决在大规模图像情况下,数据检索效率低下的问题,提出了一种基于分段哈希码的倒排索引树结构,该索引结构将哈希码进行分段处理,对每段哈希码维护一个倒排索引树结构,并结合高效的布隆过滤器构建哈希索引结构。为了进一步提高检索准确性,设计了一种准确的排序融合算法,对多个哈希算法的排序结果分别构建加权无向图,采用PageRank的思想对基于多个哈希算法的排序列表的融合技术进行了详细的说明。实验结果表明,基于分段哈希码的倒排索引树结构能极大地提升数据的检索速度。此外,相比于传统的单个哈希算法排序技术,基于多个哈希算法的排序列表融合技术的检索准确率优势显著。     

基于非线性数字滤波器的混沌Hash函数设计

在分析变系数非线性数字滤波器的混沌特性的基础上,提出一种带密钥的混沌Hash构造方法.首先构建能产生高维混沌序列的非线性数字滤波器;然后通过混沌调制方式将明文信息注入滤波器均匀分布的混沌轨迹中;最后以扰动映射和滤波器的初态作为密钥,以轨迹的粗粒化量化形成明文的Hash值.研究表明,该算法简单快速,比基于单一混沌映射的Hash算法安全性更高;同时,滤波器结构中没有复杂的浮点运算,比一般复合混沌系统更易于软硬件实现.