Bloom Filter研究进展

近年来,由于Bloom filter具有可压缩性和高效查询性,其在分布式数据库、网络缓存、对等网和信息检索等领域引起了越来越多的研究者关注。随着Bloom filter不同应用需求的出现,多种Bloom filter变体被提了出来,诸如:支持删除元素的CBF;可以统计频次型的SBF、DCF、dlCBF;大小可以动态伸长的DBF、SBF;压缩型BF等。本文对Bloom filter及其各种变体进行了介绍,并对其特点进行了分析比较,总结了它们各自的优势和不足,并进一步指出了Bloom filter未来的一些研究方向。     

一种距离加权Bloom Filter的网络路由机制

基于分布式哈希表（DHT）的P2P查找经常受到在底层网络中路由时无必要的路径长度增加的影响。另外．DHT在处理复制方面也有一定的缺陷。提出了距离加权Bloom Filter（dwBF），详细地阐述了在资源分散的覆盖网络中使用距离加权Bloom Filter网络路由算法。     

Bloom Filters散列函数数目多阶段动态优化算法

标准Bloom Filters在操作前需要知道数据集合中不同元素数目才能确定最佳的Hash函数数目,但是数据集的分布情况并不容易事先获得.本文提出一种多阶段Hash函数数目动态优化的Bloom Filters(Multi-stage Dynamic optimization Bloom Filters,MDBF),它将...     

Bloom Filter哈希空间的元素还原

本文提出使用语义增强的Counting Bloom Filter Reconstruction(RSECBF)算法来快速还原源串或给出源串的聚类特征.它给每个哈希函数独立的哈希映射空间以消除哈希函数的内部冲突;扩展哈希函数使其不受均匀性限制,使得哈希函数可以带有语义;利用哈希串的重叠和数量一致性来解决同源哈希串拼接成源串的问题,为源串的还原创造了条件.本文针对Pareto分布的哈希函数,为主成分的还原提出了一个简洁的源串还原算法.对于直接选择部分比特的哈希映射而言,如果主成分分析中的RSECBF不能还原出源串,则还原出来的最长串就是源串的聚类特征.仿真及实际检验表明,Bloom Filter可以扩展其哈希函数来实现语义增强,RSECBF还原的结果是可信的.本算法可以在异常行为发生的时候挖掘网络行为特征.     

基于Bloom Filter的云内容路由优化

随着国家三网融合战略的进一步推进,传统的“广播式”媒体内容分发模式已无法满足用户日益增长的双向“互动式”业务需求。利用云计算技术构建媒体云内容分发网络,实现媒体内容的弹性部署、高效分发来解决该问题,已成为下一代广电网络(NGB)的核心内容。在构建媒体云网络过程中,如何进一步改善用户的响应时延是必须考虑的因素。文中在此背景下,提出利用全局Bloom Filter优化媒体云网络中的内容路由。通过两种优化路由设计,使用户的平均响应时延得到有效下降。并采用排队网络对传统以及优化后的路由策略进行理论建模,使用OMNeT++网络仿真器对提出的路由策略进行仿真。其结论与仿真结果一致性良好。结果显示,优化后的路由策略,在不同的场景下,最多可节省65.2%的平均响应时延。     

基于Bloom Filter的硬件字符串匹配设计与验证

布鲁姆过滤器（Bloom Filter）是一种基于多散列大数据量的数据检索分类算法,在分析布鲁姆过滤器工作原理的基础上,给出了一种基于标准布鲁姆过滤器的硬件字符串匹配检测系统模型。完成了该系统的C语言算法实现,通过实验测试与理论结果相比较,证明了其功能的正确性。在此基础上实现模型的Verilog RTL级描述,通过仿真,验证Verilog程序的功能。针对Altera CycloneⅡEP2C35F672C6FPGA（Field Programmable Gate Array）完成了逻辑综合和时序仿真,文中的硬件字符串匹配检测系统在网络入侵检测、数据库检索等方面具有一定的实用价值。     

信源定位方案中基于Bloom Filter存储的概率日志记录方法研究

该文在信源定位方案中提出了一种基于Bloom filter存储的概率采样日志记录方法。该方法对经过路由器的所有数据实现概率采样,存储采用了高效的Bloom filter存储结构,使得采样信息能够在一定时间内存储在内存中便于查找。基于此方法该文提出信源定位服务器的概念,从而使得核心网络路由器除了路由转发功能之外,只需要完成对数据包的概率采样即可。文中还对相关参数的选择进行了理论分析,从理论上分析了信源定位服务的存储开销以及信源定位有效性,方案具有存储开销小、效率高的特点,从而为进一步的实际网络部署提供了理论依据。     

一种基于并行Bloom Filter的高速URL查找算法

