联合多维布鲁姆过滤器查询算法

分析了现有多维布鲁姆过滤器查询算法(MDBF)工作原理,提出了一种改进的两步表示和查询的联合多维布鲁姆过滤器(CMDBF)查询算法.CMDBF新增一个用于表示元素整体的联合布鲁姆过滤器CBF,CMDBF中元素表示和查找分两步进行.将MDBF的各属性的表示和查询作为第一步,第二步联合元素所有属性域,利用CBF完成元素整体的表示和查询确认.理论分析和仿真实验结果表明,CMDBF能够支持多维集合元素的简洁表示和查询,相比MDBF查询误判率降低明显.     

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

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

基于布鲁姆过滤器的文本检索系统研究

针对目前文本检索系统出现的信息重复,冗余等问题,提出了一种将布鲁姆过滤器算法与MD5有效结合的方案。对检索关键字进行MD5预处理操作,充分利用MD5的可靠性。并发挥鲁姆过滤器降低检索算法的时间复杂度和空间复杂度的特点,大大提高了检索的快速性,相关性和完备性。     

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

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

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

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

基于同源组合布鲁姆过滤器的早期流量抽样算法

提出一种同源组合布鲁姆过滤器结构,该结构包含流抽样（sample）和分组计数（packet）2个计数器向量组合,2个计数器向量宽度不同,以相同的散列源函数计算散列位置。基于该结构设计的早期流量抽样算法利用2个计数器向量将流抽样判断与分组计数检测分开,避免了早期流量抽样中大量抽样已经结束的流对分组计数过程的影响。分析和实验结果表明,通过调节2个计数器的宽度比α,在不增加内存空间的条件下,该算法有效降低了误判率。     

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

提出了一种基于计数布鲁姆过滤器的集合调和方法,该方法将远程节点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元素的优点,也具有近似集合调和仅需单轮消息交换的优点。     

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

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

基于多维计数型布鲁姆过滤器的大流检测机制

高速网络环境中,实时、准确地提取大流量对于网络安全和网络管理具有重要意义。该文针对传统的流量测量方法受计算资源和存储资源的限制,提出了一种基于多维计数型布鲁姆过滤器(Multi-Dimensional Counting Bloom Fliter, MDCBF)的大流检测机制。它将1维的计数型布鲁姆过滤器(Counting Bloom Fliter, CBF)结构,扩展到支持多维业务流表示、查询和统计计数的MDCBF结构。基于Apriori原理,通过对MDCBF实施重正化,实现了用户自定义的大流检测。并能自适应地配置CBF参数,允许测量误差控制在预定义的范围内。基于计算机产生的模拟数据和实际互联网数据进行了仿真实验,结果显示：该方法既能获得较小的测量误差,又能获得较高的空间利用率。     

一种多维向量并行查询算法

为了解决多维向量数据快速查询问题,在查询范围上限已知的条件下,通过对数据集合采用最近邻准则进行空间划分,构造一种多叉扩展平衡索引树,并设计了索引树的串行和并行查询算法.最后,对并行查询算法的性能进行了分析,测试结果验证了该方法的有效性.     

基于移动指针的数据流冗余消除算法

针对数据流的动态特性,提出了一种基于移动指针的数据流冗余消除算法—SKIP Bloom filter,其核心思想是通过动态指针和双Bloom filter来区分历史数据映射与当前数据映射,从而有效提升了算法的性能和准确度。理论证明,它具有O(n)的时间复杂度与O(1-(1-1/(2 m))w-k)k的假阳性误判率。实验结果表明,算法在实际网络环境中与已有算法相比,准确度提高了2-12倍。     

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

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

Hardware-based high-performance string lookup with value retrieval using extended Bloom filter

in network packet processing, high-performance string lookup systems are very important. In this article, an extended Bloom filter data structure is introduced to support value retrieval string lookup, and to improve its performance, a weighted extended Bloom filter （WEBF） structure is generalized. The optimal configuration of the WEBF is then derived, and it is shown that it outperforms the traditional Bloom filter. Finally, an application-specific integrated circuit （ASIC）-based technique using WEBF is outlined.     

基于新型优化窗的多维全相位数字滤波器设计

提出一种通用的多维全相位数字滤波器的设计方法.基于一维原型全相位数字滤波器(APDF),通过多维抽取变换,设计出具有任意平行六面体通带的多维APDF,并保持奈奎斯特约束特性和零相位特性.利用一种新型优化窗函数设计了性能优异的一维加窗APDF,将其作为一维原型滤波器,生成了不可分离的多维加窗APDF.实例表明,在滤波器长...     

SybilBF: Defending against Sybil Attacks via Bloom Filters

Distributed systems particularly suffer from Sybil attacks, where a malicious user creates numerous bogus nodes to influence the functions of the system. In this letter, we propose a Bloom filter‐based scheme, SybilBF, to fight against Sybil attacks. A Bloom filter presents a set of Sybil nodes according to historical behavior, which can be disseminated to at least n·(e–1)/e honest nodes. Our evaluation shows that SybilBF outperforms state of the art mechanisms improving SybilLimit by a factor of (1/e)· at least.     

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

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

基于本体与上下文感知矩阵的查询扩展算法

针对物理世界的信息查找在过去几年间也受到广泛关注,但是迄今还缺乏深入的研究.目前针对Web信息空间的搜索算法不适合普适空间内的信息查询,原因有二:面向物理实体查询的支撑技术,如嵌入式设备和无线通信,与传统Web信息搜索不同:物理实体相关的信息与Web网页不同,表现在元数据、信息动态性等方面.同时,由于用户查询用词与文档...     

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

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