URL查找是众多网络系统中重要的组成部分,如URL过滤系统、Web缓存等.随着互联网的迅速发展,URL查找面临的主要挑战是实现大规模URL集合下的高速查找,同时保证低存储和低功耗.本文提出了一种基于并行Bloom Filter的URL查找算法,CaBF.该算法高度并行化,提供大规模URL集合下的高速最长前缀匹配,并很好地适应集合中不同数量的URL组件.理论分析和真实网络数据集上的实验表明,该算法相比现有算法可以降低假阳性概率达一个数量级(或者在满足相同假阳性概率的前提下降低存储和硬件逻辑资源消耗).此外,该方法的体系结构很容易映射到FPGA等硬件器件上,提供每秒超过150M次的URL查找速度.     

Bloom公司推出新的燃料电池

最近，一直神秘的新公司BloomEnergy为它的技术揭开了面纱，推出了一款燃料电池系统。公司称，它适用各种燃料，通过低廉的能源消耗，它能在3～5年里收回成本。     

基于Bloom filter的多模式匹配引擎

基于Bloom filter,结合位拆分状态机设计了一种适合硬件实现的多模式匹配引擎,由bloom filter过滤出可疑字符,位拆分状态机进行精确匹配.提出了过滤引擎和精确匹配引擎的流水线连接结构,通过增加分配器、缓存等硬件单元解决两引擎处理速度不匹配的问题,利用引擎的并行处理达到较高的吞吐性能.还通过设定规则长度等简化设计使引擎在保持高吞吐量的同时减小资源占用量,提高了可扩展性.     

几何布鲁姆过滤器的设计与分析

针对经典计数型布鲁姆过滤器( NCBF)存储和查询性能较低的缺陷,提出了几何布鲁姆过滤器结构GBF.该结构通过引入“哈希指纹”、布鲁姆过滤器两次分割、基于桶负载存放的方法,实现了集合元素的简洁存储、快速查询.基于“微分方程”和“概率论”的相关知识,对GBF模型进行了理论分析和求解,建立了错误概率和计算复杂度的关系表达式,论证了GBF的几何分布特性.仿真结果表明:与NCBF相比,GBF具有较低错误概率和计算复杂度的同时,也能保持较高的空间利用率.     

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

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

可加速最长前缀匹配的布隆过滤查找方案

作为一种具有过滤功能的数据结构,布隆过滤器在路由查找中正在被广泛应用。在路由查找中布隆过滤器主要用于预处理路由查询,因为路由表通常存储在片外的存储器中,布隆过滤可以将路由表中不存在的路由过滤掉,保证进入查找电路的都为有效路由,最大程度减少不必要的查找。我们的方案使用一种优化的布隆过滤器来加速最长前缀匹配,优化后的布隆过滤器可并行过滤避免了使用流水线技术带来的查找延迟,同时支持删除操作路由,路由更新后不需要重建过滤器降低了路由表的更新延迟。仿真结果表明使用不到2Mb的FPGA片内资源和外部DDR,我们的方案可实现每次查找平均一次片外访问。     

基于布隆过滤器的事务存储架构中的高速缓存

在基于硬件的事务存储多核处理器中,高速缓存具有暂存事务执行结果、检测事务间冲突以及当发生冲突时解决冲突的功能,是系统的核心模块.为了简化上述功能,研究并设计了一种基于布隆过滤器的高效缓存结构,提升了事务的执行效率,并且新增的硬件开销也比较小.     

Optimizing Bloom Filter Settings for Multi-keyword Search in Kademlia-like DHT Peer-to-Peer Networks

This paper has proposed a novel method to reduce the multi-keyword query traffic in Kademlia-like Peer-to-peer （P2P） networks by optimizing the Bloom fil- ter settings. We build some models to estimate the com- munication cost, the union set size, and the loss rate of per- forming union and intersection operations. We implement a Kademlia-like system and generate a group of datasets. We use one part of the datasets to obtain the functions how to compute the optimal parameters and use another part of datasets to verify our method. Each query can de- termine the optimal settings of Bloom filter with no extra configuration. Our simulation experimental results show that with optimal Bloom filters settings, we can greatly reduce the communication cost under an acceptable loss rate.     

一种基于Bloom filter的高速浮动关键词匹配算法

目前浮动关键词模式匹配算法的性能是IP包内容检测及过滤系统的瓶颈.而现有的浮动关键词匹配模式算法存在吞吐率低或支持的关键词数量少的问题.为了解决这些问题,文中提出了一种基于Bloom filter的改进算法.对某些短模式,采用部分无状态过滤思想,使该算法具有快速、可升级、大规模、易实现的特点.仿真试验表明:只要模式出现概率小于0.01,系统吞吐率至少可以实现9Gbps的匹配速率.